読者です 読者をやめる 読者になる 読者になる

kmjp's blog

競技プログラミング参加記です

TopCoder SRM 598 Div2 Hard FoxAndFencingEasy

SRM

実際にはDiv1 Mediumを先に解いている。
Div1 Mediumを解いていたら非常にあっけなく終わる問題。
http://community.topcoder.com/stat?c=problem_statement&pm=12414

問題

1列に並んだセル上で、2人は初期状態でDの距離にある。
2人はそれぞれ1手で距離mov1、mov2以下の範囲にあるマスに移動できる。

将棋のように、先手・後手が交互に移動し、敵のいるマスに自分の手で重なると勝ちである。
D,mov1,mov2に対して、両者が最適手を取ったときの勝者を答えよ。

解法

先手は初手で相手を攻撃できれば勝ち。

それ以外のケースでは、基本的にmov1,mov2の大きい方が有利。
移動距離の大きい方が、相手の射程外にいてかつ相手が逃げても次のターンで追いつければ勝利。
たとえば先手の方が移動距離が大きい場合、後手の射程外である距離(mov2+1)のセルに到達し、次に後手がmov2マス逃げた距離(2*mov2+1)を1手で詰められるなら勝てる。
そこまで大きくない場合、相手の攻撃を避けつつ逃げる相手を追い詰められないので引き分け。

class FoxAndFencingEasy {
	public:
	string WhoCanWin(int mov1, int mov2, int d) {
		if(mov1>=min(d,mov2*2+1)) return "Ciel";
		if(mov2>=mov1*2+1) return "Liss";
		return "Draw";
	}
};

まとめ

Div2 Hardとしてはコード量が極端に少ない回。

広告を非表示にする