概要

この問題は、グリッド状のスキー場を「ジグザグ型」という移動制限のもとで上から下まで滑り降りる際に、得られるスコアの合計を最大化する問題です。 連続する移動の方向に制限があるため、現在の位置だけでなく「直前にどの方向から移動してきたか」の状態を保持しながら、動的計画法 (DP) を用いて解くことができます。

考察

1. 「ジグザグ型」の条件を整理する

山頂（1行目）から山麓（\(N\) 行目）へ進む際、1つ下の行への移動方向は以下の3通りがあります。 - 左下 (L): 列が \(1\) 減少する移動 - 真下 (D): 列が変化しない移動 - 右下 ®: 列が \(1\) 増加する移動

問題文にある「ジグザグ型」の条件は、「左下への移動が2回連続すること」および「右下への移動が2回連続すること」を禁止するというものです。 一方で、真下 (D) への移動については前後にどのような移動があっても制限はありません。

したがって、あるマス \((r, c)\) に進むとき、その前にどのような移動をしたかによって、次に選べる移動が変わります。 - 直前に 左下 (L) に移動していた場合 \(\to\) 次に左下 (L) へは移動できない（真下か右下のみ）。 - 直前に 右下 ® に移動していた場合 \(\to\) 次に右下 ® へは移動できない（左下か真下のみ）。 - 直前に 真下 (D) に移動していた場合 \(\to\) 次はどの方向へも移動できる。

2. なぜ単純な探索ではダメなのか？

もし、すべての経路を愚直に探索（深さ優先探索など）しようとすると、経路の数が指数関数的に増えてしまい、実行時間制限に間に合いません（TLE）。 しかし、あるマス \((r, c)\) に到達したとき、それ以降の最適な進み方は「現在どのマスにいるか」と「直前にどの方向から移動してきたか」だけで決まります。それより前の経路の詳細は関係ありません。 このように、過去の具体的な経路に依存せず、現在の状態だけで次の遷移が決まる性質（マルコフ性）があるため、動的計画法 (DP) が有効です。

---

アルゴリズム

DPテーブルの定義

以下のようにDPテーブルを定義します。

• \(dp[c][dir] :=\) 現在の行の列 \(c\) に、移動方向 \(dir\) で到達したときのスコアの最大値

ここで、直前の移動方向 \(dir\) は以下のように割り当てます。 - \(dir = 0\) (L): 右上 \((c+1)\) からの移動（左下への移動） - \(dir = 1\) (D): 真上 \((c)\) からの移動（真下への移動） - \(dir = 2\) ®: 左上 \((c-1)\) からの移動（右下への移動）

状態の遷移

1行ずつ下の行へ遷移させていきます。現在の行のDPテーブルを \(dp\)、次の行のDPテーブルを \(next\_dp\) とします。 次の行の各列 \(c\) において、3つの移動方向それぞれについて以下のように遷移を行います。

1. 左下への移動 (\(dir = 0\)) 右上 \((c+1)\) から移動してきます。ジグザグ条件より、直前の移動は L 以外（すなわち D または R）でなければなりません。 $\(next\_dp[c][0] = \max(dp[c+1][1], dp[c+1][2]) + G[r][c]\)\( *(ただし、 \)c+1 < M$ のときのみ遷移可能)*

2. 真下への移動 (\(dir = 1\)) 真上 \((c)\) から移動してきます。直前の移動に制限はありません。 $\(next\_dp[c][1] = \max(dp[c][0], dp[c][1], dp[c][2]) + G[r][c]\)$

3. 右下への移動 (\(dir = 2\)) 左上 \((c-1)\) から移動してきます。ジグザグ条件より、直前の移動は R 以外（すなわち L または D）でなければなりません。 $\(next\_dp[c][2] = \max(dp[c-1][0], dp[c-1][1]) + G[r][c]\)\( *(ただし、 \)c-1 \geq 0$ のときのみ遷移可能)*

初期化と答え

• 初期化 (1行目): 1行目はどこからでもスタートできるため、任意の列 \(c\) について、直前の移動に関わらずスコアは \(G[0][c]\) となります。 \(dp[c][0] = dp[c][1] = dp[c][2] = G[0][c]\)
• 答え: \(N\) 行目まで遷移を終えた後、すべての列 \(c\) とすべての方向 \(dir\) における \(dp[c][dir]\) の中の最大値が答えとなります。

---

計算量

時間計算量: \(O(N \times M)\)

グリッドの行数を \(N\)、列数を \(M\) とします。 各行 \(r\)（\(1\) から \(N-1\) まで）について、各列 \(c\)（\(0\) から \(M-1\) まで）の3つの状態を更新します。 1マスあたりの遷移は定数時間 \(O(1)\) で行えるため、全体の計算量は \(O(N \times M)\) です。 制約の \(N \times M \le 2 \times 10^6\) に対し、この計算量は十分に高速で、実行時間制限に余裕で間に合います。

空間計算量: \(O(N \times M)\)

グリッドのスコアを保持するために \(O(N \times M)\) のメモリを使用します。 DPテーブルについては、次の行の計算には直前の1行分のデータしか必要としないため、サイズ \(M \times 3\) の配列を2つ（\(dp\) と \(next\_dp\)）用意して使い回すことで、DP用の空間計算量を \(O(M)\) に抑えることができます。 よって、全体での空間計算量は \(O(N \times M)\) です。

---

実装のポイント

• オーバーフローの防止: スコアの最大値は \(10^9\) であり、最大で \(N = 2000\) 行滑り降りるため、合計スコアは \(2000 \times 10^9 = 2 \times 10^{12}\) に達する可能性があります。これは32ビット整数型（C++の int）の最大値（約 \(2 \times 10^9\)）を超えるため、必ず64ビット整数型（C++の long long）を使用してください。

• メモリの節約と高速化: C++において、次の行のDPテーブルを現在のDPテーブルに代入する際、dp = move(next_dp); を使用することで、メモリの再確保やコピーのオーバーヘッドを避けて高速に配列を切り替えることができます。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // 高速な入出力
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    if (!(cin >> N >> M)) return 0;

    vector<vector<long long>> G(N, vector<long long>(M));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            cin >> G[i][j];
        }
    }

    // dp[c][dir]
    // dir: 0 = L (直前の移動が左下、すなわち右上 c+1 からの移動)
    //      1 = D (直前の移動が真下、すなわち真上 c からの移動)
    //      2 = R (直前の移動が右下、すなわち左上 c-1 からの移動)
    vector<vector<long long>> dp(M, vector<long long>(3, -1));
    for (int c = 0; c < M; ++c) {
        dp[c][0] = G[0][c];
        dp[c][1] = G[0][c];
        dp[c][2] = G[0][c];
    }

    for (int r = 1; r < N; ++r) {
        vector<vector<long long>> next_dp(M, vector<long long>(3, -1));
        for (int c = 0; c < M; ++c) {
            // L: 右上 (c + 1) からの移動。直前が L 以外（D または R）である必要がある。
            if (c + 1 < M) {
                long long val = max(dp[c + 1][1], dp[c + 1][2]);
                if (val != -1) {
                    next_dp[c][0] = val + G[r][c];
                }
            }
            // D: 真上 (c) からの移動。直前の移動に制限はない。
            {
                long long val = max({dp[c][0], dp[c][1], dp[c][2]});
                if (val != -1) {
                    next_dp[c][1] = val + G[r][c];
                }
            }
            // R: 左上 (c - 1) からの移動。直前が R 以外（L または D）である必要がある。
            if (c - 1 >= 0) {
                long long val = max(dp[c - 1][0], dp[c - 1][1]);
                if (val != -1) {
                    next_dp[c][2] = val + G[r][c];
                }
            }
        }
        dp = move(next_dp);
    }

    long long ans = -1;
    for (int c = 0; c < M; ++c) {
        for (int d = 0; d < 3; ++d) {
            ans = max(ans, dp[c][d]);
        }
    }

    cout << ans << "\n";

    return 0;
}

---

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