結果
| 問題 | No.936 Are |
| ユーザー |
 mkawa2
|
| 提出日時 | 2019-12-02 18:46:51 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,632 bytes |
| コンパイル時間 | 477 ms |
| コンパイル使用メモリ | 82,176 KB |
| 実行使用メモリ | 419,968 KB |
| 最終ジャッジ日時 | 2024-11-24 15:12:59 |
| 合計ジャッジ時間 | 56,813 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 143 ms
83,456 KB |
| testcase_01 | TLE | - |
| testcase_02 | TLE | - |
| testcase_03 | AC | 279 ms
86,528 KB |
| testcase_04 | AC | 326 ms
340,480 KB |
| testcase_05 | AC | 237 ms
86,400 KB |
| testcase_06 | AC | 307 ms
342,528 KB |
| testcase_07 | AC | 217 ms
85,376 KB |
| testcase_08 | AC | 207 ms
339,840 KB |
| testcase_09 | AC | 290 ms
88,448 KB |
| testcase_10 | AC | 241 ms
322,432 KB |
| testcase_11 | AC | 290 ms
88,064 KB |
| testcase_12 | AC | 167 ms
292,096 KB |
| testcase_13 | AC | 2,907 ms
188,288 KB |
| testcase_14 | TLE | - |
| testcase_15 | TLE | - |
| testcase_16 | TLE | - |
| testcase_17 | TLE | - |
| testcase_18 | AC | 2,345 ms
419,968 KB |
| testcase_19 | TLE | - |
| testcase_20 | TLE | - |
| testcase_21 | TLE | - |
| testcase_22 | TLE | - |
| testcase_23 | TLE | - |
| testcase_24 | TLE | - |
ソースコード
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()