概要

山頂のどこかから山麓まで、下の行へ進みながらスコア合計を最大化する問題です。
ただし、左方向または右方向への移動を \(2\) 回連続で行うことはできないため、「直前にどの方向へ動いたか」を覚える動的計画法で解きます。

考察

各行から次の行へは、列を

• \(-1\) する（左へ移動）
• \(0\) のまま（まっすぐ移動）
• \(+1\) する（右へ移動）

のいずれかができます。

制約として、例えば

• 左へ移動した直後に、また左へ移動する
• 右へ移動した直後に、また右へ移動する

ことはできません。

一方で、まっすぐ移動した場合は、次に左・まっすぐ・右のどれへも移動できます。

単純に

\(dp[i][j] =\) 第 \(i\) 行第 \(j\) 列に到達する最大スコア

だけを持つと不十分です。

なぜなら、その最大スコアの経路が「直前に左へ動いてきた」のか「右へ動いてきた」のかによって、次に選べる移動が変わるからです。

例えば、同じマスに同じスコアで到達していても、

• 直前が左移動なら、次に左移動はできない
• 直前が右移動なら、次に右移動はできない
• 直前がまっすぐなら、次はどの方向にも行ける

という違いがあります。

そこで、各マスについて「直前の移動方向」ごとに状態を分けます。

アルゴリズム

現在処理している行に対して、次の \(3\) 種類の DP を持ちます。

• \(dpL[j]\)：現在の行の列 \(j\) にいて、直前の移動が左移動だったときの最大スコア
• \(dpS[j]\)：現在の行の列 \(j\) にいて、直前の移動がまっすぐだったときの最大スコア
• \(dpR[j]\)：現在の行の列 \(j\) にいて、直前の移動が右移動だったときの最大スコア

ここで、列番号はコード上では \(0\) 始まりで考えます。

第 \(1\) 行では、まだ移動していません。
そのため、便宜上「まっすぐ移動してきた」とみなして、

\[ dpS[j] = G_{1,j} \]

とします。

---

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

まっすぐ移動する場合

前の行の列 \(j\) から来ます。

まっすぐ移動は、直前の移動方向に関係なく可能です。

したがって、

\[ ndpS[j] = \max(dpL[j], dpS[j], dpR[j]) + G_{i,j} \]

です。

左へ移動する場合

現在の列 \(j\) に左移動で来るということは、前の行では列 \(j+1\) にいたことになります。

ただし、直前も左移動だった場合は、左・左となるため禁止です。

よって、前の状態は \(dpS[j+1]\) または \(dpR[j+1]\) のみ使えます。

\[ ndpL[j] = \max(dpS[j+1], dpR[j+1]) + G_{i,j} \]

ただし、\(j+1\) がグリッドの範囲内にある場合のみです。

右へ移動する場合

現在の列 \(j\) に右移動で来るということは、前の行では列 \(j-1\) にいたことになります。

ただし、直前も右移動だった場合は、右・右となるため禁止です。

よって、前の状態は \(dpS[j-1]\) または \(dpL[j-1]\) のみ使えます。

\[ ndpR[j] = \max(dpS[j-1], dpL[j-1]) + G_{i,j} \]

ただし、\(j-1\) がグリッドの範囲内にある場合のみです。

---

各行についてこの遷移を行い、最後の行まで処理したら、答えは最後の行の全列・全状態の最大値です。

\[ \max_j \max(dpL[j], dpS[j], dpR[j]) \]

計算量

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

各マスについて定数回の遷移を行うため、時間計算量は \(O(NM)\) です。

また、DP は直前の行の情報だけあれば更新できるため、全体のグリッドや全行分の DP を持つ必要はありません。
そのため、空間計算量は \(O(M)\) です。

実装のポイント

スコアは最大で

\[ 2 \times 10^6 \times 10^9 = 2 \times 10^{15} \]

程度になる可能性があります。

これは int の範囲を超えるため、long long を使う必要があります。

また、到達不可能な状態を表すために十分小さい値 NEG_INF を用意します。

const long long NEG_INF = -(1LL << 60);

範囲外の列へ移動しないように、

if (j + 1 < M)

や

if (j - 1 >= 0)

のような条件分岐も必要です。

ソースコード

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

    const long long NEG_INF = -(1LL << 60);

    vector<long long> dpL(M, NEG_INF), dpS(M, NEG_INF), dpR(M, NEG_INF);
    vector<long long> ndpL(M), ndpS(M), ndpR(M);

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

        if (i == 0) {
            for (int j = 0; j < M; j++) {
                dpS[j] = G[j];
            }
            continue;
        }

        fill(ndpL.begin(), ndpL.end(), NEG_INF);
        fill(ndpS.begin(), ndpS.end(), NEG_INF);
        fill(ndpR.begin(), ndpR.end(), NEG_INF);

        for (int j = 0; j < M; j++) {
            ndpS[j] = max({dpL[j], dpS[j], dpR[j]}) + G[j];

            if (j + 1 < M) {
                ndpL[j] = max(dpS[j + 1], dpR[j + 1]) + G[j];
            }

            if (j - 1 >= 0) {
                ndpR[j] = max(dpS[j - 1], dpL[j - 1]) + G[j];
            }
        }

        dpL.swap(ndpL);
        dpS.swap(ndpS);
        dpR.swap(ndpR);
    }

    long long ans = NEG_INF;
    for (int j = 0; j < M; j++) {
        ans = max({ans, dpL[j], dpS[j], dpR[j]});
    }

    cout << ans << '\n';
    return 0;
}

---

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