yukicoder : No.1852 Divide or Reduce

最初の★設定はちょっと低めだったよね。
https://yukicoder.me/problems/no/1852

問題

N要素の正整数列Aが与えられ、2人でターン制のゲームを行う。
各自の手番では以下のいずれかを行う。

• Aの全要素が2以上の場合、全要素デクリメントする
• Aのうち2以上の値を持つ要素を選び、合計が元の値と一致する2つの正整数を持つ要素に分割する

自分の手番でどちらもできなくなると負けとなる。
互いに最適手を取るとき、勝者はどちらか。

解法

Aの最小値が1の時、後者の手しか取れない。
この場合、後者の手数を取れる回数は、結局Aの全要素1になるまでなので、sum(A)-|A|である。
これを踏まえて分類していく。

• Aの最小値が1の場合
  • 2人が取れる手数はsum(A)-|A|で固定なので、その偶奇で勝者が決まる
• Aの最小値が2以上の場合
  • sum(A)-|A|が奇数の時、1要素を選んで1と残りに分類すると、sum(A)-|A|が偶数になる。あとは上記手順に則り先手が勝つ。
  • sum(A)-|A|が偶数の時、
    • |A|が奇数の場合、先手がどんな手順をとってもsum(A)-|A|が奇数になり、後手はsum(A)-|A|を偶数にできる。最終的にsum(A)-|A|=0になり先手必敗。
    • |A|が偶数の場合、後者の手順を取ると先手が負けてしまうので、前者の処理を行うしかない。後手も同様の状態なので、結局Aの最小値の偶奇で決まる。

int T,N,A[202020];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	cin>>T;
	while(T--) {
		cin>>N;
		ll sum=0;
		FOR(i,N) {
			cin>>A[i];
			sum+=A[i];
		}
		sort(A,A+N);
		if(A[0]==1) {
			if((sum-N)%2==1) {
				cout<<"First"<<endl;
			}
			else {
				cout<<"Second"<<endl;
			}
		}
		else {
			if((sum-N)%2==1) {
				cout<<"First"<<endl;
			}
			else {
				if(N%2) {
					cout<<"Second"<<endl;
				}
				else {
					if(A[0]%2==0) {
						cout<<"First"<<endl;
					}
					else {
						cout<<"Second"<<endl;
					}
				}
			}
		}
	}
}

まとめ

★２はちょっと厳しいよね…。