TopCoder SRM 538 Div1 Medium TurtleSpy

これは割と簡単に解けた。
http://community.topcoder.com/stat?c=problem_statement&pm=11704

問題

ロボットに与えられるN個の命令がある。
このN個の命令は以下のいずれかの形をしている。

• 左にX度向きを回転
• 右にX度向きを回転
• 距離Xだけ前進
• 距離Xだけ後退

N個の命令の適用順の入れ替えが可能である時、初期位置からの移動距離を最大化せよ。

解法

このロボの移動には以下の特性がある。

• 向きを変えて前進して、また向きを変えて前進して…というのは効率が悪く、前進は初期位置から離れる向きにまとめて行うのが良い。後退も同様である。
• 前進と後退の命令を使い終わった後の回転は意味がない。同様に、移動前の回転も意味がない。

よって以下の戦略が考えられる。
「ひとまず前進命令をすべて使って前進し、回転命令をいくつか使った後後退命令をいくつか使い、最も初期位置から離れた位置を求める。」

幸い今回回転角度は度数法で整数で与えられるので、360通りしかない。
そこで回転命令をDPして、得られる回転角を列挙し、「前進後回転して後退」の総距離を余弦定理で求めればよい。

class TurtleSpy {
	public:
	double maxDistance(vector <string> commands) {
		vector<int> cmd;
		int dp[51][360];
		int i,x;
		double fw=0,bw=0;
		ITR(it,commands) {
			if(sscanf(it->c_str(),"forward %d",&i)>0) fw+=i;
			if(sscanf(it->c_str(),"backward %d",&i)>0) bw+=i;
			if(sscanf(it->c_str(),"left %d",&i)>0)  cmd.push_back(i);
			if(sscanf(it->c_str(),"right %d",&i)>0)  cmd.push_back(360-i);
		}
		
		ZERO(dp);
		dp[0][0]=1;
		FOR(i,cmd.size()) {
			FOR(x,360) if(dp[i][x]) {
				dp[i+1][x] = dp[i+1][(x+cmd[i])%360] = 1;
			}
		}
		double ma=0;
		FOR(x,360) if(dp[cmd.size()][x]) {
			double dist=sqrt(fw*fw+bw*bw-2*fw*bw*cos((x)*atan(1)*4/180.0));
			ma=max(ma,dist);
		}
		return ma;
	}
}

まとめ

これはあっさり思いつけたな。