概要

\(N \times M\) のマス目に価値のある宝石が配置されており、左上から右下へ右または下にのみ移動して通過したマスの宝石を集めます。通過するマスの宝石の価値の合計を最大化する経路を求めます。

考察

この問題は「経路の選び方」が非常に多く、全探索すると組み合わせ的に爆発してしまい、現実的ではありません。たとえば、\(N = M = 1000\) の場合、経路の数は \(_{1998}C_{999}\) となり、これは天文学的な数です。

しかし、「あるマスに到達するまでの最大価値」だけを考える動的計画法（DP）を用いることで効率的に解くことができます。

具体的には、各マス \((i, j)\) について、そこまで到達する経路における価値の最大値を順に計算していけばよいのです。移動は「右」または「下」のみなので、マス \((i, j)\) に来る直前のマスは \((i-1, j)\) または \((i, j-1)\) のどちらかです。したがって、そのどちらから来たときに価値が大きいかを比較すれば良いです。

アルゴリズム

動的計画法（Dynamic Programming）を用います。

• dp[i][j] を「マス \((i, j)\) に到達するまでの経路上の宝石の価値の合計の最大値」とします。
• 初期値として、dp[0][0] = A[0][0] とします。
• 左端（\(i=0\)）については、左からのみ移動可能なので累積和的に計算します： $\( dp[0][j] = dp[0][j-1] + A[0][j] \)$
• 上端（\(j=0\)）についても同様に： $\( dp[i][0] = dp[i-1][0] + A[i][0] \)$
• それ以外のマスでは、上から来る場合と左から来る場合の大きい方を選んで加算します： $\( dp[i][j] = \max(dp[i-1][j],\ dp[i][j-1]) + A[i][j] \)$

最終的に求めたいのは dp[N-1][M-1] です。

具体例

例えば以下のような入力の場合：

3 3
1 2 3
4 5 6
7 8 9

DPテーブルは以下のようになります：

1	3	6
5	8	14
12	20	29

最大価値は 29 となります。

計算量

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

実装のポイント

• 入力を高速に読み込むために sys.stdin.read を使用しています。

• DPテーブルの初期化において、最初の行・列は特別扱いして累積和的に処理します。

• 各マスの更新では「上」と「左」の最大値を選ぶ点に注意しましょう。

  ソースコード

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    
    A = []
    index = 2
    for i in range(N):
        row = list(map(int, data[index:index + M]))
        A.append(row)
        index += M
    
    # DPテーブル初期化
    dp = [[0] * M for _ in range(N)]
    dp[0][0] = A[0][0]
    
    # 初期条件：上端
    for j in range(1, M):
        dp[0][j] = dp[0][j - 1] + A[0][j]
    
    # 初期条件：左端
    for i in range(1, N):
        dp[i][0] = dp[i - 1][0] + A[i][0]
    
    # DP更新
    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()

---

この解説は qwen3-coder-480b によって生成されました。