TopCoder SRM 598 Div1 Medium FoxAndFencing

さっきのDiv2 Hardをもう少しややこしくした問題。
http://community.topcoder.com/stat?c=problem_statement&pm=12864

問題

基本設定はDiv2 Hardと一緒。
１列のセル上で、先手と後手がDマスの距離で配置されている。
両者は１ターンでmov1,mov2マス移動できる。

ただ、勝利条件がDiv2 Hardと異なる。
Div2 Hardは相手マスに重なれば勝ちだが、こちらは両者に射程距離rng1,rng2が設定されており、自分のターンで移動後に相手マスが射程距離内にあれば勝ちになる。

両者が最適手を取った場合の勝者を答えよ。

解法

基本的にはDiv2 Hardと同じアプローチが取れる。

互いに相手に勝ち目があれば相手に近づくし、勝ち目がなければ相手から逃げようとする。

• 先手が１手目で攻撃できれば先手が勝利。
• 先手が１手目で攻撃できず、先手が逃げても後手１手目で攻撃できれば後手の勝ち。
• それ以外の場合、以下の条件を満たした方が勝ち。
  • 自分をX、相手をYとすると、相手の射程外のマスから、相手が逃げても攻撃が当たる。すなわち(movX+rngX >= (movY + rngY +1) + movY)である
  • 自分の方が速い(そうでないと相手が逃げ切る)

class FoxAndFencing {
	public:
	string WhoCanWin(int mov1, int mov2, int rng1, int rng2, int d) {
		
		if(mov1+rng1>=d) return "Ciel";
		if(d+mov1<=mov2+rng2) return "Liss";
		if(mov1>mov2) {
			if(mov1+rng1>=mov2*2+rng2+1) return "Ciel";
		}
		else if(mov1<mov2) {
			if(mov2+rng2>=mov1*2+rng1+1) return "Liss";
		}
		return "Draw";
	}
};

まとめ

Medium550ptの割にあっけない問題。