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

提出ソース

結果

問題	No.3112 Decrement or Mod Game
コンテスト
ユーザー	aaaaaaaaaaa
提出日時	2025-04-19 01:07:39
言語	C++17 (gcc 13.3.0 + boost 1.89.0)
結果	MLE
実行時間	-
コード長	4,684 bytes
記録記録タグの例: 初AC ショートコード純ショートコード純主流ショートコード最速実行時間
コンパイル時間	813 ms
コンパイル使用メモリ	84,796 KB
実行使用メモリ	814,592 KB
最終ジャッジ日時	2025-04-19 01:07:43
合計ジャッジ時間	3,004 ms
ジャッジサーバーID （参考情報）	judge4 / judge5

このコードへのチャレンジ
（要ログイン）

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

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <iostream> // 用于标准输入输出流
#include <vector>   // 虽然未使用，但通常包含在C++标准库中
#include <numeric>  // 虽然未使用，但包含一些数值算法
#include <map>      // 用于存储记忆化结果 (关键)
#include <utility>  // 用于 std::pair (map的键)
#include <algorithm> // 用于 std::swap (如果需要，但这里未使用)

// 使用 long long 类型处理可能达到 10^18 的大整数
using ll = long long;

// 使用 map 进行记忆化
// 键是游戏状态 (a, b) 对, 值是布尔类型, 表示当前玩家是否能从此状态获胜
// key是(当前玩家的数, 对手的数)
std::map<std::pair<ll, ll>, bool> memo;

// 函数 can_win(a, b): 判断当前轮到的玩家 (持有数字 a, 对手持有数字 b) 是否有必胜策略
bool can_win(ll a, ll b) {
    // 基本情况 1: 如果当前玩家的数字 a <= 0
    // 轮到你时你的数字已经是0或负数（理论上不会负），意味着你在对手的回合后数字变成了0或更少。
    // 根据规则 "先将自己数字变成 0 者获胜"，你已经输了。
    if (a <= 0) {
        return false; // 输了
    }
    // 基本情况 2: 如果对手的数字 b <= 0
    // 这意味着对手在他/她的上一个回合使得 b 变成了 0 或更少。
    // 对手获胜了。所以当前玩家面临 (a, b<=0) 这个状态时，实际上已经输了。
    if (b <= 0) {
        return false; // 输了
    }

    // 检查记忆化表: 如果状态 (a, b) 已经计算过, 直接返回存储的结果
    std::pair<ll, ll> state = {a, b};
    if (memo.count(state)) {
        return memo[state];
    }

    // 优化: 如果 a >= 2 * b, 那么当前玩家总能获胜. (这里需要 b > 0, 前面的检查已保证)
    // 这个优化是解决内存和时间限制的关键。它基于对这类博弈（类似欧几里得博弈）的分析，
    // 即使规则略有不同（多了减1操作），这个条件通常能保证存在获胜策略。
    // 我们接受这个常见的优化结论。
    if (a >= 2 * b) {
        // 记录结果并返回 true
        memo[state] = true;
        return true;
    }

    // 递归计算: 当前玩家获胜，当且仅当存在一个操作，使得操作后的状态对于下一个玩家（即当前对手）来说是必败的。
    // 必败状态意味着对手视角的 can_win 调用返回 false。

    // 考虑操作 1: 将自己的数减 1 (a -> a - 1)
    // 操作后, 对手将面临状态 (b, a - 1).
    // 当前玩家获胜，如果对手从 (b, a - 1) 状态出发无法获胜 (即 can_win(b, a - 1) == false).
    // 获胜条件: !can_win(b, a - 1)
    if (!can_win(b, a - 1)) {
        // 找到了一个获胜策略, 记录结果并返回 true
        memo[state] = true;
        return true;
    }

    // 考虑操作 2: 将自己的数替换为 a % b (仅当 a >= b 时可行)
    // 注意: 由于 a >= 2*b 的情况已被上面的优化处理，如果能执行到这里且 a >= b,
    // 那么必然有 b <= a < 2*b.
    if (a >= b) {
        ll remainder = a % b;
        // 操作后, 对手将面临状态 (b, remainder).
        // 当前玩家获胜, 如果对手从 (b, remainder) 状态出发无法获胜 (即 can_win(b, remainder) == false).
        // 获胜条件: !can_win(b, remainder)
        // 特别地, 如果 remainder == 0, 那么对手面临 (b, 0). can_win(b, 0) 返回 false.
        // 此时 !can_win(b, 0) 为 true, 表示当前玩家通过此操作直接获胜，逻辑正确。
        if (!can_win(b, remainder)) {
            // 找到了一个获胜策略, 记录结果并返回 true
            memo[state] = true;
            return true;
        }
    }

    // 如果尝试了所有可能的操作, 都无法保证让对手进入必败状态
    // (即所有操作都导向对手的必胜状态), 那么当前玩家处于必败状态.
    // 记录结果并返回 false
    memo[state] = false;
    return false;
}

int main() {
    // 加速 C++ 标准输入输出流 (在处理大量输入输出时可以提高效率)
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    ll a, b; // 定义长整型变量存储输入的 A 和 B
    std::cin >> a >> b; // 读取输入

    // Alice 是先手, 初始状态是 (A, B). 调用 can_win(a, b) 判断 Alice 是否能赢.
    if (can_win(a, b)) {
        // 如果 can_win(a, b) 返回 true, 说明 Alice 有必胜策略
        std::cout << "Alice" << std::endl;
    } else {
        // 如果 can_win(a, b) 返回 false, 说明 Alice 没有必胜策略, 因此 Bob 获胜
        std::cout << "Bob" << std::endl;
    }

    return 0; // 程序正常结束
}

yukicoder

結果

ソースコード