Codeforces #876 : Div2 E. Decreasing Game

全完できず…。
https://codeforces.com/contest/1839/problem/E

問題

N要素の整数列Aを使い以下のゲームを行うinteractiveゲームである。
先手が1つ非負要素を選び、後手が別の非負要素を選ぶ。もし自分の手番でそのような要素を選べないと負けである。
その後、両要素から小さい方の値を引く。

Aが与えられたとき、先手・後手を選択できる場合、相手に勝利せよ。

解法

力技で解ける。
Aのsubsetのうち、ちょうど総和がA全体の総和の半分である場合、後手を取るとそのような状態を継続できる。
最終的にAが全部0になって後手が勝つ。
そうでない場合、先手を取って適当にやっていると先手が勝つ。

前者の判定はナップサック問題なのでbitsetで解けばよい。

int N;
int A[303];
bitset<90200> BS[301];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	BS[0][0]=1;
	int sum=0;
	FOR(i,N) {
		cin>>A[i];
		BS[i+1]=BS[i]|(BS[i]<<A[i]);
		sum+=A[i];
	}
	
	set<int> S[2];
	if(sum%2==0&&BS[N][sum/2]) {
		cout<<"Second"<<endl;
		sum/=2;
		int cur=N;
		while(cur>0) {
			cur--;
			if(sum>=A[cur]&&BS[cur][sum-A[cur]]) {
				S[0].insert(cur);
				sum-=A[cur];
			}
			else {
				S[1].insert(cur);
			}
		}
		while(1) {
			cin>>j;
			if(j==0) break;
			j--;
			int t=S[0].count(j);
			FORR(c,S[t]) {
				if(A[c]) x=c;
			}
			cout<<(x+1)<<endl;
			k=min(A[x],A[j]);
			A[x]-=k;
			A[j]-=k;
		}
	}
	else {
		cout<<"First"<<endl;
		while(1) {
			FOR(i,N) if(A[i]) break;
			cout<<(i+1)<<endl;
			cin>>j;
			if(j==0) break;
			j--;
			k=min(A[i],A[j]);
			A[i]-=k;
			A[j]-=k;
		}
	}
	
}

解法

こういうのさっと思いつかないな。