VK Cup 2015 Round 2 : C. Board Game

かなり面倒な処理を書いてしまったが、最終的には簡単なコードで済んだ。
http://codeforces.com/contest/533/problem/C

問題

2次元座標上で、先手は(Xp,Yp)、(Xv,Yv)にいる。
以下のルールで両者は交互に移動する。

• 先手は、現在位置を(x,y)とすると1手ごとに(x-1,y)か(x,y-1)に移動できる。
• 後手は、現在位置を(x,y)とすると1手ごとに(x-1,y)か(x,y-1)か(x-1,y-1)に移動できる。
• ただし、どちらもx,y座標が負の場所には移動できない。
• また、移動先に相手がいると移動できない。
• 移動はパスしても良い。

両者が最適に行動すると、先に原点につくのはどちらか。

解法

本番はコーナーケースが怖くて愚直にシミュレーションしてしまった。
実際は以下のように解くことができる。

まず、前提として後手は基本(x-1,y-1)に移動するのが最適である。
よって、先手が勝つには後手が(x-1,y-1)に移動できないようにその座標をふさぐか、後手より先に原点につくしかない。

よって以下のどちらかのケースで先手が勝つ。

• Xp≦XvかつYp≦Yvなら、後手の移動先を先手が塞げるので勝でる。
• Xp+Yp≦max(Xv,Yv)なら、後手より先に原点につけるので勝てる。

int X[2],Y[2],T[2];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>X[0]>>Y[0]>>X[1]>>Y[1];
	
	if(X[0]<=X[1]&&Y[0]<=Y[1]) return _P("Polycarp\n");
	if(X[0]+Y[0]<=max(X[1],Y[1])) return _P("Polycarp\n");
	return _P("Vasiliy\n");
}

まとめ

わかってしまえば簡単だが、本番は検討漏れが怖くて愚直シミュレーションを書いてしまった。
まぁ通ったので良かったが…。