C++で解く「最高の観光ペア」問題：効率的なアルゴリズムと実装

問題の概要

正の整数からなる配列 A が与えられ、A[i] は i 番目の観光スポットの価値を表しているものとします。2つの観光スポット i と j の間の距離は j - i で定義され、観光スポットのペア（i < j）のスコアは次の式で計算されます。

A[i] + A[j] + i − j

このとき、すべてのペアの中で最大のスコアを求める必要があります。

たとえば、入力が [8, 1, 5, 2, 6] の場合を考えてみましょう。i = 0、j = 2 を選ぶと、A[0] + A[2] + 0 − 2 = 8 + 5 + 0 − 2 = 11 となり、これが最大スコアになります。したがって出力は 11 です。

解法のアプローチ

全ペアを総当たりで調べると計算量は O(n²) になり、配列が大きい場合には非効率です。そこで、式を次のように変形して考えます。

A[i] + A[j] + i − j = (A[i] + i) + (A[j] − j)

ここで重要なのは、j を固定したときに最大化したいのは「それまでに見た中で最大の A[i] + i」だという点です。つまり、配列を左から一度走査しながら、以下の手順を実行すれば O(n) で解けます。

• ret := 0、maxVal := 0、n := 配列 A のサイズとして初期化する

• i を 0 から n − 1 まで繰り返す

  • ret := max(ret, maxVal + A[i] − i) で現在の最大スコアを更新

  • maxVal := max(A[i] + i, maxVal) で「A[i] + i」の最大値を更新

• 最後に ret を返す

ポイントは、maxVal を更新する前にスコアを計算することです。これにより、常に i より前の要素とのペアだけを評価でき、同じ位置同士の組み合わせを避けられます。

C++での実装例

以下に実際のコードを示します。

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int maxScoreSightseeingPair(vector<int>& A) {
      int ret = 0;
      int maxVal = 0;
      int n = A.size();
      for(int i = 0; i < n; i++){
         ret = max(ret, maxVal + A[i] - i);
         maxVal = max(A[i] + i, maxVal);
      }
      return ret;
   }
};
main(){
   vector<int> v1 = {8, 1, 5, 2, 6};
   Solution ob;
   cout << (ob.maxScoreSightseeingPair(v1));
}

入力

[8,1,5,2,6]

出力

11

まとめ

この問題は、式を「(A[i] + i)」と「(A[j] − j)」に分解し、左側の項の累積最大値を管理しながら一回の走査で答えを求めるのが鍵となります。時間計算量 O(n)、空間計算量 O(1) と非常に効率的で、動的計画法の考え方に近いシンプルなテクニックです。類似の「片側の累積最大値を使う」パターンは他の配列問題でも応用できるので、ぜひ覚えておきましょう。