C++でチョコレートを最適に分割するアルゴリズム

問題の概要

いくつかのチャンク(欠片)からなる1本のチョコレートバーがあるとします。各チャンクには固有の甘さがあり、それらは sweetness というリストで与えられます。このチョコレートを K 人の友人と分け合うため、K 回のカットで K+1 個のピースに切り分けます。各ピースは連続したチャンクで構成され、その中で合計甘さが最小のピースを自分が受け取ることになります。

ここで求めたいのは、チョコレートバーを最適に切り分けたときに、自分が得られるピースの合計甘さの最大値です。

例えば、入力が sweetness = [1,2,3,4,5,6,7,8,9]、K = 5 の場合、出力は 6 になります。これは [1,2,3]、[4,5]、[6]、[7]、[8]、[9] の6個のピースに分割でき、自分の取り分である最小ピース([1,2,3])の合計甘さが 6 となるためです。

解法のアプローチ:二分探索

この問題は二分探索を用いて効率的に解くことができます。「全てのピースの合計甘さが mid 以上になるように K+1 個のピースへ分割できるか?」という判定を繰り返しながら、条件を満たす最大の mid を探索します。

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

• 判定用の関数 ok() を定義する。引数は配列 v、必要なピース数 cuts、基準値 maxVal
• counter := 0、temp := 0 で初期化
• i := 0 から配列サイズまでループ:
  • temp >= maxVal なら counter を1増やし、temp を 0 にリセット
  • i が配列サイズと等しくなったらループを抜ける
  • temp に v[i] を加算
• counter >= cuts が成立すれば true を返す
• メイン処理では以下を実行:
  • n := 配列 s のサイズ
  • low := 0、high := 0 で初期化
  • 配列を走査し、low に最小値、high に合計値を設定(最後に high を +1)
  • low < high の間、mid := low + (high - low + 1) / 2 を計算し、ok(s, k + 1, mid) が真なら low := mid、偽なら high := mid - 1
• 最終的に low を返す

C++による実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   bool ok(vector <int> v, int cuts, int maxVal){
      int counter = 0;
      int temp = 0;
      for (int i = 0; i <= v.size(); i++) {
         if (temp >= maxVal) {
            counter++;
            temp = 0;
         }
         if (i == v.size()) {
            break;
         }
         temp += v[i];
      }
      return counter >= cuts;
   }
   int maximizeSweetness(vector<int>& s, int k) {
      int maxa = -1;
      int n = s.size();
      int low = 0;
      int high = 0;
      for (int i = 0; i < n; i++) {
         low = min(low, s[i]);
         high += s[i];
      }
      high++;
      while (low < high) {
         int mid = low + (high - low + 1) / 2;
         if (ok(s, k + 1, mid))
            low = mid;
         else
            high = mid - 1;
      }
      return low;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,2,3,4,5,6,7,8,9};
   cout << (ob.maximizeSweetness(v, 5));
}

入力

{1,2,3,4,5,6,7,8,9}, 5

出力

6

まとめ

このアルゴリズムでは、探索範囲の下限を配列の最小要素、上限を全体の合計甘さとし、二分探索によって「自分の取り分となりうる最小ピースの合計甘さ」の最大値を求めています。判定関数 ok() が貪欲法でピース数を数える仕組みになっているため、全体の計算量は O(n log S)(S は合計甘さ)程度に抑えられ、大きな入力に対しても高速に動作します。