SRM 538 div1 med: TurtleSpy

問題

TopCoder Statistics - Problem Statement

解法

forward に全振りして進む -> 適当に回転 -> backward に全振りして進む -> 余った分の回転をする
というのが最適になります。以下しばらく適当な説明↓

「forward に全振り」って言うのが正しい場合は, backward に全振りしたほうが良いのは明らかで, なるべく原点から離れる方向に角度をセットしてから離れるのを全部やるのが良いからです。

回転しないのに forward と backward を混ぜるのは明らかに無駄です。
回転しながら forward を使っていく選択肢もありますが, 下図を見ると全振りの方が強そうです(内積とか使えば長いことを示せそう)。

全部混ぜろ(forward の後に rotation, で backward とか)と言われると…うーん, なんか全振りのほうが得じゃないですか？(適当)

はっきりした証明はわかりませんがこんな感じのことを考えて解きました。

「適当に回転」ってところで回転できる角度が列挙できれば答えが求まります(余弦定理を使うだけ)が, これは簡単な dp で出来ます。

余弦定理じゃなくて, 複素数とかを使うと楽だったっぽいです。なるほど。

bool dp[55][360];
const double pi = acos(-1);

double calc(double x, double y, double theta) {
    if (theta > pi) theta = 2*pi - theta;
    return sqrt(x*x + y*y - 2*x*y*cos(theta));
}

class TurtleSpy {
public:
    double maxDistance(vector <string> commands) {
        int forward = 0, backward = 0;
        vector<int> angle;
        for (string s : commands) {
            stringstream ss(s);
            string t;
            int X;
            ss >> t >> X;
            if (t == "forward") forward += X;
            if (t == "backward") backward += X;
            if (t == "right") angle.push_back(X);
            if (t == "left") angle.push_back(-X);
        }
        int sz = angle.size();
        memset(dp, false, sizeof(dp));
        dp[0][0] = true;
        for (int i = 0; i < sz; i++) {
            for (int j = 0; j < 360; j++) {
                if (!dp[i][j]) continue;
                dp[i+1][j] = true;
                int next = (j+angle[i]+360)%360;
                dp[i+1][next] = true;
            }
        }
        double ans = 0;
        for (int i = 0; i < 360; i++) {
            if (!dp[sz][i]) continue;
            ans = max(ans, calc(forward, backward, i*pi/180));
        }
        return ans;
    }
};