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

kmjp's blog

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

TopCoder SRM 597 Div1 Medium ConvexPolygonGame

SRM

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

問題

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

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

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

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

解法

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


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

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

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

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

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

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

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

以下のコードでは念のため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";
	}
};

まとめ

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

広告を非表示にする