結果

問題 No.524 コインゲーム
コンテスト
ユーザー @abcde
提出日時 2019-03-10 16:04:26
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 1,000 ms
コード長 3,624 bytes
コンパイル時間 1,424 ms
コンパイル使用メモリ 163,148 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-23 15:18:36
合計ジャッジ時間 2,374 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

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';
            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";
    
    // 4. 後処理.
    cout << ans << endl;
    return 0;
    
}
0