結果
| 問題 |
No.936 Are
|
| コンテスト | |
| ユーザー |
 mkawa2
|
| 提出日時 | 2019-12-02 17:09:34 |
| 言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 5,815 bytes |
| コンパイル時間 | 148 ms |
| コンパイル使用メモリ | 13,440 KB |
| 実行使用メモリ | 450,768 KB |
| 最終ジャッジ日時 | 2024-11-24 12:12:47 |
| 合計ジャッジ時間 | 58,817 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 3 WA * 8 TLE * 14 |
ソースコード
import sys
sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
n, k = MI()
l1, r1, l2, r2 = MI()
def main():
# 1がIotが負けそう、2どちらも負けそう、3が髙橋が負けそう
lose = [[[[0] * 5 for _ in range(5)] for _ in range(5)] for _ in range(5)]
for il in range(5):
for ir in range(5):
if (il, ir) == (0, 0): continue
for tl in range(5):
for tr in range(5):
if (tl, tr) == (0, 0): continue
i_lose, t_lose = False, False
if tl * tr == 0 and (5 - tl - tr) % 5 in [il, ir]:
t_lose = True
if il * ir == 0 and (5 - il - ir) % 5 in [tl, tr]:
i_lose = True
if i_lose and t_lose:
lose[il][ir][tl][tr] = 2
elif i_lose:
lose[il][ir][tl][tr] = 1
elif t_lose:
lose[il][ir][tl][tr] = 3
# 手がil,ir,tl,trの状態からiターンでIotが勝つ方法を
# dp[i][il][ir][tl][tr]とする
dp = [[[[[0] * 5 for _ in range(5)] for _ in range(5)] for _ in range(5)] for _ in range(k + 1)]
# 初期化
for il in range(5):
for ir in range(5):
if (il, ir) == (0, 0): continue
dp[0][il][ir][0][0] = 1
# もらうdp
for i in range(1, k + 1):
for il in range(5):
for ir in range(5):
if (il, ir) == (0, 0): continue
for tl in range(5):
for tr in range(5):
if (tl, tr) == (0, 0): continue
if i % 2: # Iotのターン
dp_value = 0
# 攻撃
if il > 0 and tl > 0: dp_value += dp[i - 1][il][ir][(tl + il) % 5][tr]
if il > 0 and tr > 0: dp_value += dp[i - 1][il][ir][tl][(tr + il) % 5]
if ir > 0 and tl > 0: dp_value += dp[i - 1][il][ir][(tl + ir) % 5][tr]
if ir > 0 and tr > 0: dp_value += dp[i - 1][il][ir][tl][(tr + ir) % 5]
# 分割（自滅、交換、重複がないように）
ng = set([(0, 0), (il, ir), (ir, il)])
for nl in range(il + ir + 1):
nr = il + ir - nl
nl, nr = nl % 5, nr % 5
if (nl, nr) in ng: continue
ng.add((nl, nr))
dp_value += dp[i - 1][nl][nr][tl][tr]
dp[i][il][ir][tl][tr] = dp_value
else: # 髙橋のターン
# 勝てるときは必ず勝つ
if 0 < lose[il][ir][tl][tr] < 3: continue
dp_value = 0
# 詰んでいるとき負けパターン数とそのフラグ
dp_lose=0
flag_lose=True
# 攻撃
if il > 0 and tl > 0:
nl, nr = (il + tl) % 5, ir
pre=dp[i - 1][nl][nr][tl][tr]
dp_lose+=pre
if lose[nl][nr][tl][tr] < 2:
flag_lose=False
dp_value +=pre
if il > 0 and tr > 0:
nl, nr = (il + tr) % 5, ir
pre=dp[i - 1][nl][nr][tl][tr]
dp_lose+=pre
if lose[nl][nr][tl][tr] < 2:
flag_lose=False
dp_value +=pre
if ir > 0 and tl > 0:
nl, nr = il, (ir + tl) % 5
pre=dp[i - 1][nl][nr][tl][tr]
dp_lose+=pre
if lose[nl][nr][tl][tr] < 2:
flag_lose=False
dp_value +=pre
if ir > 0 and tr > 0:
nl, nr = il, (ir + tr) % 5
pre=dp[i - 1][nl][nr][tl][tr]
dp_lose+=pre
if lose[nl][nr][tl][tr] < 2:
flag_lose=False
dp_value +=pre
# 分割（自滅、交換、重複がないように）
ng = set([(0, 0), (tl, tr), (tr, tl)])
for nl in range(tl + tr + 1):
nr = tl + tr - nl
nl, nr = nl % 5, nr % 5
if (nl, nr) in ng: continue
ng.add((nl, nr))
pre=dp[i - 1][il][ir][nl][nr]
dp_lose+=pre
if lose[il][ir][nl][nr] < 2:
flag_lose=False
dp_value +=pre
dp[i][il][ir][tl][tr] = dp_lose if flag_lose else dp_value
ans = 0
for i in range(n + 1, k + 1, 2):
ans += dp[i][l1][r1][l2][r2]
print(ans)
main()