結果

問題 No.102 トランプを奪え
ユーザー gew1fw
提出日時 2025-06-12 13:55:26
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 775 ms / 5,000 ms
コード長 1,874 bytes
コンパイル時間 584 ms
コンパイル使用メモリ 82,120 KB
実行使用メモリ 118,236 KB
最終ジャッジ日時 2025-06-12 13:56:39
合計ジャッジ時間 4,154 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from functools import lru_cache

def main():
    N = list(map(int, sys.stdin.readline().split()))
    N_sorted = tuple(sorted(N))
    
    @lru_cache(maxsize=None)
    def dfs(heaps, taro, jiro, is_taro_turn):
        if all(h == 0 for h in heaps):
            return taro - jiro
        
        best_diff = -float('inf') if is_taro_turn else float('inf')
        prev_h = None
        for i in range(len(heaps)):
            h = heaps[i]
            if h == 0:
                continue
            if h == prev_h:
                continue
            prev_h = h
            for take in range(1, min(3, h) + 1):
                new_h = h - take
                new_heaps = list(heaps)
                new_heaps[i] = new_h
                new_heaps_sorted = tuple(sorted(new_heaps))
                if is_taro_turn:
                    new_t = taro + take
                    new_j = jiro
                else:
                    new_t = taro
                    new_j = jiro + take
                if new_h == 0:
                    if is_taro_turn:
                        steal = (new_j + 1) // 2
                        new_t += steal
                        new_j -= steal
                    else:
                        steal = (new_t + 1) // 2
                        new_j += steal
                        new_t -= steal
                diff = dfs(new_heaps_sorted, new_t, new_j, not is_taro_turn)
                if is_taro_turn:
                    if diff > best_diff:
                        best_diff = diff
                else:
                    if diff < best_diff:
                        best_diff = diff
        return best_diff
    
    total_diff = dfs(N_sorted, 0, 0, True)
    if total_diff > 0:
        print("Taro")
    elif total_diff < 0:
        print("Jiro")
    else:
        print("Draw")

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