SRM538 Div1 Medium(450) TurtleSpy
TurtleSpy
ジグザグに進むと距離は短くなる。前進して、なるべく180°に近くなるように回転して、後退する。角度は整数で360通りしかないので、動的計画法により、回転可能な角度を求めることができる。
#include <sstream> #include <string> #include <vector> #include <cmath> using namespace std; class TurtleSpy{public: double maxDistance( vector <string> commands ) { const int C = 360; const double PI = acos(-1.0); int f = 0; // fowardの合計 int b = 0; // backwardの合計 vector<int> t; // 回転 for ( int i=0; i<(int)commands.size(); i++ ) { stringstream ss(commands[i]); string c; int x; ss>>c>>x; if ( c=="left" ) t.push_back(x); if ( c=="right" ) t.push_back(-x); if ( c=="forward" ) f += x; if ( c=="backward" ) b += x; } // tの要素の和で作れる角度のうち、180°に最も近いものを求める vector<bool> T(C); T[0] = true; for ( int i=0; i<(int)t.size(); i++ ) { vector<bool> P = T; for ( int j=0; j<C; j++ ) if ( P[j] ) T[(j+t[i]+C)%C] = true; } int m = C/2; for ( int i=0; i<C; i++ ) if ( T[i] ) m = min( m, abs(i-C/2) ); double a = m/360.*2*PI; return hypot( f+b*cos(a), b*sin(a) ); }};