Codeforces #173 Div2 D "Yet Another Number Game"
問題
奇妙なゲームがある。
ゲームを始めるにあたって、
まず負ではないN個の整数a1, a2 ... aNが与えられる。
そして、以下の2つの操作のどちらかを行う
- 操作A. a1からaNまでの整数を選び(aiとする)、数値x(1 <= x <= ai)を決め、
- 操作B. a1,a2...aNでの最も小さい数をaiとしたとき、数値x(1 <= x <= ai)を決め、
上記の2つの操作のどちらも出来なくなってしまった方の負けである。
ここで、Nと整数a1, a2 ... aNが与えられた時、
先攻後攻どちらが勝つかを出力せよ。
制約
1 <= N <= 3
0 <= ai <= 300
ACしてるコードをカンニング
Nによって場合わけを行う。
N == 1の場合
唯一の整数a1が0なら後攻が勝ち。
それ以外なら先攻が勝ち。
N == 2の場合
Nimのように出来ないか考えてみる。
Nimは次のような考え方から答えを導き出せる
a bを石の数として、 a^b=0の状態で石を取ると、必ずa^b!=0になる。 a^b!=0の状態からa^b=0となる石の取り方が必ず存在する。 a=0, b=0はa^b=0なので、 a^b!=0の状態を迎えたほうが勝ち。
今回のゲームでは、a1 = a2のとき、a1^a2=0で、
Nimにおいては負けなのだが、
操作Bを使うと勝ててしまうので、Nimの考え方は使えない。
そこで、
bool (i, j): a1 = i, a2 = jの時、先攻が勝つか?
のDPを行う。
まず(0,0):= falseとする。
それから各i, jにおいて、
・iをx(1~i)引いてみる
・jをx(1~j)引いてみる
・iとjをx(1~min(i,j))引いてみる
の3つの操作を一通り行った時、
falseとなっているものがあれば、
(i,j) = trueとなる。
計算量はだいたい
300 * 300 * (300 + 300 + 300)/ 2くらい
N == 3の場合
またまたNimのように出来ないか考えてみる。
操作Bを実行して、
a^b=0 から a^b=0に遷移するものが存在しないか考えてみる。
例) a1 = 5 a2 = 3 a3 = 6 ビット列 1 2 3 1 0 1 = 5 0 1 1 = 3 1 1 0 = 6 xor 0 0 0 = 0 1を引いてみる ビット列 1 2 3 1 0 0 = 4 0 1 0 = 2 1 0 1 = 5 xor 0 1 1 != 0 2を引いてみる ビット列 1 2 3 0 1 1 = 3 0 0 1 = 1 1 0 0 = 4 xor 1 1 0 != 0 3を引いてみる ビット列 1 2 3 0 1 0 = 2 0 0 0 = 0 0 1 1 = 3 xor 0 0 1 != 0
どうやら3個の時は大丈夫っぽい・・
(証明がよく分からん)
よって、Nimのように、a1^a2^a3が0か否かで判断する。
自分が勘違いしてた部分なのだけど、
n == 3の時、0 3 3のように何か1つでも0になったら、
操作Bは使えない(1 <= x <= 0のようなxはない)んだね・・・
ソースコード
int n, a[4]; cin >> n; for( int i = 1; i <= n; i++ ){ cin >> a[i]; } // n == 2用のdp bool win[301][301]; memset( win, false, sizeof(win) ); for( int i = 0; i <= 300; i++ ){ for( int j = 0; j <= 300; j++ ){ bool ok = false; // iを1つずつ減らしたのを見ていく for( int t = i - 1; t >= 0; t-- ){ if( !win[t][j] ) ok = true; } // jを1つずつ減らしたのを見ていく for( int t = j - 1; t >= 0; t-- ){ if( !win[i][t] ) ok = true; } // 両方減らしたのを見ていく for( int t = min(i,j); t >= 1; t-- ){ if( !win[i-t][j-t] ) ok = true; } if( ok ) win[i][j] = true; } } if( n == 1 ){ if( a[1] != 0 ){ cout << "BitLGM" << endl; }else{ cout << "BitAryo" << endl; } } if( n == 2 ){ if( win[a[1]][a[2]] ){ cout << "BitLGM" << endl; }else{ cout << "BitAryo" << endl; } } if( n == 3 ){ int x = a[1] ^ a[2] ^ a[3]; if( x != 0 ){ cout << "BitLGM" << endl; }else{ cout << "BitAryo" << endl; } } }