結果
問題 | No.102 トランプを奪え |
ユーザー | rpy3cpp |
提出日時 | 2015-07-18 00:23:19 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
AC
|
実行時間 | 145 ms / 5,000 ms |
コード長 | 1,821 bytes |
コンパイル時間 | 102 ms |
コンパイル使用メモリ | 10,968 KB |
実行使用メモリ | 27,880 KB |
最終ジャッジ日時 | 2023-09-22 18:39:39 |
合計ジャッジ時間 | 1,275 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 17 ms
8,112 KB |
testcase_01 | AC | 15 ms
8,168 KB |
testcase_02 | AC | 21 ms
8,808 KB |
testcase_03 | AC | 16 ms
8,180 KB |
testcase_04 | AC | 16 ms
8,180 KB |
testcase_05 | AC | 36 ms
10,196 KB |
testcase_06 | AC | 36 ms
9,944 KB |
testcase_07 | AC | 21 ms
8,828 KB |
testcase_08 | AC | 41 ms
10,460 KB |
testcase_09 | AC | 145 ms
27,880 KB |
testcase_10 | AC | 132 ms
25,780 KB |
ソースコード
def solve(N1, N2, N3, N4): global dp Ns = [N1, N2, N3, N4] Ntotal = sum(Ns) Ns.sort(reverse = True) dp = [[[[[-2] * (Ntotal + 1) for n3 in range(Ns[3]+1)] for n2 in range(Ns[2]+1)] for n1 in range(Ns[1]+1)] for n0 in range(Ns[0]+1)] for n_player in range(Ntotal + 1): if n_player > Ntotal - n_player: dp[0][0][0][0][n_player] = 1 elif n_player == Ntotal - n_player: dp[0][0][0][0][n_player] = 0 else: dp[0][0][0][0][n_player] = -1 return win(0, 0, Ns) dp = [] def win(n_player, n_opponent, ns): '''手番のもちカード数がn_player, 相手のもちカード数がn_opponent 山のカードの枚数が n0, n1, n2, n3 であるときに、 自分が勝つならば 1 相手が勝つならば -1 引き分けならば 0 を返す。 ''' global dp ns.sort(reverse=True) n0, n1, n2, n3 = ns if dp[n0][n1][n2][n3][n_player] != -2: return dp[n0][n1][n2][n3][n_player] record = -1 for idx in range(4): for dn in range(1, 4): ns_copy = ns[:] ns_copy[idx] -= dn if ns_copy[idx] > 0: result = win(n_opponent, n_player + dn, ns_copy) elif ns_copy[idx] == 0: result = win(n_opponent//2, n_player + dn + (n_opponent + 1)//2, ns_copy) else: break if result == -1: dp[n0][n1][n2][n3][n_player] = 1 return 1 if result == 0 and record == -1: record = 0 dp[n0][n1][n2][n3][n_player] = record return record N1, N2, N3, N4 = map(int, input().split()) winner = solve(N1, N2, N3, N4) if winner == 1: print('Taro') elif winner == -1: print('Jiro') else: print('Draw')