kmjp's blog

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

yukicoder : No.361 門松ゲーム2

こちらはすんなり。
http://yukicoder.me/problems/1016

問題

2人で交互に竹を分割するゲームを行う。
各人の手番では、手持ちの竹のうち一つを選び、以下の条件を満たす範囲で長さを3分割する。

  • 各長さは正整数。
  • 3つの長さは門松列を成すように並べられる。
  • 3つの長さの最大値と最小値の差はD以内。

自分の手番で分割できなくなったら負けである。
初期状態で長さLの竹が1本ある場合、互いに最適手を取ったときの勝者はどちらか。

解法

Nimで解くだけ。
門松列は余り意識する必要はない。3つ異なる長さの竹に分割すれば、最長の竹を真ん中に持ってくるだけで門松列になる。

int L,D;
int gr[501];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>L>>D;
	for(i=1;i<=L;i++) {
		set<int> me;
		for(x=1;x<=i-1;x++) {
			for(y=x+1;i-(x+y)>y;y++) {
				r=i-x-y;
				if(r-x<=D) me.insert(gr[x]^gr[y]^gr[r]);
			}
		}
		while(me.count(gr[i])) gr[i]++;
	}
	
	if(gr[L]==0) _P("matsu\n");
	else _P("kado\n");
	
}

まとめ

竹の分割アニメーションこってるな。