結果

問題 No.3112 Decrement or Mod Game
コンテスト
ユーザー Rira
提出日時 2025-04-20 14:49:40
言語 C++17
(gcc 15.2.0 + boost 1.90.0)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
MLE  
実行時間 -
コード長 725 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 495 ms
コンパイル使用メモリ 105,252 KB
実行使用メモリ 1,298,856 KB
最終ジャッジ日時 2026-07-10 02:21:16
合計ジャッジ時間 4,191 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other MLE * 2 -- * 63
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <unordered_map>
using namespace std;

unordered_map<long long, unordered_map<long long, string>> dp;

string winner(long long a, long long b) {
    if (a == 0) return "Bob";
    if (b == 0) return "Alice";

    if (dp[a][b] != "") return dp[a][b];

    // 操作1: a を 1 減らす
    if (winner(a - 1, b) == "Bob") {
        dp[a][b] = "Alice";
        return "Alice";
    }

    // 操作2: a を b で割ったあまりに置き換える
    if (a >= b && winner(a % b, b) == "Bob") {
        dp[a][b] = "Alice";
        return "Alice";
    }

    dp[a][b] = "Bob";
    return "Bob";
}

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

    cout << winner(A, B) << endl;

    return 0;
}
0