C++でしきい値を満たす最小の除数を二分探索で効率よく見つける方法

問題の概要

整数型の配列 nums と、しきい値を表す整数 k が与えられます。ここで、正の整数である「除数(割る数)」を1つ選び、配列のすべての要素をその値で割った結果(切り上げ)を合計することを考えます。この合計値がしきい値 k 以下となるような、最小の除数を求めるのが本問題の目的です。

例として、nums = [1,2,5,9]、k = 6 の場合を考えてみましょう。答えは 5 になります。

• 除数が 1 のとき:合計は (1+2+5+9) = 17 となり、しきい値を超えてしまいます。
• 除数が 4 のとき:合計は (1+1+2+3) = 7 となり、まだしきい値より大きいです。
• 除数が 5 のとき:合計は (1+1+1+2) = 5 となり、初めてしきい値以下になります。

なお、この問題では必ず解が存在することが保証されています。

解き方のアプローチ

この問題を効率的に解く鍵は「単調性」にあります。除数を大きくするほど各要素の商(切り上げ値)は小さくなり、合計も減少していきます。つまり、ある除数で条件を満たすなら、それより大きい除数でも必ず条件を満たします。この性質を利用すれば、二分探索によって条件を満たす最小の除数を高速に特定できます。

ステップ1:判定用メソッド check を定義する

まず、指定された除数 x が条件を満たすかどうかを判定するメソッド check を用意します。引数は x、配列 nums、しきい値 k の3つです。

• sum := 0 で初期化する。
• i が 0 から nums のサイズ − 1 までの範囲で、sum := sum + nums[i] / x の切り上げ値を加算していく。
• sum <= k なら true を、そうでなければ false を返す。

ステップ2:二分探索で最小の除数を求める

続いて、実際に答えを探索する本体の処理は次のようになります。

• low := 1、high := 十分に大きな値(配列の最大要素や固定上限値)と設定する。
• low < high の間、以下を繰り返す。
  • mid := low + (high − low) / 2 を計算する。
  • check(mid, nums, k) が true なら high := mid と更新し、false なら low := mid + 1 と更新する。
• ループを抜けたら high を返す。これが求める最小の除数です。

この方法の計算量は O(n log m)(n は配列の長さ、m は探索範囲の幅)であり、全組み合わせを試す総当たり方式よりもはるかに高速です。

C++での実装例

それでは、実際のコードを見て理解を深めましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    bool ok(int x, vector <int> &nums, int th){
        int sum = 0;
        for(int i = 0; i < nums.size(); i++){
            sum += ceil((double)nums[i]/(double)x);
        }
        return sum<=th;
    }
    int smallestDivisor(vector<int>& nums, int th) {
        int low = 1;
        int high = 1e7;
        while(low < high){
            int mid = low + (high - low)/2;
            if(ok(mid, nums, th)){
                high = mid;
            }else low = mid + 1;
        }
        return high;
    }
};
main(){
    vector<int> v = {1,2,5,9};
    Solution ob;
    cout << (ob.smallestDivisor(v, 6));
}

補足として、切り上げ除算は (nums[i] + x - 1) / x のように整数演算で表現することもできます。浮動小数点数を使う ceil 関数よりも誤差の心配がなく、パフォーマンス面でも有利なので、競技プログラミングではこちらの書き方が推奨されます。

入力

[1,2,5,9]
6

出力

5

まとめ

本記事では、配列全体をある正の整数で割った切り上げ合計がしきい値以下となる最小の除数を、C++で求める方法を解説しました。ポイントは、除数に対する合計値の単調性を見抜き、二分探索を適用することです。判定関数と二分探索を組み合わせるこのパターンは、類似の最適化問題にも応用できる汎用的なテクニックなので、ぜひマスターしておきましょう。