C++で解く「3nスライスのピザ」問題 ― 動的計画法でスライスの合計を最大化する方法

問題の概要

大きさがまちまちの 3n 個のスライスからなるピザがあるとします。私と友人2人は、次のルールに従ってピザを取っていきます。

• 私が任意のスライスを1枚選びます。
• 友人のAmalは、私が選んだスライスの反時計回り方向に隣接するスライスを取ります。
• 友人のBimalは、私が選んだスライスの時計回り方向に隣接するスライスを取ります。
• ピザのスライスがなくなるまで、この手順を繰り返します。

各スライスの大きさは、時計回りの順に並べた環状配列 slices として与えられます。求めるのは、私が手にできるスライスの大きさの合計の最大値です。

入出力例

入力が [9, 8, 6, 1, 1, 8] の場合を考えてみましょう。

このときの出力は 16 になります。毎ターン大きさ 8 のスライスを選べば、合計は 8 + 8 = 16 となるからです。もし最初に大きさ 9 のスライスを選んでしまうと、両隣にある大きさ 8 のスライスを友人たちに取られてしまい、結果的に損をしてしまいます。

解法のアプローチ

この問題の鍵は、自分がスライスを1枚取るとその両隣が友人に取られてしまうため、「環状配列から互いに隣接しない n/3 枚のスライスを選び、合計を最大化する」問題に帰着できる点です。これを動的計画法(DP)で解いていきます。

まず、配列 v と整数 m を引数にとる関数 solve() を定義します。m は「これから選べるスライスの残り枚数」を表します。

solve() 関数の処理手順

1. n := v のサイズとします。
2. 2つの2次元配列 dp1 と dp2 を、それぞれ (n + 1) × (m + 1) のサイズで定義します。
3. i を 0 から n - 1 まで1ずつ増やしながら、以下を繰り返します。
   • j を 0 から m まで1ずつ増やしながら、以下を繰り返します。
     • x := v[i] とします。
     • j < m の場合、次の状態遷移を行います。
       • dp2[i + 1][j + 1] = max(dp2[i + 1][j + 1], dp1[i][j] + x)
       • dp1[i + 1][j] = max(dp1[i + 1][j], dp2[i][j], dp1[i][j])
4. max(dp1[n][m], dp2[n][m]) を返します。

ここで dp1[i][j] は「i 番目のスライスを選べる状態で、先頭から i 枚の範囲で j 枚選んだときの合計の最大値」、dp2[i][j] は「直前のスライスを取ったため i 番目が選べない状態での合計の最大値」を表します。スライスを選んだ直後は隣のスライスが取れないため、この2状態のDPが必要になるのです。

メイン処理の手順

ピザは環状につながっているため、先頭のスライスを取るかどうかで場合分けします。

1. n := slices のサイズとします。
2. ret := 0 とします。
3. ret := max( solve(slices の 2 番目以降, n / 3), slices[0] + solve(slices の 3 番目から末尾の1つ手前まで, n / 3 - 1) ) とします。
4. ret を返します。

1つ目のケースは「先頭のスライスを取らない」場合、2つ目は「先頭のスライスを取る」場合です。先頭を取ると環状のつながりにより末尾のスライスは取れなくなるため、探索範囲から除外しています。

C++による実装例

それでは、以下の実装例を見て理解を深めましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int solve(vector <int> v, int m){
      int n = v.size();
      vector<vector<int> > dp1(n + 1, vector<int>(m + 1));
      vector<vector<int> > dp2(n + 1, vector<int>(m + 1));
      for (int i = 0; i < n; i++) {
         for (int j = 0; j <= m; j++) {
            int x = v[i];
            if (j < m)
            dp2[i + 1][j + 1] = max(dp2[i + 1][j + 1], dp1[i]
            [j] + x);
            dp1[i + 1][j] = max({ dp1[i + 1][j], dp2[i][j],
            dp1[i][j] });
         }
      }
      return max(dp1[n][m], dp2[n][m]);
   }
   int maxSizeSlices(vector<int>& slices) {
      int n = slices.size();
      int ret = 0;
      ret = max(solve(vector<int>(slices.begin() + 1,
      slices.end()), n / 3), slices[0] + solve(vector<int>(slices.begin() +
      2, slices.end() - 1), n / 3 - 1));
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {9,8,6,1,1,8};
   cout << (ob.maxSizeSlices(v));
}

入力

{9,8,6,1,1,8}

出力

16

計算量

このアルゴリズムの時間計算量・空間計算量は、いずれも O(n²) です(n はスライスの総数)。DPテーブルのサイズは n × (n/3) であり、各セルの更新が定数時間で行えるためです。環状のピザを直線上の問題に分解してからDPを適用するこの手法は、同種の「環状配列から制約付きで要素を選ぶ」問題にも応用できる汎用的なテクニックです。