結果

問題 No.3112 Decrement or Mod Game
ユーザー aaaaaaaaaaa
提出日時 2025-04-19 00:56:40
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 3,081 bytes
コンパイル時間 944 ms
コンパイル使用メモリ 81,916 KB
実行使用メモリ 814,464 KB
最終ジャッジ日時 2025-04-19 00:56:46
合計ジャッジ時間 5,566 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other MLE * 1 -- * 64
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <utility>

using namespace std;

typedef long long ll;

// memo[0] for Alice's turn, memo[1] for Bob's turn
// value is 1 if the player whose turn it is wins, 0 otherwise.
map<pair<ll, ll>, int> memo[2];

// Returns 1 if the current player (with my_num) wins against opponent (with opp_num), 0 otherwise.
// Assumes my_num > 0 and opp_num > 0 when called initially.
int solve(ll my_num, ll opp_num, bool is_my_turn) {
    // If we reach a state where memo already has the answer, return it.
    pair<ll, ll> state = {my_num, opp_num};
    int player_idx = is_my_turn ? 0 : 1;
    if (memo[player_idx].count(state)) {
        return memo[player_idx][state];
    }

    // Check immediate win conditions for the current player: make my_num = 0
    // Move 1: Decrease my_num by 1
    if (my_num == 1) { // my_num - 1 becomes 0
        return memo[player_idx][state] = 1; // Current player wins
    }
    // Move 2: Modulo my_num by opp_num (if possible)
    if (opp_num <= my_num && my_num % opp_num == 0) { // my_num % opp_num becomes 0
         return memo[player_idx][state] = 1; // Current player wins
    }

    // If no immediate win, explore non-winning moves.
    // Current player wins if *any* non-winning move leads to a state where the opponent loses.

    bool can_win = false;

    // Option 1: Decrease my_num by 1 (results in my_num - 1 > 0)
    // New state for opponent: opponent has opp_num, I have my_num - 1. State (opp_num, my_num - 1) for opponent's turn.
    // Current player wins if solve(opp_num, my_num - 1, !is_my_turn) returns 0 (opponent loses).
    if (my_num > 1) { // Only consider this move if my_num - 1 > 0 (my_num == 1 is immediate win)
        if (solve(opp_num, my_num - 1, !is_my_turn) == 0) {
            can_win = true;
        }
    }

    // If already found a winning move, no need to check others
    if (can_win) {
         return memo[player_idx][state] = 1;
    }

    // Option 2: Modulo my_num by opp_num (if possible and non-zero). The resulting number my_num' = my_num % opp_num.
    // New state for opponent: opponent has opp_num, I have my_num % opp_num. State (opp_num, my_num % opp_num) for opponent's turn.
    // Current player wins if solve(opp_num, my_num % opp_num, !is_my_turn) returns 0 (opponent loses).
    if (opp_num <= my_num) { // Modulo is possible
        if (my_num % opp_num != 0) { // If not an immediate win by modulo
             if (solve(opp_num, my_num % opp_num, !is_my_turn) == 0) {
                can_win = true;
            }
        }
    }

    // Store and return result
    return memo[player_idx][state] = can_win ? 1 : 0;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll A, B;
    cin >> A >> B;

    // Alice goes first, has A, Bob has B.
    // solve(A, B, true) checks if the player with A (Alice) wins starting the game with numbers (A, B).
    if (solve(A, B, true) == 1) {
        cout << "Alice" << endl;
    } else {
        cout << "Bob" << endl;
    }

    return 0;
}
0