結果

問題 No.102 トランプを奪え
ユーザー lam6er
提出日時 2025-04-15 21:39:25
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,043 bytes
コンパイル時間 404 ms
コンパイル使用メモリ 82,508 KB
実行使用メモリ 153,404 KB
最終ジャッジ日時 2025-04-15 21:41:38
合計ジャッジ時間 13,074 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 6 TLE * 1 -- * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from functools import lru_cache

sys.setrecursionlimit(1 << 25)

def main():
    n1, n2, n3, n4 = map(int, sys.stdin.readline().split())
    initial_total = n1 + n2 + n3 + n4
    piles = (n1, n2, n3, n4)

    @lru_cache(maxsize=None)
    def dfs(current_piles, taro_hand, is_taro_turn):
        sum_piles = sum(current_piles)
        if sum_piles == 0:
            jiro_hand = initial_total - taro_hand
            if taro_hand > jiro_hand:
                return 'Taro'
            elif taro_hand < jiro_hand:
                return 'Jiro'
            else:
                return 'Draw'

        possible_results = []
        for i in range(4):
            pile = current_piles[i]
            if pile == 0:
                continue
            for take in range(1, min(3, pile) + 1):
                new_pile = list(current_piles)
                new_pile[i] -= take
                new_pile_tuple = tuple(new_pile)
                new_sum_piles = sum(new_pile_tuple)
                sum_so_far = initial_total - sum_piles
                jiro_hand = sum_so_far - taro_hand

                if new_pile[i] == 0:
                    if is_taro_turn:
                        stolen = (jiro_hand + 1) // 2
                        new_t = taro_hand + take + stolen
                    else:
                        stolen = (taro_hand + 1) // 2
                        new_t = taro_hand - stolen
                        new_t += 0  # Jiro's take adds to his hand, not Taro's
                        new_t = max(new_t, 0)
                else:
                    if is_taro_turn:
                        new_t = taro_hand + take
                    else:
                        new_t = taro_hand

                if new_pile[i] == 0 and is_taro_turn:
                    new_t = taro_hand + take + ((jiro_hand + 1) // 2)
                elif new_pile[i] == 0 and not is_taro_turn:
                    stolen = (taro_hand + 1) // 2
                    new_j_hand = (sum_so_far - taro_hand) + take + stolen
                    new_t = taro_hand - stolen
                    new_t = max(new_t, 0)
                else:
                    if not is_taro_turn:
                        new_j_hand = (sum_so_far - taro_hand) + take
                        new_t = taro_hand
                    else:
                        new_j_hand = sum_so_far - taro_hand

                next_turn = not is_taro_turn
                result = dfs(new_pile_tuple, new_t, next_turn)
                possible_results.append(result)

        if is_taro_turn:
            if 'Taro' in possible_results:
                return 'Taro'
            elif 'Draw' in possible_results:
                return 'Draw'
            else:
                return 'Jiro'
        else:
            if 'Jiro' in possible_results:
                return 'Jiro'
            elif 'Draw' in possible_results:
                return 'Draw'
            else:
                return 'Taro'

    result = dfs(piles, 0, True)
    print(result)

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