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) );
}};