yukicoder : No.1770 N言っちゃダメゲーム (6)

なるほど…。
https://yukicoder.me/problems/no/1770

問題

正整数N,Kが与えられる。
2人制の以下のゲームを考える。
変数Xの初期値は0である。
自分の手番では、Xに1～Kのいずれかの整数を加算する。ただし

• 自分の加算によりXがN以上になったら負け
• 直前の相手の手番の加算量と同じ値を加算したら負け

とする。先手が勝つには、初手で何を加算すればよいか列挙せよ。

解法

f(n,k) := 直前の相手がk加算することでX=nとしてきた場合、自分はここから勝てるか
という2次元の配列を考える。初手mを取った場合を考えると、f(m,m)=FalseとなるK以下の正整数の集合が解となる。
O(N*K^2)掛けて愚直にこの配列を埋めれば、解は求められるが、TLに間に合わない。

そこで各f(n,*)に着目すると、

• f(n,*)は全部True
• f(n,*)は全部False
• f(n,*)は1つだけFalseで他はTrue

となる。それぞれが生じる条件を考えると

• f(n+i,i)にFalseが2個以上あれば、f(n,*)は全部True
• f(n+i,i)にFalseが1個あり、それがf(n+j,j)あれば、f(n,j)はFalseでそれ以外はTrue
• f(n+i,i)にFalseが1個もなければ、f(n,*)は全部False

f(n,k)においてFalseなのは高々O(N)個なので、f(n+i,i)=Falseなら、f(n,*)からの遷移先にFalseが1個ある、と数え上げて行っても上記処理はO(N)で済む。

int N,K;

int winq[525252];
vector<int> W[525252];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	cin>>N>>K;

	
	for(i=N-1;i>=0;i--) {
		if(W[i].empty()) {
			winq[i]=-2;
			for(j=1;j<=K;j++) if(i-j>=0) W[i-j].push_back(j);
		}
		else if(W[i].size()>=2) {
			winq[i]=-1;
		}
		else {
			x=winq[i]=W[i][0];
			if(i-x>=0) W[i-x].push_back(x);
		}
	}
	
	int num=0;
	for(i=1;i<=K;i++) {
		if(winq[i]==i||winq[i]==-2) {
			cout<<i<<endl;
			num++;
		}
	}
	if(num==0) cout<<0<<endl;
}

まとめ

色々考えつくなぁ。