C++で多角形の最小スコア三角分割を求めるアルゴリズム

問題概要

値 N が与えられ、頂点が A[0], A[1], ..., A[N-1] と時計回りに並んだ凸 N 角形を考えます。この多角形を N-2 個の三角形に分割する「三角分割」を行います。各三角形の値はその頂点ラベルの積として定義され、三角分割全体のスコアは N-2 個の三角形の値の合計となります。ここでの目標は、さまざまな三角分割の方法の中から達成可能な最小の合計スコアを見つけることです。

たとえば、入力が [1,2,3] の場合、出力は 6 になります。これは多角形がすでに三角形そのものであり、唯一の三角形のスコアが 1 × 2 × 3 = 6 となるためです。

解法アプローチ(区間DP)

この問題は区間動的計画法(DP)を用いて効率的に解くことができます。dp[i][j] を「頂点 i から頂点 j までの部分多角形を三角分割したときの最小スコア」と定義します。三角形の第3の頂点 k(i < k < j)を選ぶことで、部分多角形をさらに小さい部分問題へと分割できるのがポイントです。

具体的な手順は以下の通りです。

• 50 × 50 のサイズの行列 dp を作成し、すべて 0 で初期化します

• n := 与えられた配列のサイズとします

• l を 3 から n まで繰り返します(部分多角形の頂点数)

• i := 0、j := l − 1 から開始し、j < n の間、i と j をそれぞれ 1 ずつ増やしながら処理します

• k を i + 1 から j − 1 まで繰り返します

• dp[i][j] が 0 の場合は、dp[i][j] := min(無限大, dp[i][k] + dp[k][j] + A[i] × A[j] × A[k]) とします

• そうでなければ、dp[i][j] := min(dp[i][j], dp[i][k] + dp[k][j] + A[i] × A[j] × A[k]) と更新します

• 最後に dp[0][n − 1] を返します

計算量は区間の組み合わせ O(N²) と分割点の探索 O(N) からなり、全体で O(N³) となります。N ≤ 50 の制約下では十分高速に動作します。

C++ 実装例

以下のコードで実際の実装を確認してみましょう。

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
   class Solution {
   public:
   int minScoreTriangulation(vector<int>& A) {
      lli dp[50][50];
      for(int i = 0; i < 50; i++){
         for(int j = 0; j < 50; j++){
            dp[i][j] = 0;
         }
      }
      int n = A.size();
      for(int l = 3; l <= n; l++){
         for(int i = 0, j = l - 1; j < n;i++, j++){
            for(int k = i + 1; k < j; k++){
               dp[i][j] = min(dp[i][j] == 0?INT_MAX : dp[i][j],
               dp[i][k] + dp[k][j] + A[i] * A[k] * A[j]);
            }
         }
      }
      return dp[0][n - 1];
   }
};
main(){
   vector<int> v1 = {1,2,3};
   Solution ob;
   cout << (ob.minScoreTriangulation(v1));
}

入力

[1,2,3]

出力

6

まとめ

本記事では、凸多角形の三角分割における最小スコアを区間DPで求める手法を紹介しました。頂点 i と j を結ぶ辺を含む三角形の第3の頂点 k を全通り試し、部分問題の最適解を組み合わせることで、全体の最小スコアを効率よく計算できます。同様の区間DPの考え方は、行列連鎖乗算など他の古典的な問題にも応用できるため、ぜひマスターしておきましょう。