概要

この問題は、グリッド状のスキー場をルールに従って滑り降りるときの、最大獲得スコアを求める問題です。 移動には「同じ方向に連続して斜めに移動できない（ジグザグ条件）」という制約があるため、直前の移動方向を状態として保持しながら、動的計画法（DP）を用いて効率的に解を求めます。

考察

1. ナイーブなアプローチとその限界

各マス \((r, c)\) から次の行への移動方法は「左下」「真下」「右下」の最大 \(3\) 通りあります。 単純にすべての経路を探索する深さ優先探索（DFS）などの全探索を行うと、経路の数は \(O(3^N)\) となり、 \(N \le 2000\) では制限時間内に終わりません。

2. ジグザグ条件の整理

問題の肝は「同じ斜め方向への連続移動の禁止」です。列の変化量を \(d\) としたとき： - 左下への移動（\(d = -1\)）の後は、左下（\(d = -1\)）へは移動できません。真下（\(d = 0\)）または右下（\(d = 1\)）へ移動する必要があります。 - 右下への移動（\(d = 1\)）の後は、右下（\(d = 1\)）へは移動できません。真下（\(d = 0\)）または左下（\(d = -1\)）へ移動する必要があります。 - 真下への移動（\(d = 0\)）の後は、どの方向（\(d \in \{-1, 0, 1\}\)）へも移動できます。

このように、次の移動で選べる方向は「直前にどの方向に移動してきたか」に依存します。 したがって、各マスに到達した時点の最大スコアを求めるためには、単に「どのマスにいるか」だけでなく、「どの方向からそのマスにやってきたか」という情報を状態として持たせる必要があります。

アルゴリズム

動的計画法（DP）の定義

各行 \(r\) において、列 \(c\) の状態を以下の \(3\) つに分けて保持します。

• \(dp_0[c]\) : 直前の移動が真下（\(d = 0\)）で、マス \((r, c)\) に到達したときの最大スコア
• \(dp_1[c]\) : 直前の移動が左下（\(d = -1\)）で、マス \((r, c)\) に到達したときの最大スコア
• \(dp_2[c]\) : 直前の移動が右下（\(d = 1\)）で、マス \((r, c)\) に到達したときの最大スコア

状態遷移

第 \(r-1\) 行の DP テーブルから、第 \(r\) 行の新しい DP テーブル（next_dp）への遷移は以下のようになります（そのマスのスコアを \(G[r][c]\) とします）。

1. 真下への移動（\(next\_dp_0[c]\)）

   • 直前の移動に制限はありません。第 \(r-1\) 行の同じ列 \(c\) のどの状態からも遷移できます。 $\(next\_dp_0[c] = \max(dp_0[c], dp_1[c], dp_2[c]) + G[r][c]\)$$

2. 左下への移動（\(next\_dp_1[c]\)）

   • 第 \(r-1\) 行の列 \(c+1\) からの遷移です。
   • 直前の移動が「左下（\(dp_1\)）」であってはならないため、遷移元は \(dp_0\) または \(dp_2\) に限られます。 $\(next\_dp_1[c] = \max(dp_0[c+1], dp_2[c+1]) + G[r][c]\)$\( *(※ \)c = M-1\(（右端）のときは、さらに右からの遷移は存在しないため、\)-\infty$ とします)*

3. 右下への移動（\(next\_dp_2[c]\)）

   • 第 \(r-1\) 行の列 \(c-1\) からの遷移です。
   • 直前の移動が「右下（\(dp_2\)）」であってはならないため、遷移元は \(dp_0\) または \(dp_1\) に限られます。 $\(next\_dp_2[c] = \max(dp_0[c-1], dp_1[c-1]) + G[r][c]\)$\( *(※ \)c = 0\(（左端）のときは、さらに左からの遷移は存在しないため、\)-\infty$ とします)*

初期値

第 \(1\) 行目（\(r = 0\)）からスタートするため、最初のマスは「直前の移動がない（真下移動と同等）」とみなします。 - \(dp_0[c] = G[0][c]\) - \(dp_1[c] = -\infty\) - \(dp_2[c] = -\infty\)

第 \(N\) 行目まで遷移を繰り返した後、すべての状態の最大値 \(\max(dp_0, dp_1, dp_2)\) が答えとなります。

計算量

• 時間計算量: \(O(N \times M)\) 各行の更新において、列数 \(M\) に対する遷移を定数時間 \(O(1)\) で行います。これを行数 \(N\) 回繰り返すため、全体の計算量は \(O(N \times M)\) となり、制約の \(N \times M \le 2 \times 10^6\) に対して十分高速に動作します。

• 空間計算量: \(O(N \times M)\) グリッドの情報を保持するために \(O(N \times M)\) のメモリを使用します。DP テーブルは直前の \(1\) 行分のみを保持すればよいため、DP 自体に必要なメモリは \(O(M)\) で済みます。

実装のポイント

• Pythonでの高速化（スライスと zip の活用） Pythonで二重ループを愚直に回すと実行時間制限（TL）が厳しくなることがあります。 提示されたコードでは、以下のようにスライスと zip を用いて、各列の計算をまとめて（ベクトル化するように）高速に行っています。

  # next_dp1[c] は c+1 列目から遷移するため、[1:] でスライスして一括で最大値を取る
  next_dp1 = [max(a, b) + x for a, b, x in zip(dp0[1:], dp2[1:], g[:-1])] + [-INF]
  

  これにより、ループのオーバーヘッドを劇的に減らし、高速な動作を実現しています。

• 無限小（INF）の設定 移動できない経路（グリッド外からの遷移など）を排除するために十分小さな値（-INF）を使用します。 本問題では、スコアの最大合計値が \(N \times \max(G_{i,j}) = 2000 \times 10^9 = 2 \times 10^{12}\) に達する可能性があるため、INF はそれより十分大きい 10**18 に設定されています。

  ソースコード

import sys


def solve():
    # Read all inputs from standard input
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    N = int(input_data[0])
    M = int(input_data[1])

    # Flattened grid values converted to integers
    flat_G = list(map(int, input_data[2:]))

    # Reconstruct 2D grid
    G = []
    for r in range(N):
        G.append(flat_G[r * M : (r + 1) * M])

    INF = 10**18

    # dp0[c]: Max score at (r, c) where the last move was straight down (d = 0)
    # dp1[c]: Max score at (r, c) where the last move was down-left (d = -1)
    # dp2[c]: Max score at (r, c) where the last move was down-right (d = 1)
    dp0 = G[0][:]
    dp1 = [-INF] * M
    dp2 = [-INF] * M

    for r in range(1, N):
        g = G[r]

        # Transition for state 0 (straight down): can come from any state 0, 1, 2
        next_dp0 = [max(a, b, c) + x for a, b, c, x in zip(dp0, dp1, dp2, g)]

        # Transition for state 1 (down-left): must come from state 0 or 2 (not 1)
        # next_dp1[c] comes from column c+1
        next_dp1 = [
            max(a, b) + x for a, b, x in zip(dp0[1:], dp2[1:], g[:-1])
        ] + [-INF]

        # Transition for state 2 (down-right): must come from state 0 or 1 (not 2)
        # next_dp2[c] comes from column c-1
        next_dp2 = [-INF] + [
            max(a, b) + x for a, b, x in zip(dp0[:-1], dp1[:-1], g[1:])
        ]

        dp0 = next_dp0
        dp1 = next_dp1
        dp2 = next_dp2

    # The answer is the maximum value in any state at the last row
    ans = max(max(dp0), max(dp1), max(dp2))
    print(ans)


if __name__ == "__main__":
    solve()

---

この解説は gemini-3.5-flash-thinking によって生成されました。