結果

問題 No.102 トランプを奪え
ユーザー gew1fw
提出日時 2025-06-12 13:50:17
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 4,003 ms / 5,000 ms
コード長 3,701 bytes
コンパイル時間 173 ms
コンパイル使用メモリ 82,756 KB
実行使用メモリ 276,380 KB
最終ジャッジ日時 2025-06-12 13:51:04
合計ジャッジ時間 11,254 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from functools import lru_cache

def main():
    sys.setrecursionlimit(1 << 25)
    N = list(map(int, sys.stdin.readline().split()))
    N = tuple(N)
    
    @lru_cache(maxsize=None)
    def dfs(piles, taro, jiro, is_taro_turn):
        piles = list(piles)
        # Check if all piles are empty
        if sum(piles) == 0:
            if taro > jiro:
                return 1  # Taro wins
            elif taro < jiro:
                return -1 # Jiro wins
            else:
                return 0  # Draw
        
        best = None
        for i in range(4):
            if piles[i] == 0:
                continue
            for take in [1, 2, 3]:
                if take > piles[i]:
                    continue
                new_piles = piles.copy()
                new_piles[i] -= take
                new_piles_tuple = tuple(new_piles)
                if is_taro_turn:
                    new_taro = taro + take
                    new_jiro = jiro
                    if new_piles[i] == 0:
                        stolen = (new_jiro) // 2 + (new_jiro % 2)
                        new_taro += stolen
                        new_jiro -= stolen
                        if new_jiro < 0:
                            new_jiro = 0
                    outcome = dfs(new_piles_tuple, new_taro, new_jiro, False)
                    if outcome == 1:
                        return 1
                else:
                    new_taro = taro
                    new_jiro = jiro + take
                    if new_piles[i] == 0:
                        stolen = (new_taro) // 2 + (new_taro % 2)
                        new_jiro += stolen
                        new_taro -= stolen
                        if new_taro < 0:
                            new_taro = 0
                    outcome = dfs(new_piles_tuple, new_taro, new_jiro, True)
                    if outcome == -1:
                        return -1
        
        # After checking all possible moves
        results = []
        for i in range(4):
            if piles[i] == 0:
                continue
            for take in [1, 2, 3]:
                if take > piles[i]:
                    continue
                new_piles = piles.copy()
                new_piles[i] -= take
                new_piles_tuple = tuple(new_piles)
                if is_taro_turn:
                    new_taro = taro + take
                    new_jiro = jiro
                    if new_piles[i] == 0:
                        stolen = (new_jiro) // 2 + (new_jiro % 2)
                        new_taro += stolen
                        new_jiro -= stolen
                        if new_jiro < 0:
                            new_jiro = 0
                else:
                    new_taro = taro
                    new_jiro = jiro + take
                    if new_piles[i] == 0:
                        stolen = (new_taro) // 2 + (new_taro % 2)
                        new_jiro += stolen
                        new_taro -= stolen
                        if new_taro < 0:
                            new_taro = 0
                outcome = dfs(new_piles_tuple, new_taro, new_jiro, not is_taro_turn)
                results.append(outcome)
        
        if is_taro_turn:
            if 1 in results:
                return 1
            if 0 in results:
                return 0
            return -1
        else:
            if -1 in results:
                return -1
            if 0 in results:
                return 0
            return 1
    
    result = dfs(N, 0, 0, True)
    if result == 1:
        print("Taro")
    elif result == -1:
        print("Jiro")
    else:
        print("Draw")

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