結果

問題 No.102 トランプを奪え
ユーザー gew1fw
提出日時 2025-06-12 13:49:42
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,654 bytes
コンパイル時間 193 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 150,952 KB
最終ジャッジ日時 2025-06-12 13:50:05
合計ジャッジ時間 11,901 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 6 TLE * 1 -- * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

from functools import lru_cache

def main():
    import sys
    N = list(map(int, sys.stdin.readline().split()))
    S = sum(N)
    N_tuple = tuple(N)

    @lru_cache(maxsize=None)
    def play(piles, taro_hand, turn):
        sum_piles = sum(piles)
        jiro_hand = S - taro_hand - sum_piles

        if sum_piles == 0:
            if taro_hand > jiro_hand:
                return 1  # Taro wins
            elif taro_hand < jiro_hand:
                return -1  # Jiro wins
            else:
                return 0  # Draw

        if turn:
            # Taro's turn; he wants to maximize the outcome
            max_score = -2  # worst case
            for i in range(4):
                for k in range(1, 4):
                    if piles[i] >= k:
                        new_piles = list(piles)
                        new_piles[i] -= k
                        new_piles = tuple(new_piles)
                        new_taro = taro_hand + k
                        new_jiro = jiro_hand

                        # Check if this move empties the pile
                        if new_piles[i] == 0:
                            stolen = (new_jiro + 1) // 2
                            new_taro += stolen
                            new_jiro -= stolen

                        # Recurse
                        score = play(new_piles, new_taro, False)
                        if score > max_score:
                            max_score = score
            return max_score if max_score != -2 else 0
        else:
            # Jiro's turn; he wants to minimize the outcome
            min_score = 2  # worst case
            for i in range(4):
                for k in range(1, 4):
                    if piles[i] >= k:
                        new_piles = list(piles)
                        new_piles[i] -= k
                        new_piles = tuple(new_piles)
                        new_jiro = jiro_hand + k
                        new_taro = taro_hand

                        # Check if this move empties the pile
                        if new_piles[i] == 0:
                            stolen = (new_taro + 1) // 2
                            new_jiro += stolen
                            new_taro -= stolen

                        # Recurse
                        score = play(new_piles, new_taro, True)
                        if score < min_score:
                            min_score = score
            return min_score if min_score != 2 else 0

    result = play(N_tuple, 0, True)
    if result > 0:
        print("Taro")
    elif result < 0:
        print("Jiro")
    else:
        print("Draw")

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