結果
| 問題 |
No.936 Are
|
| コンテスト | |
| ユーザー |
 mkawa2
|
| 提出日時 | 2019-12-02 18:45:51 |
| 言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,632 bytes |
| コンパイル時間 | 253 ms |
| コンパイル使用メモリ | 13,696 KB |
| 実行使用メモリ | 25,800 KB |
| 最終ジャッジ日時 | 2024-11-24 15:11:13 |
| 合計ジャッジ時間 | 58,805 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 11 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()
md = 10 ** 9 + 7
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
# i=0がItoの番、1が髙橋の番で遷移先のリスト
to = [[[[[[], [], [], [], []] for _ in range(5)] for _ in range(5)] for _ in range(5)] for _ in range(2)]
# 遷移先リストを作る
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のターン
to_value = []
# 攻撃
if il > 0 and tl > 0: to_value.append((il, ir, (tl + il) % 5, tr))
if il > 0 and tr > 0: to_value.append((il, ir, tl, (tr + il) % 5))
if ir > 0 and tl > 0: to_value.append((il, ir, (tl + ir) % 5, tr))
if ir > 0 and tr > 0: to_value.append((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))
to_value.append((nl, nr, tl, tr))
to[0][il][ir][tl][tr] = to_value
else: # 髙橋のターン
# 勝てるときは必ず勝つ
if 0 < lose[il][ir][tl][tr] < 3: continue
to_value = []
# 詰んでいるとき負けパターン数とそのフラグ
to_lose = []
flag_lose = True
# 攻撃
if il > 0 and tl > 0:
nl, nr = (il + tl) % 5, ir
pre = (nl, nr, tl, tr)
to_lose.append(pre)
if lose[nl][nr][tl][tr] < 2:
flag_lose = False
to_value.append(pre)
if il > 0 and tr > 0:
nl, nr = (il + tr) % 5, ir
pre = (nl, nr, tl, tr)
to_lose.append(pre)
if lose[nl][nr][tl][tr] < 2:
flag_lose = False
to_value.append(pre)
if ir > 0 and tl > 0:
nl, nr = il, (ir + tl) % 5
pre = (nl, nr, tl, tr)
to_lose.append(pre)
if lose[nl][nr][tl][tr] < 2:
flag_lose = False
to_value.append(pre)
if ir > 0 and tr > 0:
nl, nr = il, (ir + tr) % 5
pre = (nl, nr, tl, tr)
to_lose.append(pre)
if lose[nl][nr][tl][tr] < 2:
flag_lose = False
to_value.append(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 = (il, ir, nl, nr)
to_lose.append(pre)
if lose[il][ir][nl][nr] < 2:
flag_lose = False
to_value.append(pre)
to[1][il][ir][tl][tr] = to_lose if flag_lose else to_value
# 手が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 il in range(5):
for ir in range(5):
if (il, ir) == (0, 0): continue
dp[il][ir][0][0] = 1
ans = 0
for i in range(k):
pdp = dp
dp = [[[[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
dp_value = 0
for pil, pir, ptl, ptr in to[i % 2][il][ir][tl][tr]:
dp_value += pdp[pil][pir][ptl][ptr]
dp[il][ir][tl][tr] = dp_value % md
if i % 2 == n:
ans += dp[l1][r1][l2][r2]
ans %= md
print(ans)
main()