結果

問題 No.3112 Decrement or Mod Game
ユーザー aaaaaaaaaaa
提出日時 2025-04-19 12:26:15
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 4,198 bytes
コンパイル時間 1,470 ms
コンパイル使用メモリ 90,172 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-04-19 12:26:19
合計ジャッジ時間 3,572 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 60 WA * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <utility> // for pair
#include <functional> // for hash

using namespace std;

// Custom hash for pair<long long, long long> for unordered_map
struct pair_hash {
    template <class T1, class T2>
    std::size_t operator () (const std::pair<T1,T2> &p) const {
        auto h1 = std::hash<T1>{}(p.first);
        auto h2 = std::hash<T2>{}(p.second);
        // A common way to combine hashes, inspired by boost::hash_combine
        // Use different multipliers for better distribution
        return h1 ^ (h2 + 0x9e3779b97f4a7c15LL + (h1 << 12) + (h1 >> 4));
    }
};

// Use unordered_map for memoization with the custom hash
unordered_map<pair<long long, long long>, bool, pair_hash> memo;

// can_win(my, opp): Can the player whose turn it is, starting with numbers (my, opp), force a win?
// Returns true if the current player wins, false otherwise.
bool can_win(long long my, long long opp) {
    // Base case 1: If my number is 0, I cannot make a move to win. This state implies I lost on a previous turn.
    if (my == 0) return false;

    // Base case 2: If opponent's number is 0, I won on my previous turn.
    if (opp == 0) return true;

    // Immediate Win: Check if I can make my number 0 this turn.
    // If my number is a multiple of opponent's number (and my >= opp), using the remainder operation makes my number 0.
    if (my >= opp && my % opp == 0) {
         return memo[{my, opp}] = true;
    }
    // If my number is 1, I can subtract 1 to make it 0.
    if (my == 1) {
        return memo[{my, opp}] = true;
    }

    // Check memoization to avoid recomputing states.
    if (memo.count({my, opp})) {
        return memo[{my, opp}];
    }

    // Optimization: If my < opp, the only move is Subtract.
    // As derived through analyzing the state transitions (my, opp) -> (opp, my-1) -> (my-1, opp-1) -> ...
    // for my < opp, the current player will eventually face a losing state (like (1, X) with X > 1) if the opponent plays optimally.
    // Thus, if my < opp, the current player loses.
    if (my < opp) {
         return memo[{my, opp}] = false;
    }

    // Evaluate possible moves for the current player (my >= opp and my % opp != 0 handled by immediate win)

    long long q = my / opp; // Quotient
    long long r = my % opp; // Remainder (r > 0 because my % opp != 0)

    bool res; // Result for the current state (my, opp)

    if (q >= 2) {
        // Apply the hypothesis for state space reduction, common in Euclidean-like games:
        // If the Remainder move is winning (!can_win(opp, r)), I win.
        // If the Remainder move is losing (can_win(opp, r)), I can still win via Subtract if q is odd.
        // This simplifies to: (!can_win(opp, r)) || (q % 2 == 1)
        // This avoids the potentially deep recursion of the Subtract move when q is large.
        res = !can_win(opp, r) || (q % 2 == 1);
    } else { // q == 1 (opp <= my < 2*opp and my % opp != 0)
        // In this range, both Remainder and Subtract are important strategic options.
        // The current player wins if either move leads to a state where the opponent loses.

        // Option 1: Remainder move leads to opponent facing (opp, r). Win if !can_win(opp, r).
        bool can_win_by_remainder = !can_win(opp, r);

        // Option 2: Subtract move leads to opponent facing (opp, my - 1). Win if !can_win(opp, my - 1).
        // This recursive call is the primary suspect for TLE if other optimizations are correct.
        bool can_win_by_subtract = !can_win(opp, my - 1);

        res = can_win_by_remainder || can_win_by_subtract;
    }

    // Store the computed result in the memoization table for the current state (my, opp)
    return memo[{my, opp}] = res;
}

int main() {
    // Optimize input/output operations
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

    // Alice starts the game with numbers A and B.
    // Call can_win with Alice's number as 'my' and Bob's number as 'opp'.
    if (can_win(A, B)) {
        cout << "Alice" << endl;
    } else {
        cout << "Bob" << endl;
    }

    return 0;
}
0