結果

問題 No.3112 Decrement or Mod Game
コンテスト
ユーザー Rira
提出日時 2025-04-19 19:47:38
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
MLE  
実行時間 -
コード長 1,783 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 616 ms
コンパイル使用メモリ 83,788 KB
実行使用メモリ 814,592 KB
最終ジャッジ日時 2025-04-19 19:47:44
合計ジャッジ時間 4,389 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other MLE * 1 -- * 64
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <unordered_map>
#include <tuple>

using namespace std;

// std::tuple<long long, long long> 用のカスタムハッシュ関数
struct tuple_hash {
    template <class T1, class T2>
    std::size_t operator ( )(const std::tuple<T1, T2>& t) const {
        auto h1 = std::hash<T1>{}(std::get<0>(t));
        auto h2 = std::hash<T2>{}(std::get<1>(t));
        return h1 ^ (h2 << 1);  // 2つのハッシュ値を組み合わせる
    }
};

// メモ化用のハッシュマップ
unordered_map<tuple<long long, long long>, bool, tuple_hash> memo;

// 再帰的に勝敗を判定する関数
bool canAliceWin(long long A, long long B) {
    // すでに計算した状態はメモ化された結果を返す
    if (memo.find(make_tuple(A, B)) != memo.end()) {
        return memo[make_tuple(A, B)];
    }
    
    // ゲーム終了条件: どちらかの数が0なら、その時点で勝者が決定
    if (A == 0) {
        return true;   // Aliceの数が0になったのでBobの勝ち
    }
    if (B == 0) {
        return false;  // Bobの数が0になったのでAliceの勝ち
    }

    // Aliceのターン
    // 1. Aliceが自分の数を1減らす
    if (!canAliceWin(A - 1, B)) {
        memo[make_tuple(A, B)] = true;
        return true;
    }

    // 2. Aliceが自分の数をBで割った余りにする（B <= Aの場合のみ）
    if (B <= A && !canAliceWin(A % B, B)) {
        memo[make_tuple(A, B)] = true;
        return true;
    }

    // Bobのターンになってしまう場合
    memo[make_tuple(A, B)] = false;
    return false;
}

int main() {
    long long A, B;
    cin >> A >> B;

    if (canAliceWin(A, B)) {
        cout << "Alice" << endl;
    } else {
        cout << "Bob" << endl;
    }

    return 0;
}
0