オイラープロジェクト301～310 - c21coterie @ ウィキ

問い306

次のゲームは, 組み合わせゲーム理論の古典的な例である:
２人のプレイヤーが, 一列に並んだ n 個の白い正方形から開始して, 交互にターンを行う.
各ターンでは, プレイヤーは２つの隣り合う白い正方形を選び, 黒で塗る.
最初に色を塗ることができなくなったプレイヤーが負けとなる.
n = 1 の場合, 有効な手はないため, 先手が自動的に負けとなる.
n = 2 の場合, 有効な手は１つのみであり, その後, 後手が負けとなる.
n = 3 の場合, 有効な手は２つあるが, どちらも後手が負ける状況となる.
n = 4 の場合, 有効な手は先手に３つある; 先手は中央の２つの正方形を塗ると勝利できる.
n = 5 の場合, 有効な手は先手に４つある(下図に赤で示す); しかしいずれを選んでも, 後手(青)が勝利する.
したがって, 1≦n≦5 に対し, 先手必勝となる n の値は 3 個ある.
同様に, 1≦n≦50 に対し, 先手必勝となる n の値は 40 個ある.
1≦n≦1 000 000 に対し, 先手必勝となる n の値は何個あるか.

この問題見た目より難しい、、、
最初ただ単にブロックで左右に分割された両側で互いに勝利を目指してどちらが勝つか調べればいいというのを思いつきます。
しかしこれでは上手くいきません。
なぜなら片方でわざと負けることで得られる勝利があるからです。

その場合を考慮してとりあえずコードを書いてみましたが何か見落としがないか書いたコードにまったく自信がない状態です。
試行錯誤の結果後一歩な感じのコードに到達しました。
calc関数の中のt1==1&&t2==-1かt1==-1&&t2==1のあたりの処理があやしい感じがする。
大学いってないから自分で考えるしかないんだよね。
大変だ、、、

#include<stdio.h>
int memoV[1000001]={0};//先手が勝つ場合1
int memoL[1000001]={0};//わざと負ける場合が可能な場合1
int calc(int size){
//自分の手番で勝てるなら1、勝てないなら-1を返す
int t1,t2,p;
for(int i=0;i<size-1;i++){
	if(i>1)t1=memoV[i];//左側で相手が勝てるなら1
	else t1=0;
	p=size-i-2;
	if(p>1)t2=memoV[p];//右側で相手が勝てるなら1
	else t2=0;
	//printf("<%d %d %d>",i,t1,t2);
	if(t1==0&&t2==-1)return 1;//相手が勝てないと言ってきたので自分の勝ち
	if(t2==0&&t1==-1)return 1;//同じく
	if(t1==0&&t2==0)return 1;		
	if(t1!=0&&t2!=0){
		if(t1==1&&t2==1){
			//相手が両方で勝つ場合
			//相手が片側で勝ちもう片方で負けることになるので自分の勝ちになる
			//まだ相手が片側でわざと負けてきた場合の考慮を行う
			//printf("(a %d)",i);
			if(memoL[i+1]!=1&&memoL[p]!=1){
				return 1;//相手が片方でわざと負けることで勝利をつかもうとしたができない。こちらの勝利
			}
		}
		if(t1==1&&t2==-1){
			//相手が左側で勝ち右で負ける場合
			//こちらが右側でわざと負けることで勝利をつかめる
			//つまり相手が左側でわざと負けることができず右でこちらがわざと負けられる場合のみ勝利
			//printf("(b %d)",i);
			if(memoL[i+1]==0&&memoL[p]==1)return 1;
		}
		if(t1==-1&&t2==1){
		//相手が左側で負け右側で勝つ場合
			//こちらは左側でわざと負けることで勝利をつかめる
			//printf("(c %d)",i);
			if(memoL[i+1]==1&&memoL[p]==0)return 1;
		}
		if(t1==-1&&t2==-1){
			//printf("(d %d)",i);
			return 1;//相手が両側で負ける場合そのままこちらの勝ち
		}
	}
}
//勝てなかったので私の負けと相手に伝える
return -1;
}
int calcLoss(int size){
int t1,t2,p;
for(int i=0;i<size;i++){
	p=size-i-2;
	if(i>1) t1=memoL[i];
	else t1=1;
	if(p>1) t2=memoL[p];
	else t2=1;
	if(t1+t2==2)return 1;
}
return 0;
}
int main(){
memoV[1]=-1;
memoV[2]=1;
memoV[3]=1;
memoV[4]=1;
memoV[5]=-1;
memoL[1]=1;
memoL[2]=0;//負けるための最善手が出来るなら1出来ないなら0
memoL[3]=0;
memoL[4]=1;
memoL[5]=1;
int ans=3;
for(int i=6;i<51;i++){
	memoL[i]=calcLoss(i);
	memoV[i]=calc(i);
	if(memoV[i]==1)ans++;
	printf("%d %d %d\n",i,memoV[i],memoL[i]);
}
printf("ans=%d\n",ans);
}