結果

問題 No.524 コインゲーム
ユーザー @abcde@abcde
提出日時 2019-03-10 16:08:32
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 2 ms / 1,000 ms
コード長 4,264 bytes
コンパイル時間 1,558 ms
コンパイル使用メモリ 164,168 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-23 15:18:38
合計ジャッジ時間 2,187 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 1 ms
6,944 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 1 ms
6,940 KB
testcase_05 AC 1 ms
6,940 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 1 ms
6,940 KB
testcase_08 AC 1 ms
6,944 KB
testcase_09 AC 1 ms
6,940 KB
testcase_10 AC 1 ms
6,940 KB
testcase_11 AC 2 ms
6,940 KB
testcase_12 AC 1 ms
6,940 KB
testcase_13 AC 1 ms
6,940 KB
testcase_14 AC 1 ms
6,940 KB
testcase_15 AC 1 ms
6,944 KB
testcase_16 AC 1 ms
6,944 KB
testcase_17 AC 2 ms
6,944 KB
testcase_18 AC 1 ms
6,940 KB
testcase_19 AC 1 ms
6,940 KB
testcase_20 AC 1 ms
6,944 KB
testcase_21 AC 2 ms
6,944 KB
testcase_22 AC 2 ms
6,944 KB
testcase_23 AC 1 ms
6,944 KB
testcase_24 AC 1 ms
6,944 KB
testcase_25 AC 2 ms
6,944 KB
testcase_26 AC 2 ms
6,940 KB
testcase_27 AC 1 ms
6,940 KB
testcase_28 AC 2 ms
6,944 KB
testcase_29 AC 2 ms
6,944 KB
testcase_30 AC 1 ms
6,940 KB
testcase_31 AC 1 ms
6,940 KB
testcase_32 AC 1 ms
6,944 KB
testcase_33 AC 1 ms
6,940 KB
testcase_34 AC 2 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// コメント修正して, 再提出.
// TODO: 解答不能のため, 以下のサイトを参考にした.
// ニム（複数山の石取りゲーム）の必勝法.
// https://mathtrain.jp/nim
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

// n桁の0埋めの数字を作る.
// https://gin0606.hatenablog.com/entry/2013/12/24/134138
// @param s: 0埋めしたい文字列(※d桁より多い場合は, 0埋め出来ないので何もしない).
// @param d: 0埋め後の桁数.
string fillText(string s, LL d) {
    string ret = s;
    while(ret.size() < d) ret = "0" + ret;
    return ret;
}

// Use of dynamic bitset to convert decimal numbers.
// https://stackoverflow.com/questions/42759330/use-of-dynamic-bitset-to-convert-decimal-numbers
// 10進数 → 2進数.
// @param n: 2進数へ変換したい10進数.
// @param d: 2進数表記する桁数.
// @return: 2進数.
string decimalToBinary(LL n, LL d) {
    if(n == 0) return fillText("0", d);
    string ret;
    LL ln = abs(n);
    while(ln) {
        ret = string((ln & 1) ? "1" : "0") + ret;
        ln /= 2;
    }
    ret = fillText(ret, d);
    if(n < 0) ret = "-" + ret;
    return ret;
}

int main() {
    
    // 1. 入力情報取得.
    LL N;
    cin >> N;
    
    // 2. ニムの必勝法？？？
    // 1 ～ N までの 排他的論理和 を計算し, その各桁の mod 2 を確認する方針とする.
    // ex. 15 までの排他的論理和の合計.
    // 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
    // -> 8888
    // 
    // ex. 他のケースについての排他的論理和の合計.
    // 19 = 16 + 0 + 0 + 2 + 1
    //    = 18888 + 00000 + 00000 + 20011 + 10011
    //    = 4, 8, 8, 10, 10
    // 27 = 16 + 8 + 0 + 2 + 1
    //    = 18888 + 81444 + 00000 + 22011 + 11011
    //    = 12, 12, 12, 14, 14
    // 29 = 16 + 8 + 1 + 0 + 1
    //    = 18888 + 81444 + 44122 + 00000 + 11101
    //    = 14, 14, 14, 14, 15
    
    // 2-1. N の 2進数表現取得(32桁).
    LL d = 0, DN = N;
    while(DN > 0) DN /= 2, d++;
    string nStr = decimalToBinary(N, d);
    // cout << "d=" << d << " nStr=" << nStr << endl;

    // 2-2. 2 の べき乗 を保存.
    LL pow2[d];
    pow2[0] = 1;
    for(LL i = 1; i < d; i++) pow2[i] = 2 * pow2[i - 1];
    // for(LL i = 0; i < d; i++) cout << "pow2[" << i << "]=" << pow2[i] << endl;
    
    // 2-3. N までの 排他的論理和 の 合計 に向けた準備.
    // ex. 29 ならば, nXorStock に, 以下の値を保存.
    // 1 8 8 8 8 
    // 8 1 4 4 4 
    // 4 4 1 2 2 
    // 0 0 0 0 0 
    // 1 1 1 0 1 
    LL nXorStock[d][d];
    for(LL i = 0; i < d; i++){
        int ci = nStr[i] - '0';
        for(LL j = 0; j < d; j++){
            int cj = nStr[j] - '0';
            // cj を 乗ずる必要あり(ex. N = 29 の 1 1 1 0 1 を 作成するパターンなど).
            if(j <  i) nXorStock[i][j] = (pow2[d - 1 - i]) * ci * cj;
            if(j == i) nXorStock[i][j] = 1 * ci;
            if(j >  i) nXorStock[i][j] = (pow2[d - 1 - i] / 2) * ci;
        }
    }
    
    // for(LL i = 0; i < d; i++){
    //     for(LL j = 0; j < d; j++){
    //         cout << nXorStock[i][j] << " ";
    //     }
    //     cout << endl;
    // }
    
    // 2-4. N までの 排他的論理和 の 合計 を, 各桁ごとに取得.
    LL nXor[d];
    for(LL i = 0; i < d; i++) nXor[i] = 0;
    for(LL j = 0; j < d; j++) for(LL i = 0; i < d; i++) nXor[j] += nXorStock[i][j];
    // for(LL i = 0; i < d; i++) cout << nXor[i] << " ";
    
    // 3. 配列 nXor に, 奇数 が 含まれてなければ, 後手勝利と見る.
    string ans = "X";
    for(LL i = 0; i < d; i++) if(nXor[i] % 2 == 1) ans = "O";
    // ex. N = 9999999999 の場合, 後手勝利らしい.
    // 1410065408 4294967296 4294967296 4631290880 4831838208 4899726336 4966055936 4966835200 
    // 4999610368 4999610368 4999610368 4999610368 4999610368 4999610368 4999865344 4999872512 
    // 4999996416 4999996416 4999996416 4999996416 4999996416 4999999488 4999999488 4999999488 
    // 5000000000 5000000000 5000000000 5000000000 5000000000 5000000000 5000000000 5000000000 
    // 5000000000 5000000000
    
    // 4. 後処理.
    cout << ans << endl;
    return 0;
    
}
0