AOJ 宇宙ヤシガニ(Space Coconut Grab) 解説

問題
Space Coconut Grab | Aizu Online Judge

解説
３つの変数をループで回して全探索すると、O(10^9)となってTLEします。
しかし、x+y*y+z*z*z=eになることから、y,zが分かればxが分かります。

よってy,zを２重ループで回して、残りのxをx = e- y*y - z*z*z と算出できます。
このときの計算量はO(10^6)まで落ちるので間に合います。
またこの過程では、計算により求めたxの値がマイナスになることがあります。これはx+y*y+z*z*z=e において、左辺が大きくなりすぎているということなので、continueすることで除外します。

int main(){
    while(1){
        int e;
        int ans=1e9+7;
        cin>>e;
        if(e==0)break;
         
        rep(y,0,1000){
            rep(z,0,1000){
                int x=e-y*y-z*z*z;
                if(x<0)continue;
                ans=min(ans,x+y+z);
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}