ABC248F - Keep Connect

考え方

左から見ていくと，コの字の辺を追加していく形になっている（初期状態のみ特殊）．各ステップで3辺のうちどれを切るかをきめるとdpで解ける．

dp[i][j][k]を，

• 左から$i$番目まで決まっていて，
• $j$本の辺を取り除かれていて，
• 上と下が連結している/いない（連結なら1，非連結なら0）

ものの数とする（ただし，上下を連結させれば，左右方向にも連結になるものに限定して考える）．

遷移は，辺を0〜2本消す場合を考えればよい（3本なら左右方向に非連結になりNG）．$i\rightarrow i + 1$の遷移を考えると

• 0本切断：$i$が連結でも非連結でも，連結に遷移する．
• 1本切断：$i$が連結の場合はどこを切っても連結に遷移する．$i$が非連結の場合は横方向の連結可能性を保ったまま切断できるのは縦の1つに限られ，この場合非連結に遷移する．
• 2本切断：$i$が連結の場合，隣り合った2本を切断する2通りの方法で，非連結に遷移する．$i$が非連結の場合，横方向の連結可能性を保てるものは存在しない．

【参考】ユニークビジョンプログラミングコンテスト2022（AtCoder Beginner Contest 248） - YouTube

回答例

3次元配列を使うとTLEするので，2次元配列2つで実装した．

N, P = map(int, input().split())

dp0 = [[0] * N for _ in range(N)]
dp1 = [[0] * N for _ in range(N)]

dp0[0][1] = 1
dp1[0][0] = 1

for i in range(N - 1):
    for j in range(N):
        dp1[i + 1][j] += dp0[i][j] + dp1[i][j]
        dp1[i + 1][j] %= P
        if j + 1 < N:
            dp1[i + 1][j + 1] += dp1[i][j] * 3
            dp1[i + 1][j + 1] %= P
            dp0[i + 1][j + 1] += dp0[i][j]
            dp0[i + 1][j + 1] %= P
        if j + 2 < N:
            dp0[i + 1][j + 2] += dp1[i][j] * 2
            dp0[i + 1][j + 2] %= P

print(*dp1[N - 1][1:])

1次元配列を駆使するともっと早いぽい．
【参考】Submission #31027110 - UNIQUE VISION Programming Contest 2022（AtCoder Beginner Contest 248）

配列の高速化に関して，以下の記事を見つけた．
[numpy] 2次元配列の高速化 | maspyのHP

numpyを使って書き直して見ると，きれいに書けたが，(Pythonでないといけないぶん？) 上のコード＋PyPyよりは遅くなってしまった．

import numpy as np

N, P = map(int, input().split())

dp0 = np.zeros((N, N), dtype = np.int64)
dp1 = np.zeros((N, N), dtype = np.int64)
dp0[0][1] = 1
dp1[0][0] = 1

for i in range(N - 1):
    dp1[i + 1] += dp0[i] + dp1[i]
    dp1[i + 1][1:] += dp1[i][:-1] * 3
    dp0[i + 1][1:] += dp0[i][:-1]
    dp0[i + 1][2:] += dp1[i][:-2] * 2
    dp0[i + 1] %= P
    dp1[i + 1] %= P

print(*dp1[N - 1][1:])