yukicoder : No.2814 Block Game

なんか今回数値の上限が大きい問題が多いな。
https://yukicoder.me/problems/no/2814

問題

整数Nと、偶奇が与えられる。
N要素の整数列Aがあり、初期状態で値はいずれも未定義である。

これに対し2人で、交互に1要素を選び非負整数値を埋めて行く。この時、Aは1～NのPermutationでなければならない。
こうしてできたAに対し、A'[i]=A[i]+A[i+1]となるような要素数|A|-1の整数列A'を作り、AをA'で更新することを要素数が1になるまで繰り返す。
その結果が、与えられた偶奇と一致すれば先手、不一致なら後手の勝利とする。
両者最適手を取るとき、勝者はどちらか。

解法

Lucasの定理より、N要素のうち偶奇に影響を及ぼす要素数が判定できる。

• N=1,2の時、最後の値は奇数になる。
• Nがそれ以外の2の累乗の場合、最後の値は偶数になる。
• Nがそれ以外の場合、最後の1手を打つ側が勝ち。

int T;
ll N;
string S;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>S;
		if(N==1||N==2) {
			if(S=="Odd") {
				cout<<"Alice"<<endl;
			}
			else {
				cout<<"Bob"<<endl;
			}
		}
		else if((N&(N-1))==0) {
			if(S=="Even") {
				cout<<"Alice"<<endl;
			}
			else {
				cout<<"Bob"<<endl;
			}
		}
		else if(N%2) {
			cout<<"Alice"<<endl;
		}
		else {
			cout<<"Bob"<<endl;
		}
	}
}

まとめ

うーむ、どうしても実験ゲーになってしまう。