結果

問題 No.3112 Decrement or Mod Game
ユーザー aaaaaaaaaaa
提出日時 2025-04-19 12:55:01
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,918 bytes
コンパイル時間 1,111 ms
コンパイル使用メモリ 90,188 KB
実行使用メモリ 154,216 KB
最終ジャッジ日時 2025-04-19 12:55:09
合計ジャッジ時間 7,580 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other TLE * 1 -- * 64
権限があれば一括ダウンロードができます

ソースコード

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, use a large prime number for better distribution
        return h1 ^ (h2 + 0x9e3779b9 + (h1 << 6) + (h1 >> 2));
    }
};

// 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}];
    }

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

    // Case 1: my < opp
    if (my < opp) {
        // Only Operation 1 (Subtract) is possible.
        // I subtract 1, state becomes (opp, my-1). I win if the opponent loses from this new state.
        // REMOVED: Simple return false here was likely wrong.
        res = !can_win(opp, my - 1);
    } else { // my >= opp and my % opp != 0 (Immediate win handled above)
        long long q = my / opp; // Quotient
        long long r = my % opp; // Remainder (r > 0 because my % opp != 0)

        // 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);

        if (can_win_by_remainder) {
            // If Remainder is a winning move, take it.
            res = true;
        } else {
            // If Remainder is not a winning move, consider the Subtract move.
            // Apply the state space reduction based on q >= 2 for the Subtract path evaluation.
            if (q >= 2) {
                // When Remainder is not winning, and my is significantly larger than opp (q >= 2),
                // the outcome via Subtract seems to depend on the parity of q.
                // If Remainder is losing, the current player wins via Subtract iff q is odd.
                res = (q % 2 == 1);
            } else { // q == 1 (opp <= my < 2*opp and my % opp != 0)
                // In this range, Remainder is not winning, so check if Subtract is a winning move.
                // Subtract leads to opponent facing (opp, my - 1). Win if !can_win(opp, my - 1).
                res = !can_win(opp, my - 1);
            }
        }
    }

    // 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