SRM 538 450pt : TurtleSpy
問題概要
前進、後進、回転の操作列を適切に並び替えて原点からの距離を最大化する問題。
解法
前進、後進は全部まとめた方が良い。後は回転をその間にどう挟むか。つくれる角度は超簡単なDPで計算しておく。
acceptされたコード
色々無駄はあるけどバグの生まれにくい書き方ではあったと思う。
#include <cmath> #include <vector> #include <string> #include <sstream> #include <numeric> using namespace std; const int MAX_N = 50; const double PI = atan(1.0) * 4.0; bool can_make[MAX_N + 1][360]; struct TurtleSpy { double sq(double x){ return x * x; } double maxDistance(vector <string> commands) { vector<int> fs, bs, as; for(int i=0; i<(int)commands.size(); i++){ stringstream ss(commands[i]); string cmd; int x; ss >> cmd >> x; if(cmd == "forward"){ fs.push_back(x); } else if(cmd == "backward"){ bs.push_back(x); } else if(cmd == "right"){ as.push_back(x); } else{ as.push_back( (360 - x) % 360); } } if(fs.empty()){ return (double)accumulate(bs.begin(), bs.end(), 0); } else if(bs.empty()){ return (double)accumulate(fs.begin(), fs.end(), 0); } can_make[0][0] = true; const int N = as.size(); for(int i=0; i<N; i++){ for(int j=0; j<360; j++)if(can_make[i][j]){ can_make[i+1][j] = true; can_make[i+1][(j + as[i] + 360) % 360] = true; } } double f = (double)accumulate(fs.begin(), fs.end(), 0); double b = (double)accumulate(bs.begin(), bs.end(), 0); double ans = 0.0; //forward -> backward for(int a=0; a<360; a++)if(can_make[N][a]){ double x = f - cos(a*PI/180)*b; double y = 0 - sin(a*PI/180)*b; ans = max(ans, sqrt(sq(x) + sq(y))); } //backward -> forward for(int a=0; a<360; a++)if(can_make[N][a]){ double x = -b + cos(a*PI/180)*f; double y = -0 + sin(a*PI/180)*f; ans = max(ans, sqrt(sq(x) + sq(y))); } return ans; } };