TopCoder SRM 597 Div1 Medium ConvexPolygonGame

600ptのMediumなのでびっくりするが、あることに気づくと450pt級になる問題。
本番では気づかなかったし、正答率も異常に低い問題だったけど…。
http://community.topcoder.com/stat?c=problem_statement&pm=12785

問題

格子点を頂点とする凸多角形が与えられる。
ここで以下の手順で２人交互に以下の条件を満たす多角形を作成するゲームを行う。

• 新しい多角形は元の多角形の内部または辺上にある。頂点は共有しない。
• 頂点は格子点上にある。
• 点の数は任意である。
• 面積が正である。

新しい多角形を作成したら、前の多角形は削除する。
条件を満たす多角形を作れなかったら負け。

２人が最適手を取った場合、勝つのはどちらか。

解法

本番は、1辺1の直角二等辺三角形を作って失敗した。
終了５分前に鈍角三角形に対応できないことに気づいたけど間に合わなかった。

この問題は大幅に簡略化できる。
仮に先手が１手目で、ある多角形を作ったとする。

• 後手がその内部に２手目の多角形を作れなければ先手の勝ちである。
• 後手がその内部に２手目の多角形を作れてしまう場合、２手目の多角形は初期状態の多角形内部にあるので、先手が１手目で（後手が２手目で作るはずだった）多角形を作ってしまうことができる。

再帰的に考えると、次に後手が作れそうな多角形を先手が先取りして作れるので、結局先手が１手目に多角形を作れるならば勝ちである。

ここから、この問題は以下のように言い換えられる。

• 凸多角形に対し、内部または辺上にある格子点で面積のある３角形を作れるなら先手が勝ち。作れないなら後手の勝ち。

ここまで来たらもう450ptレベルの問題。

X座標の範囲が高々20000なので、各整数のX座標ごとに配置できる格子点の数を数える。
もしあるX座標に格子点が2個以上あり、他のX座標に１個でも格子点があれば三角形を作れる。
各X座標に格子点が1個以下しかない場合、全部で格子点が３個以上あって全部が一直線上になければ三角形を作れる。

以下のコードでは念のためXとYを逆にしてチェックしてるけど、不要かも。

class ConvexPolygonGame {
	public:
	int N;
	pair<int,int> RR[200001];
	int okok(vector <int> X, vector <int> Y) {
		int i;
		int mix=X[0],miy=Y[0],maxx=0,x;
		FOR(i,N) mix=min(mix,X[i]),miy=min(miy,Y[i]);
		FOR(i,N) X[i]-=mix,Y[i]-=miy;
		FOR(i,N) maxx=max(maxx,X[i]);
		FOR(i,maxx+1) RR[i].first=1000000,RR[i].second=-1000000;
		
		FOR(i,N) RR[X[i]].first=min(RR[X[i]].first,Y[i]+1),RR[X[i]].second=max(RR[X[i]].second,Y[i]-1);
		FOR(i,N) {
			if(X[i]==X[(i+1)%N]) continue;
			for(x=min(X[i],X[(i+1)%N])+1;x<max(X[i],X[(i+1)%N]);x++) {
				ll dy=(Y[(i+1)%N]-Y[i])*(ll)(x-X[i])+Y[i]*(ll)(X[(i+1)%N]-X[i]);
				ll dx=X[(i+1)%N]-X[i];
				if(dy%dx==0) {
					RR[x].first=min(RR[x].first,(int)(dy/dx));
					RR[x].second=max(RR[x].second,(int)(dy/dx));
				}
				else {
					RR[x].first=min(RR[x].first,(int)(dy/dx)+1);
					RR[x].second=max(RR[x].second,(int)(dy/dx));
				}
			}
		}
		int num2=0,num1=0;
		vector<pair<int,int> > SS;
		FOR(i,maxx+1) {
			//_P("%d %d %d\n",i+mix,RR[i].first+miy,RR[i].second+miy);
			if(RR[i].second-RR[i].first>=1) num2++;
			if(RR[i].second-RR[i].first==0) {
				num1++;
				SS.push_back(make_pair(i,RR[i].first));
			}
		}
		
		if(num2>=2 || (num2&&num1)) return 1;
		if(num1<3) return 0;
		
		for(i=2;i<num1;i++) {
			if((SS[1].first-SS[0].first)*(ll)(SS[i].second-SS[0].second)-(SS[i].first-SS[0].first)*(ll)(SS[1].second-SS[0].second))
				return 1;
		}
		
		return 0;
		
	}
	
	string winner(vector <int> X, vector <int> Y) {
		N=X.size();
		if(okok(X,Y) || okok(Y,X)) return "Masha";
		return "Petya";
	}
};

まとめ

三角形が作れさえすればよい、と気づけばだいぶ簡単だけど、自分含め多くの人は気づかなかったようだ。