Codeforces #557 Div1 C. Thanos Nim

これはシンプルな問題設定でよかった。
https://codeforces.com/contest/1161/problem/C

問題

以下の変則Nimを行う。
偶数個の石の山がある。
各手番では、そのうちちょうど半分の山を選び、それぞれ1個以上任意の数の石を取り除く。
半分の山を選べなくなったら負け。

初期状態に対し、互いに最適手を取ると勝者は先手後手どちらか。

解法

最小値が過半数の状態だと負けになる。
これを示すには、負け状態で何をやっても相手の勝ち状態になり、相手の勝ち状態から常に負け状態に持ち込めることを確認すればよい。

• 最小値が過半数の場合、選んだ山の中に必ず最小値の山がいくつか含まれ、かつ過半数は選べないので、自分の手番のあとは最小値の山の数は半分以下、すなわち勝ち状態になる。
• 逆に最小値が半分以下の場合、最小値以外の要素をN/2個選んで最小値と一致させると、最小値が過半数、すなわち負け状態になる。

int N;
int A[51];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	sort(A,A+N);
	if(A[0]==A[N/2]) cout<<"Bob"<<endl;
	else cout<<"Alice"<<endl;
	
	
}

まとめ

かなり考察に手間取ったし、コードは非常に単純だけど、考察が楽しめて良かったです。