Golden Week Contest 2015 : F - ピラミッド - 誕生日編

これは少し悩んだけど、本番解けた。
http://gwcontest2015.contest.atcoder.jp/tasks/gw2015_f

問題

N要素の自然数からなる数列A[i]が与えられる。
この数列に対し、２人交互にターンを行うゲームを考える。

自分のターンでは以下の何れかの手を取ることができる。

• 正の値である要素を１つ選び、１減らす
• 全要素が正の値なら、全要素から１減らす

自分のターンで全要素０にしたら勝ちである。
先手後手最適手を取った場合、勝者はどちらか。

解法

１つ目の手を取る場合、どの要素から選ぶかは余り重要ではない。
最小値が0の要素が登場すると２つ目の手が取れなくなる。
よって手の取り方は以下の３通り。

• 最小値が正なら、それをさらに1減らす。
• 最小値より大きな要素が1個でもあれば、それをさらに1減らす。
• 最小値が正なら、全要素を1減らす。

よって状態として(残り合計値, 最小値)だけ持てばよい(最小値*N==残り合計値かどうかで、皆同じ最小値に一致するかわかる)。
あとはメモ化再帰で探索する。

int N;
int A[51];
int sum,mi=1000;
int memo[3000][51];

int win(int tot,int mi) {
	int& ret=memo[tot][mi];
	if(ret>=0) return ret;
	if(tot==0) return 0;
	ret = 0;
	
	if(tot>mi*N) {
		if(win(tot-1,mi)==0) ret=1;
	}
	if(mi>0) {
		if(win(tot-N,mi-1)==0) ret=1;
		if(win(tot-1,mi-1)==0) ret=1;
	}
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i], sum+=A[i], mi=min(mi,A[i]);
	MINUS(memo);
	
	if(win(sum,mi)) cout<<"Iori"<<endl;
	else cout<<"Yayoi"<<endl;
}

まとめ

これ本番も余り苦戦してなかったな。