#1076608 (C++17) No.3112 Decrement or Mod Game

• 問題: No.3112 Decrement or Mod Game
• ユーザー: aaaaaaaaaaa
• 提出日時: 2025-04-19 10:47:59
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: MLE
• 実行時間: -
• コード長: 7,305 bytes
• コンパイル時間: 1,169 ms
• コンパイル使用メモリ: 82,708 KB
• 実行使用メモリ: 814,336 KB
• 最終ジャッジ日時: 2025-04-19 10:48:05
• 合計ジャッジ時間: 5,290 ms
• ジャッジサーバーID （参考情報）: judge3 / judge1

ファイルパターン	結果
sample	-- * 3
other	MLE * 1 -- * 64

ソースコード

#include <iostream>
#include <string>
#include <map>
#include <tuple>
#include <algorithm>

using namespace std;

// Using map for memoization: key is tuple<Alice's number, Bob's number, is_Alice's_turn>
map<tuple<long long, long long, bool>, bool> memo;

// Function to determine if the current player can win from state (a, b)
// a: Alice's number, b: Bob's number, is_alice_turn: true if Alice's turn, false if Bob's
// Returns: true if current player wins, false otherwise
bool solve(long long a, long long b, bool is_alice_turn) {
    // Base case: If either number is 0, the player whose turn it is *now* did not make it 0.
    // The player who made it 0 in the previous turn won. So the current player loses.
    if (a == 0 || b == 0) {
        return false;
    }

    // Check if this state has been computed before
    tuple<long long, long long, bool> current_state = {a, b, is_alice_turn};
    if (memo.count(current_state)) {
        return memo[current_state];
    }

    bool can_win; // Whether the current player can win from this state

    if (is_alice_turn) {
        // Alice's turn, she has 'a', Bob has 'b'.

        // Option 1: Subtract 1 from Alice's number. New state (a-1, b), Bob's turn.
        // Alice wins by subtract if Bob loses from (a-1, b).
        bool can_win_sub = !solve(a - 1, b, false);

        // Option 2: Modulo (only if a >= b). New state (a % b, b), Bob's turn.
        // Alice wins by modulo if a % b == 0 (immediate win), or if Bob loses from (a%b, b) (if a%b > 0).
        bool can_win_mod = false; // Default: cannot win by modulo (either not possible or leads to loss)
        bool modulo_possible = (a >= b);

        if (modulo_possible) {
             if (b == 1) { // If Bob's number is 1, Alice can do a % 1 = 0
                can_win_mod = true;
            } else if (a % b == 0) { // Modulo results in 0
                can_win_mod = true;
            } else { // Modulo results in non-zero (a%b > 0)
                 // Optimization: If Alice's number (a) is much larger than Bob's (b),
                 // specifically a >= 2*b, and the modulo move (a%b, b) leads to Bob winning,
                 // the outcome depends on the parity of the quotient a/b.
                 if (a >= 2 * b) {
                    // Alice wins if Bob loses from (a%b, b) OR (Bob wins from (a%b, b) AND (a/b) is even)
                    // Simplified: Alice wins if (!solve(a%b, b, false)) || ((a / b) % 2 == 0)
                    can_win = (!solve(a % b, b, false)) || ((a / b) % 2 == 0);

                    // If the optimization was applied, the outcome is determined.
                    // Do NOT memoize this specific result as it relies on quotient parity which isn't in the key.
                    return can_win; // Directly return the optimized result
                 } else { // a >= b but a < 2*b (Ratio is 1) - no optimization, check modulo path recursively
                     can_win_mod = !solve(a % b, b, false); // Alice wins by modulo if Bob loses from (a%b, b)
                 }
            }
        }

        // Combine possible winning moves (modulo and subtract)
        // If modulo was not possible, or no immediate win by modulo, check if either move is winning.
        if (!modulo_possible || (!can_win_mod && modulo_possible && a % b != 0 && a < 2*b) || (!modulo_possible && a < b)) {
             // If modulo was not possible, or we are in the a < 2*b non-zero remainder case, check both.
             // If modulo gave immediate win (b=1 or a%b=0), can_win_mod is true.
             // If a >= 2b and optimization applied, we already returned.
             if (modulo_possible && (b == 1 || a % b == 0)) {
                  can_win = true; // Immediate win by modulo
             } else if (modulo_possible && a >= b && a < 2*b && a%b != 0) {
                  can_win = can_win_mod || can_win_sub; // Check both modulo path outcome and subtract path outcome
             } else if (a < b) { // Only subtract possible
                  can_win = can_win_sub;
             } else { // Should not reach here if logic is correct
                 // This case covers a >= b, b > 1, a%b != 0, a >= 2b - handled by direct return above
                 // or a >= b, b > 1, a%b == 0 - handled by immediate win above
                 // or a >= b, b == 1 - handled by immediate win above
                 // or a >= b, a < 2b, b > 1, a%b != 0 - handled by (modulo_possible && a >= b && a < 2*b && a%b != 0)
                 // or a < b - handled by (a < b)
                 // It seems the logic branches above cover all cases correctly.
                 // This final 'else' should ideally not be needed if all branches are exhaustive.
                 // Let's re-structure slightly to be clearer.
             }

        } else {
             // This means modulo was possible and led to an immediate win (b=1 or a%b=0), or we are in the a >= 2b optimized case.
             // If modulo was an immediate win, can_win_mod is true, and can_win is true.
             // If a >= 2b optimization applied, we already determined can_win and returned.
             // This else block seems redundant with the structure above.
        }
        // Let's simplify the structure based on the main conditions: a<b, a>=b && a<2b, a>=b && a>=2b.
        if (a < b) {
            can_win = !solve(a - 1, b, false);
        } else { // a >= b
             if (b == 1 || a % b == 0) {
                can_win = true; // Immediate win by modulo
            } else if (a < 2 * b) { // a >= b, b > 1, a%b != 0, a < 2b
                 can_win = !solve(a % b, b, false) || !solve(a - 1, b, false);
            } else { // a >= 2*b, b > 1, a%b != 0
                 // Apply optimization
                 can_win = (!solve(a % b, b, false)) || ((a / b) % 2 == 0);
                 // Do NOT memoize this specific result
                 memo[current_state] = can_win; // Still memoize this state's outcome *after* calculation
                 return can_win; // Directly return the optimized result
            }
        }


    } else { // Bob's turn, he has 'b', opponent Alice has 'a'. Symmetric logic.
        if (b < a) {
            can_win = !solve(a, b - 1, true);
        } else { // b >= a
             if (a == 1 || b % a == 0) {
                can_win = true; // Immediate win by modulo
            } else if (b < 2 * a) { // b >= a, a > 1, b%a != 0, b < 2a
                 can_win = !solve(a, b % a, true) || !solve(a, b - 1, true);
            } else { // b >= 2*a, a > 1, b%a != 0
                 // Apply optimization
                 can_win = (!solve(a, b % a, true)) || ((b / a) % 2 == 0);
                 // Do NOT memoize this specific result
                 memo[current_state] = can_win; // Still memoize this state's outcome *after* calculation
                 return can_win; // Directly return the optimized result
            }
        }
    }

    // Memoize if the optimized rule was NOT applied in this call
    memo[current_state] = can_win;

    return can_win;
}

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

    long long A, B;
    cin >> A >> B;

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

    return 0;
}