C++でk個の部分リストに分割したときの最大合計の最小値を求める方法

問題概要

数値のリスト nums と整数 k が与えられます。このリストを k 個の空でない部分リスト（元の順序を保った連続する区間）に分割するとき、各部分リストの要素の合計のうち最も大きい値（最大合計）をできるだけ小さくしたいと考えます。求めるのは、その最大合計の最小値です。

例えば、nums = [2, 4, 3, 5, 12]、k = 2 の場合を見てみましょう。[2, 4, 3, 5] と [12] のように分割すると、合計はそれぞれ 14 と 12 になり、最大合計は 14 です。これより小さくすることはできないため、答えは 14 になります。

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

この問題は、次のような判定問題に言い換えることができます。

「上限値 x が与えられたとき、各部分リストの合計がすべて x 以下になるように、リストを k 個以下の部分リストに分割できるか？」

x を大きくするほど分割は容易になり、小さくするほど難しくなります。この単調な性質を利用すると、答えとなる x を二分探索で効率よく絞り込めます。

探索範囲は次のように設定します。

• 下限（low）：リスト内の最大要素。どの要素も必ずいずれかの部分リストに含まれるため、これ未満にはできません。
• 上限（high）：全要素の合計。リスト全体を1つの部分リストとみなせる場合の上限です。

判定関数 ok() の作成

関数 ok(v, k, x) は、配列 v を貪欲法（Greedy）で先頭から走査し、累積合計が x を超えそうになった時点で新しい部分リストを開始します。必要な部分リストの数が k 以下であれば true を返します。

1. カウンタ cnt := 0、累積値 sum := 0 で初期化します。
2. v の各要素 i に対して次を繰り返します。
   • sum + i > x の場合：sum := i とし、cnt を1増やします（新しい部分リストを開始）。
   • それ以外の場合：sum := sum + i として現在の部分リストに追加します。
3. 最後に cnt <= k なら true、そうでなければ false を返します。

solve() 関数での二分探索

1. low := 0、ret := 0、high := 0 で初期化します。
2. nums の各要素 i について、high += i、ret += i、low = max(low, i) を行います。
3. low <= high の間、次を繰り返します。
   • mid := low + (high - low) / 2 を計算します。
   • ok(nums, k - 1, mid) が true なら、ret := mid として答えを更新し、さらに小さい値を探すため high := mid - 1 とします。
   • false なら条件が厳しすぎるため、low := mid + 1 とします。
4. ループ終了後、ret を返します。

なお、ok() に渡す引数が k - 1 になっているのは、k 個への分割が「k-1 回の切り分け」に相当し、cnt がその切り分け回数を数えているためです。

C++ 実装例

以下に、上記のアルゴリズムを実装した C++ のコードを示します。

#include <bits/stdc++.h>
using namespace std;
bool ok(vector <int>& v, int k, int x){
    int cnt = 0;
    int sum = 0;
    for(int i : v){
        if(sum + i > x){
            sum = i;
            cnt++;
        }
        else{
            sum += i;
        }
    }
    return cnt <= k;
}
int solve(vector<int>& nums, int k) {
    int low = 0;
    int ret = 0;
    int high = 0;
    for(int i : nums){
        high += i;
        ret += i;
        low = max(low, i);
    }
    while(low <= high){
        int mid = low + ( high - low) / 2;
        if(ok(nums, k - 1, mid)){
            ret = mid;
            high = mid - 1;
        }
        else{
            low = mid + 1;
        }
    }
    return ret;
}
int main(){
    vector<int> v = {2, 4, 3, 5, 12};
    int k = 2;
    cout << solve(v, k);
}

入力

{2, 4, 3, 5, 12}, 2

出力

14

計算量の目安

判定関数 ok() は1回あたり O(n) で動作し、二分探索は O(log S) 回程度（S は要素の総和）繰り返されるため、全体の時間計算量は O(n log S) となります。動的計画法（DP）を用いる O(n²k) の解法と比べて非常に高速に動作します。