yukicoder : No.761 平均値ゲーム

これはあまり迷わなかった。
https://yukicoder.me/problems/no/761

問題

数列が与えられ、２人で交互にターンが来るゲームを行う。
各自のターンでは以下のいずれかを行える。

• 現状の平均以上の要素を削除する。
• 現状の平均未満の要素を削除する。

自分のターン開始時で要素数が０であると負けである。

互いに最適手を取る場合、勝者はいずれか。

解法

先に数列をソートしておく。
そうすると、各ターンでは数列を平均値を境界として２分割していずれかを選択することに相当する。
分割位置は数列の累積和を取っておけば二分探索で求められる。
あとはDFSで互いに勝利確定パターンを取れるかどうか判定しよう。

int N;
ll A[101010];
ll S[101010];

int win(int L,int R) {
	if(R<=L) return 0;
	if(A[L]==A[R-1]) return 1;
	
	ll sum=S[R]-S[L];
	int x;
	ll M=R-1;
	for(x=20;x>=0;x--) if(M-(1<<x)>=L && A[M-(1<<x)]*(R-L)>=sum) M-=1<<x;
	
	return win(L,M)==0||win(M,R)==0;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
		S[i+1]=S[i]+A[i];
	}
	
	if(win(0,N)) cout<<"First"<<endl;
	else cout<<"Second"<<endl;
	
}

まとめ

シンプルな設定で良いね。