概要

\(N \times M\) のグリッド上を左上から右下まで、右または下にのみ移動しながら、通過するマスの宝石の価値の合計を最大化する問題です。典型的な2次元動的計画法（DP）で解けます。

考察

重要な気づき

1. 移動方向の制限: 右か下にしか移動できないため、あるマス \((i, j)\) に到達するには、必ず「左のマス \((i, j-1)\)」か「上のマス \((i-1, j)\)」のどちらかから来ることになります。

2. 最適部分構造: マス \((i, j)\) までの最大価値を求めるには、\((i-1, j)\) までの最大価値と \((i, j-1)\) までの最大価値のうち、大きい方を選んで現在のマスの価値を足せばよいです。

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

全ての経路を列挙する方法では、経路の数が指数的に増加します。例えば \(N = M = 1000\) の場合、経路の総数は \(\binom{1998}{999}\) という天文学的な数になり、到底間に合いません。

解決策

動的計画法（DP） を使います。各マスへの最大価値を一度だけ計算し、その結果を再利用することで効率的に解けます。

アルゴリズム

\(dp[i][j]\) を「スタート \((0, 0)\) からマス \((i, j)\) までの宝石の価値の合計の最大値」と定義します（0-indexed）。

漸化式: $\(dp[i][j] = \max(dp[i-1][j], dp[i][j-1]) + A[i][j]\)$

初期条件と境界: - \(dp[0][0] = A[0][0]\)（スタート地点） - 1行目: \(dp[0][j] = dp[0][j-1] + A[0][j]\)（左からしか来れない） - 1列目: \(dp[i][0] = dp[i-1][0] + A[i][0]\)（上からしか来れない）

具体例: \(N=2, M=3\) で以下のグリッドを考えます。

1 3 1
1 5 1

DPテーブルの計算過程:

dp[0][0] = 1
dp[0][1] = 1 + 3 = 4
dp[0][2] = 4 + 1 = 5
dp[1][0] = 1 + 1 = 2
dp[1][1] = max(4, 2) + 5 = 9
dp[1][2] = max(5, 9) + 1 = 10

答えは \(dp[1][2] = 10\) となります。

計算量

• 時間計算量: \(O(N \times M)\)
  • 各マスを1回ずつ処理するため
• 空間計算量: \(O(N \times M)\)
  • DPテーブルのサイズ
  • ※ 1行分だけ保持する工夫をすれば \(O(M)\) に削減可能

実装のポイント

1. インデックスの扱い: 問題文では1-indexedですが、コードでは0-indexedで実装しています。混乱しないよう注意が必要です。

2. 境界条件の処理: 1行目と1列目は、それぞれ左からと上からしか到達できないため、別途処理しています。これにより、一般のマスで dp[i-1][j] や dp[i][j-1] を参照する際に、配列外アクセスを防げます。

3. オーバーフロー対策: 宝石の価値は最大 \(10^9\)、マス数は最大 \(10^6\) なので、合計値は最大約 \(10^{15}\) になります。Pythonでは整数のオーバーフローを気にする必要はありませんが、C++などでは long long を使う必要があります。

   ソースコード

def main():
    N, M = map(int, input().split())
    A = []
    for _ in range(N):
        row = list(map(int, input().split()))
        A.append(row)
    
    # dp[i][j] = (1,1)から(i,j)までの最大価値
    dp = [[0] * M for _ in range(N)]
    
    # 初期値
    dp[0][0] = A[0][0]
    
    # 1行目を埋める（右からしか来れない）
    for j in range(1, M):
        dp[0][j] = dp[0][j-1] + A[0][j]
    
    # 1列目を埋める（上からしか来れない）
    for i in range(1, N):
        dp[i][0] = dp[i-1][0] + A[i][0]
    
    # 残りのマスを埋める
    for i in range(1, N):
        for j in range(1, M):
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + A[i][j]
    
    print(dp[N-1][M-1])

if __name__ == "__main__":
    main()

---

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