概要

上から下へ 1 行ずつ移動しながら、通ったマスのスコア合計を最大化する問題です。
ただし「右→右」や「左→左」のように、同じ横方向へ 2 回連続で移動してはいけません。

考察

各行で移動できる先は、次の行の

• 左下
• 真下
• 右下

の 3 通りです。

単純にすべての経路を試すと、各行ごとに最大 3 通りに分岐するため、経路数はおよそ \(3^{N-1}\) となり、到底間に合いません。

そこで動的計画法を考えます。

通常の「上から下へ進むグリッド DP」なら、

「今いるマスに到達する最大スコア」

だけを持てばよいです。

しかし、この問題ではジグザグ条件があります。
例えば、直前に右へ移動してきた場合、次も右へ移動することはできません。

つまり、次の移動が可能かどうかは「直前の横方向の移動」に依存します。
そのため、各マスについて次の 3 状態を持ちます。

• 最後の移動が真下だった場合
• 最後の移動が右方向だった場合
• 最後の移動が左方向だった場合

ここで、列番号の変化を \(d\) とすると、

• 真下移動: \(d = 0\)
• 右方向移動: \(d = +1\)
• 左方向移動: \(d = -1\)

です。

真下移動はジグザグ制約に影響しないため、どの方向の後にも行えます。
一方で、右方向移動は直前も右方向だった場合は禁止、左方向移動は直前も左方向だった場合は禁止です。

アルゴリズム

次の 3 つの DP 配列を用意します。

• z[j]: 現在の行の列 \(j\) にいて、最後の移動が真下だったときの最大スコア
• p[j]: 現在の行の列 \(j\) にいて、最後の移動が右方向だったときの最大スコア
• m[j]: 現在の行の列 \(j\) にいて、最後の移動が左方向だったときの最大スコア

列番号は実装上 \(0\) 始まりで考えます。

初期化

第 1 行では、まだ移動していません。
このコードでは「最後の移動が真下だった状態」として扱い、

z = first
p = [NEG] * M
m = [NEG] * M

としています。

NEG は到達不可能を表す十分小さい値です。

遷移

次の行の値を row[j] とします。

真下に移動する場合

前の行の同じ列 \(j\) から来ます。
真下移動は直前の方向に関係なく可能なので、

\[ nz[j] = \max(z[j], p[j], m[j]) + row[j] \]

です。

右方向に移動する場合

前の行の列 \(j-1\) から、現在の列 \(j\) に来ます。
これは列が \(+1\) される移動です。

ただし、直前も右方向だった場合は禁止なので、使えるのは z[j-1] または m[j-1] です。

\[ np[j] = \max(z[j-1], m[j-1]) + row[j] \]

ただし、\(j > 0\) のときのみ可能です。

左方向に移動する場合

前の行の列 \(j+1\) から、現在の列 \(j\) に来ます。
これは列が \(-1\) される移動です。

直前も左方向だった場合は禁止なので、使えるのは z[j+1] または p[j+1] です。

\[ nm[j] = \max(z[j+1], p[j+1]) + row[j] \]

ただし、\(j+1 < M\) のときのみ可能です。

答え

最後の行のどの列で終わってもよく、最後の移動方向も何でもよいので、

\[ \max(\max(z), \max(p), \max(m)) \]

が答えです。

計算量

• 時間計算量: \(O(NM)\)
• 空間計算量: \(O(M)\)

各マスについて定数回の遷移だけを行います。
また、DP は直前の行だけあればよいため、グリッド全体を保持せず、1 行ずつ処理できます。

実装のポイント

到達不可能な状態を表すために、十分小さい値 NEG = -10**30 を使っています。

スコアの最大合計は高々

\[ N \times 10^9 \]

程度なので、\(N \leq 2000\) の制約では -10**30 は十分小さい値です。

また、\(N=1\) の場合は移動がないため、第 1 行の最大値がそのまま答えになります。
この実装では初期状態 z = first のまま答えを取ることで自然に対応できています。

ソースコード

import sys

def main():
    input = sys.stdin.buffer.readline
    N, M = map(int, input().split())

    first = list(map(int, input().split()))
    NEG = -10**30

    z = first
    p = [NEG] * M
    m = [NEG] * M

    for _ in range(1, N):
        row = list(map(int, input().split()))

        nz = [NEG] * M
        np = [NEG] * M
        nm = [NEG] * M

        zz = z
        pp = p
        mm = m
        rr = row

        for j in range(M):
            g = rr[j]

            a = zz[j]
            b = pp[j]
            c = mm[j]
            if b > a:
                a = b
            if c > a:
                a = c
            nz[j] = a + g

            if j > 0:
                a = zz[j - 1]
                b = mm[j - 1]
                if b > a:
                    a = b
                np[j] = a + g

            if j + 1 < M:
                a = zz[j + 1]
                b = pp[j + 1]
                if b > a:
                    a = b
                nm[j] = a + g

        z, p, m = nz, np, nm

    ans = max(max(z), max(p), max(m))
    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.5-high によって生成されました。