結果

問題 No.3112 Decrement or Mod Game
ユーザー aaaaaaaaaaa
提出日時 2025-04-19 12:13:29
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 4,371 bytes
コンパイル時間 1,076 ms
コンパイル使用メモリ 89,892 KB
実行使用メモリ 151,740 KB
最終ジャッジ日時 2025-04-19 12:13:37
合計ジャッジ時間 7,879 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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, inspired by boost::hash_combine
        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 & 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 true;
    // If my number is 1, I can subtract 1 to make it 0.
    if (my == 1) return 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)

    // Evaluate possible moves for the current player

    // Case 1: my < opp
    if (my < opp) {
        // If my number is less than opponent's, only Operation 1 (Subtract) is possible.
        // I subtract 1, state becomes (opp, my-1). I win if the opponent loses from this new state.
        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: Use Remainder operation. New state for opponent: (opp, r).
        // I win by this move if the opponent loses from (opp, r).
        bool can_win_by_remainder = !can_win(opp, r);

        // Option 2: Use Subtract operation. New state for opponent: (opp, my-1).
        // I win by this move if the opponent loses from this new state.
        // Apply the state space reduction based on q >= 2.
        if (q >= 2) {
            // Based on game properties, when my is significantly larger than opp (q >= 2)
            // and Remainder operation is not an immediate win (my % opp != 0),
            // the outcome often depends on the Remainder outcome and the parity of q.
            // If Remainder is winning (!can_win(opp, r)), I win.
            // If Remainder 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)
            res = can_win_by_remainder || (q % 2 == 1);
        } else { // q == 1 (opp <= my < 2*opp and my % opp != 0)
            // Both Remainder and Subtract are important strategic options in this range.
            // The current player wins if either move leads to a state where the opponent loses.

            // If winning by Remainder is possible, take it.
            if (can_win_by_remainder) {
                res = true;
            } else {
                 // If Remainder is not a winning move, check if Subtract is a winning move.
                 // The Subtract path !can_win(opp, my - 1) is likely the primary source of TLE
                 // if the previous optimization didn't cover all necessary cases.
                 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