C++で平均値が最大となるパスを求める方法

問題の概要

この問題では、2次元行列が与えられ、その中から平均値が最大となるパスを見つける必要があります。パスの始点は必ず左上のセル、終点は右下のセルです。具体的には以下のような例になります。

入力 : Matrix = [1, 2, 3
                 4, 5, 6
                 7, 8, 9]
出力 : 5.8
平均値が最大となるパスは、1 -> 4 -> 7 -> 8 -> 9
パスの合計は 29、平均は 29/5 = 5.8

この問題では、移動は「右」または「下」の2方向のみが許されています。この制約があるおかげで問題はぐっとシンプルになります。というのも、目的地に到達するには右への移動が N-1 回、下への移動が N-1 回必要であり、それが最短かつ有効なパスになることが明確だからです。この観察をもとに、解法のアプローチを組み立てていきましょう。

解法のアプローチ

ここで重要なのは、パスの長さ（移動回数）が常に固定であるという点です。N×N の行列の場合、移動回数は必ず (2×N) − 1 回になります。つまり、平均の分母が固定されているため、私たちが求めるべきは最大パス和だけです。

そこで、動的計画法（Dynamic Programming）を活用して最大パス和を効率的に計算します。DP表の各セルには「そのセルに到達するまでの最大パス和」を格納し、各セルへは左または上からしか来れないため、遷移式は次のようになります。

dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + cost[i][j]

C++による実装例

上記のアプローチを実装したC++コードがこちらです。

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

// 最大パス和を返す関数
int maximumPathSum(int cost[][3], int n){
    int dp[n+1][n+1];
    dp[0][0] = cost[0][0];

    // DP表の最初の列を初期化
    for (int i = 1; i < n; i++)
        dp[i][0] = dp[i-1][0] + cost[i][0];

    // DP表の最初の行を初期化
    for (int j = 1; j < n; j++)
        dp[0][j] = dp[0][j-1] + cost[0][j];

    // 残りのDP表を構築
    for (int i = 1; i < n; i++)
        for (int j = 1; j < n; j++)
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + cost[i][j];

    return dp[n-1][n-1]; // 最大パス和を返す
}

int main(){
    int cost[3][3] = { {1, 2, 3}, {4, 5, 6}, {7, 8, 9} }; // 与えられたグリッド
    int n = 3; // 行列のサイズ
    // 最大パス和を移動回数 (2*n - 1) で割って平均を求める
    printf("%.1f", float(maximumPathSum(cost, n)) / float(2*n - 1));
    return 0;
}

出力結果

5.8

コードの解説

このコードのポイントを順番に見ていきましょう。

• 移動回数の固定： 移動回数の最大値は (2×n) − 1（n は行列のサイズ）で一定です。そのため、平均を求めるには最大パス和さえ計算できれば十分です。
• 境界の初期化： DP表の最初の行と最初の列は、それぞれ左方向・上方向からしか到達できないため、累積和で直接初期化できます。
• 遷移の構築： 各セルの値は「上から来た場合」と「左から来た場合」の大きい方に現在のセルのコストを加えたものになります。
• 計算量： 時間計算量は O(n²)、空間計算量も O(n²) であり、非常に効率的です。

これは動的計画法における古典的な問題の一つであり、グリッド上の経路探索の基礎としても多くの場面で応用されます。

まとめ

このチュートリアルでは、平均値が最大となるパスを求める問題を取り上げました。移動方向が右と下に限定されているためパスの長さが固定され、問題は「最大パス和を求める動的計画法」に帰着することを学びました。紹介したC++プログラムは、C、Java、Pythonなど他の言語でも同様のロジックで実装可能です。ぜひ実際にコードを書いて、動作を確認してみてください。