概要

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

考察

重要な気づき

各行での位置だけでなく、直前にどの方向に移動したかを記録しないと、ジグザグ制約を正しく判定できません。

例えば、列の変化 \(d_r = c_{r+1} - c_r\) について： - \(d_r > 0\)（右移動）の後に \(d_{r+1} > 0\)（右移動）は 禁止 - \(d_r < 0\)（左移動）の後に \(d_{r+1} < 0\)（左移動）は 禁止 - \(d_r = 0\)（直進）の後はどの方向にも移動可能

素朴なアプローチの問題

単純に dp[r][c] =「第 \(r\) 行の列 \(c\) に到達したときの最大スコア」とすると、次の行への遷移時にジグザグ制約を考慮できません。前回の移動方向が分からないためです。

解決策

DPの状態に直前の移動方向を加えます。方向は「左（\(d < 0\)）」「直進（\(d = 0\)）」「右（\(d > 0\)）」の3種類なので、状態数は \(O(N \times M \times 3)\) となり、制約内に収まります。

アルゴリズム

DPの状態を以下のように定義します：

• \(\text{dp}[c][0]\)：現在の行の列 \(c\) に左移動（列が減少）で到達したときの最大スコア
• \(\text{dp}[c][1]\)：現在の行の列 \(c\) に直進（列が変化なし）で到達したときの最大スコア
• \(\text{dp}[c][2]\)：現在の行の列 \(c\) に右移動（列が増加）で到達したときの最大スコア

遷移

次の行の列 \(c\) に到達する場合を考えます：

1. 左移動で到達（前の行の列 \(c+1\) から来る）：
   前回の移動方向は直進(1)か右(2)でなければならない（左→左は禁止）
   \(\text{ndp}[c][0] = \max(\text{dp}[c+1][1],\ \text{dp}[c+1][2]) + G[r][c]\)

2. 直進で到達（前の行の列 \(c\) から来る）：
   前回の移動方向は何でもよい
   \(\text{ndp}[c][1] = \max(\text{dp}[c][0],\ \text{dp}[c][1],\ \text{dp}[c][2]) + G[r][c]\)

3. 右移動で到達（前の行の列 \(c-1\) から来る）：
   前回の移動方向は左(0)か直進(1)でなければならない（右→右は禁止）
   \(\text{ndp}[c][2] = \max(\text{dp}[c-1][0],\ \text{dp}[c-1][1]) + G[r][c]\)

初期化

第1行ではまだ移動していないので、全ての列 \(c\) について \(\text{dp}[c][1] = G[1][c]\)（直進扱い、どの方向にも続けられる）とします。

答え

最終行で全ての列・全ての方向の中から最大値を取ります。

計算量

• 時間計算量: \(O(N \times M)\)（各セルで定数回の操作）
• 空間計算量: \(O(M)\)（現在の行と次の行の2行分のDP配列のみ保持）

実装のポイント

• 初期状態を「直進（方向1）」として初期化することで、第1行からどの方向にも自然に遷移できるようにしています。

• NEG_INF = -10^{18} を使い、到達不可能な状態と区別しています。到達不可能な状態からの遷移を防ぐため、val != NEG_INF のチェックを入れています。

• swap(dp, ndp) でDP配列を使い回すことで、メモリを節約しています。

• \(N = 1\) の場合は移動が発生しないため、第1行の最大値をそのまま出力する特別処理をしています。

  ソースコード

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N, M;
    cin >> N >> M;
    
    const long long NEG_INF = -1e18;
    vector<array<long long, 3>> dp(M, {NEG_INF, NEG_INF, NEG_INF});
    vector<array<long long, 3>> ndp(M, {NEG_INF, NEG_INF, NEG_INF});
    
    // Read and process row 0
    for (int c = 0; c < M; c++) {
        long long g;
        cin >> g;
        dp[c][1] = g;
    }
    
    if (N == 1) {
        long long ans = NEG_INF;
        for (int c = 0; c < M; c++) ans = max(ans, dp[c][1]);
        cout << ans << endl;
        return 0;
    }
    
    // Process rows 1 to N-1
    for (int r = 1; r < N; r++) {
        vector<long long> row(M);
        for (int c = 0; c < M; c++) cin >> row[c];
        
        for (int c = 0; c < M; c++) {
            ndp[c] = {NEG_INF, NEG_INF, NEG_INF};
            
            // ndp[c][0]: arrived by moving left (from c+1 in previous row)
            // allowed after straight(1) or right(2)
            if (c + 1 < M) {
                long long val = max(dp[c+1][1], dp[c+1][2]);
                if (val != NEG_INF)
                    ndp[c][0] = val + row[c];
            }
            
            // ndp[c][1]: arrived by moving straight (from c in previous row)
            // allowed after any direction
            {
                long long val = max({dp[c][0], dp[c][1], dp[c][2]});
                if (val != NEG_INF)
                    ndp[c][1] = val + row[c];
            }
            
            // ndp[c][2]: arrived by moving right (from c-1 in previous row)
            // allowed after left(0) or straight(1)
            if (c - 1 >= 0) {
                long long val = max(dp[c-1][0], dp[c-1][1]);
                if (val != NEG_INF)
                    ndp[c][2] = val + row[c];
            }
        }
        
        swap(dp, ndp);
    }
    
    long long ans = NEG_INF;
    for (int c = 0; c < M; c++) {
        ans = max(ans, max({dp[c][0], dp[c][1], dp[c][2]}));
    }
    
    cout << ans << endl;
    return 0;
}

---

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