結果
| 問題 | No.936 Are |
| ユーザー |
 mkawa2
|
| 提出日時 | 2019-12-02 18:45:51 |
| 言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,632 bytes |
| コンパイル時間 | 196 ms |
| コンパイル使用メモリ | 13,568 KB |
| 実行使用メモリ | 18,972 KB |
| 最終ジャッジ日時 | 2024-05-03 14:27:48 |
| 合計ジャッジ時間 | 4,837 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 53 ms
18,972 KB |
| testcase_01 | TLE | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
ソースコード
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()