C++で解く：1回だけ出会える2人が収集できる最大ポイントの求め方

問題概要

本記事では、「1回だけ出会うことが許された2人が収集できる最大ポイント」を求めるC++のプログラムについて解説します。

各セルにポイントが書かれた行列（マトリックス）が与えられます。2人の人物は、一方が左上の角から右下の角へ、もう一方が左下の角から右上の角へと移動します。移動の途中で2人はちょうど1回だけ同じセルで出会うことができ、そのとき2人が合計で収集できるポイントの最大値を求めるのが課題です。

アルゴリズムの考え方

この問題は動的計画法（DP）を用いることで効率的に解けます。まず、次の4つのテーブルを事前に計算しておきます。

• P1S：1人目がスタート地点（左上）から各セルへ到達するまでに収集できる最大ポイント
• P1E：1人目が各セルからゴール地点（右下）へ向かう過程で収集できる最大ポイント
• P2S：2人目がスタート地点（左下）から各セルへ到達するまでに収集できる最大ポイント
• P2E：2人目が各セルからゴール地点（右上）へ向かう過程で収集できる最大ポイント

次に、出会い地点となり得る内部の各セル（i, j）について、2つの経路パターンを比較します。1人目が横方向に通り、2人目が縦方向に通るケース（op1）と、その逆のケース（op2）です。すべての候補の中で最も大きい値が答えとなります。

C++による実装例

#include<bits/stdc++.h>
#define M 3
#define N 3
using namespace std;
int findMaxPoints(int A[][M]) {
    // 各経路のポイントを保存
    int P1S[M+1][N+1], P1E[M+1][N+1];
    memset(P1S, 0, sizeof(P1S));
    memset(P1E, 0, sizeof(P1E));
    int P2S[M+1][N+1], P2E[M+1][N+1];
    memset(P2S, 0, sizeof(P2S));
    memset(P2E, 0, sizeof(P2E));
    for (int i=1; i<=N; i++)
       for (int j=1; j<=M; j++)
          P1S[i][j] = max(P1S[i-1][j], P1S[i][j-1]) + A[i-1][j-1];
    for (int i=N; i>=1; i--)
       for (int j=M; j>=1; j--)
          P1E[i][j] = max(P1E[i+1][j], P1E[i][j+1]) + A[i-1][j-1];
    for (int i=N; i>=1; i--)
       for(int j=1; j<=M; j++)
          P2S[i][j] = max(P2S[i+1][j], P2S[i][j-1]) + A[i-1][j-1];
    for (int i=1; i<=N; i++)
       for (int j=M; j>=1; j--)
          P2E[i][j] = max(P2E[i-1][j], P2E[i][j+1]) + A[i-1][j-1];
    int ans = 0;
    for (int i=2; i<N; i++) {
       for (int j=2; j<M; j++) {
          int op1 = P1S[i][j-1] + P1E[i][j+1] + P2S[i+1][j] + P2E[i-1][j];
          int op2 = P1S[i-1][j] + P1E[i+1][j] + P2S[i][j-1] + P2E[i][j+1];
          ans = max(ans, max(op1, op2));
       }
    }
    return ans;
}
int main() {
    int A[][M] = {
       {100, 100, 100},
       {100, 1, 100},
       {100, 100, 100}
    };
    cout << "Max Points : " << findMaxPoints(A);
    return 0;
}

実行結果

Max Points : 800

出力の解説

この例では、中央のセルだけが「1」、それ以外のセルはすべて「100」となっています。2人は中央の低ポイントセルを避けて交差するように進むことで、経路の重複なく合計800ポイントを収集できます。

まとめ

本記事では、動的計画法を用いて「1回だけ出会える2人」が収集できる最大ポイントを求める方法を紹介しました。4つの累積テーブルを前計算し、出会い地点の候補ごとに最適な組み合わせを評価することで、時間計算量・空間計算量ともに O(N×M) の効率的な解法を実現できます。