概要

\(N \times M\) のグリッドを上から下へ滑り降りるコースを選ぶ際、「同じ方向に2回連続で曲がれない（ジグザグ制約）」という条件のもとで、通過する区画のスコア合計を最大化する問題です。動的計画法（DP）で解きます。

考察

重要な気づき

この問題のポイントは「連続する同じ方向への移動を禁止する」というジグザグ制約をどう扱うかです。

例えば、今いるセルに「右移動（\(d=+1\)）で到着した」場合、次の移動で再び右（\(d=+1\)）に進むことはできません。一方、直進（\(d=0\)）や左（\(d=-1\)）には進めます。

つまり、次にどの方向に進めるかは、直前の移動方向に依存します。これは「状態」として持つべき情報です。

素朴なアプローチの問題点

もし全てのコースを列挙すると、各行で最大3通りの選択肢があるため \(O(3^N)\) 通りとなり、到底間に合いません。

解決策

直前の移動方向を状態に加えたDPを行えば、各セル・各状態について \(O(1)\) で遷移を計算でき、全体で \(O(NM)\) で解けます。

アルゴリズム

状態の定義

\(dp[r][c][s]\)：第 \(r\) 行の列 \(c\) に、状態 \(s\) で到着したときのスコア合計の最大値

状態 \(s\) は以下の3種類： - 状態0：直進（\(d=0\)）で到着した、もしくはスタート地点 - 状態1：右移動（\(d=+1\)）で到着した - 状態2：左移動（\(d=-1\)）で到着した

遷移

第 \(r\) 行の列 \(c\) への到着を考えます：

1. 直進で到着（\((r-1, c) \to (r, c)\)）：
   前の行の同じ列から来る。直前の状態は何でもOK。
   \(\text{new\_dp0}[c] = \max(dp0[c], dp1[c], dp2[c]) + G[r][c]\)

2. 右移動で到着（\((r-1, c-1) \to (r, c)\)）：
   前の行の列 \(c-1\) から来る。ただし、状態1（前回も右移動）からは来られない。
   \(\text{new\_dp1}[c] = \max(dp0[c-1], dp2[c-1]) + G[r][c]\)

3. 左移動で到着（\((r-1, c+1) \to (r, c)\)）：
   前の行の列 \(c+1\) から来る。ただし、状態2（前回も左移動）からは来られない。
   \(\text{new\_dp2}[c] = \max(dp0[c+1], dp1[c+1]) + G[r][c]\)

初期値と答え

• 初期値：第1行の全ての列 \(c\) について \(dp0[c] = G[0][c]\)（スタート地点）
• 答え：第 \(N\) 行の全ての列・全ての状態の最大値

具体例

3行3列で、列を左から1,2,3とします。もし行1で列2にいて、行2で列3に移動（右移動）したら状態1です。次の行3では： - 列2へ（左移動）→ OK ✓ - 列3へ（直進）→ OK ✓
- 列4へ（右移動）→ NG ✗（右が2回連続）

計算量

• 時間計算量: \(O(NM)\) — 各セルについて3状態の遷移を \(O(1)\) で計算
• 空間計算量: \(O(M)\) — 行ごとにDPテーブルを更新するため、前の行の情報のみ保持

実装のポイント

• DPの配列を行ごとに更新する（前の行の値を参照して新しい行の値を計算する）ことで、空間を \(O(M)\) に抑えている。

• 到達不可能な状態を NEG_INF = -10^18 で表し、到達可能な状態のみ遷移に使う。

• 入力が大きくなりうる（\(NM \leq 2 \times 10^6\)）ため、sys.stdin.buffer.read() で高速に読み込んでいる。

• Python では定数倍が重い場合、この解法がギリギリになる可能性がある（PyPy推奨のケースもある）。

  ソースコード

import sys

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    
    G = []
    for i in range(N):
        row = [int(data[idx + j]) for j in range(M)]
        idx += M
        G.append(row)
    
    NEG_INF = -10**18
    
    # state 0: arrived straight (or start), state 1: arrived via d=+1 (right), state 2: arrived via d=-1 (left)
    dp0 = [NEG_INF] * M
    dp1 = [NEG_INF] * M
    dp2 = [NEG_INF] * M
    
    for c in range(M):
        dp0[c] = G[0][c]
    
    for r in range(1, N):
        new_dp0 = [NEG_INF] * M
        new_dp1 = [NEG_INF] * M
        new_dp2 = [NEG_INF] * M
        gr = G[r]
        
        for c in range(M):
            # Arrive via straight (d=0): from (r-1, c), any previous state allowed
            v0 = dp0[c]
            v1 = dp1[c]
            v2 = dp2[c]
            val = v0
            if v1 > val: val = v1
            if v2 > val: val = v2
            if val != NEG_INF:
                new_dp0[c] = val + gr[c]
            
            # Arrive via right (d=+1): from (r-1, c-1), exclude state 1 (can't have two rights)
            if c > 0:
                v0 = dp0[c - 1]
                v2 = dp2[c - 1]
                val = v0
                if v2 > val: val = v2
                if val != NEG_INF:
                    new_dp1[c] = val + gr[c]
            
            # Arrive via left (d=-1): from (r-1, c+1), exclude state 2 (can't have two lefts)
            if c < M - 1:
                v0 = dp0[c + 1]
                v1 = dp1[c + 1]
                val = v0
                if v1 > val: val = v1
                if val != NEG_INF:
                    new_dp2[c] = val + gr[c]
        
        dp0 = new_dp0
        dp1 = new_dp1
        dp2 = new_dp2
    
    ans = NEG_INF
    for c in range(M):
        if dp0[c] > ans: ans = dp0[c]
        if dp1[c] > ans: ans = dp1[c]
        if dp2[c] > ans: ans = dp2[c]
    
    print(ans)

main()

---

この解説は claude4.6opus-thinking によって生成されました。