結果

問題 No.3112 Decrement or Mod Game
コンテスト
ユーザー Mistletoe
提出日時 2025-04-19 00:54:52
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
RE  
実行時間 -
コード長 2,366 bytes
コンパイル時間 409 ms
コンパイル使用メモリ 12,032 KB
実行使用メモリ 11,264 KB
最終ジャッジ日時 2025-04-19 00:54:57
合計ジャッジ時間 5,099 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 3
other RE * 65
権限があれば一括ダウンロードができます

ソースコード

diff # 

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**7)

def exact_dp_winner(A, B):
    # dp[a][b] = True if the position (a,b) with Alice to move is winning for Alice
    dp = [[False]*(B+1) for _ in range(A+1)]
    # Base cases:
    # If Alice already has 0, she can't move and thus loses (dp[0][b]=False).
    # If Bob has 0 (i.e. b=0) and it's Alice's turn, then Alice wins immediately (dp[a][0]=True for a>0).
    for a in range(1, A+1):
        dp[a][0] = True
    # dp[0][*] already False by initialization

    for a in range(1, A+1):
        for b in range(1, B+1):
            win = False
            # 1) subtract 1
            if a-1 == 0:
                win = True
            elif not dp[a-1][b]:
                win = True
            # 2) divide by b, if possible
            if not win and b <= a:
                a2 = a // b
                if a2 == 0:
                    win = True
                elif not dp[a2][b]:
                    win = True
            dp[a][b] = win

    return dp[A][B]

def greedy_winner(A, B):
    a, b = A, B
    alice_turn = True
    while True:
        if alice_turn:
            # Alice's move on 'a'
            # how much does each option reduce?
            sub = a - 1
            if b > 1 and b <= a:
                div = a // b
            else:
                div = a  # treat dividing by 1 or invalid as no reduction
            # pick the one that yields the smaller new a
            if div < sub:
                a = div
            else:
                a = sub
            if a == 0:
                return True
        else:
            # Bob's move on 'b'
            sub = b - 1
            if a > 1 and a <= b:
                div = b // a
            else:
                div = b
            if div < sub:
                b = div
            else:
                b = sub
            if b == 0:
                return False
        alice_turn = not alice_turn

def main():
    A = int(sys.stdin.readline())
    B = int(sys.stdin.readline())

    # If both are small enough, do exact DP in O(A*B)
    if A <= 2000 and B <= 2000:
        alice_wins = exact_dp_winner(A, B)
    else:
        # otherwise, fall back to a fast greedy simulation (O(log max) steps)
        alice_wins = greedy_winner(A, B)

    print("Alice" if alice_wins else "Bob")

if __name__ == "__main__":
    main()
0