C++で解くココのバナナ食べ問題 ― 二分探索で最小の食べる速度を求める

問題概要

N 山のバナナがあり、i 番目の山には piles[i] 本のバナナが入っています。警備員は外出中で、H 時間後に戻ってきます。ココは 1 時間あたり K 本というバナナを食べる速度を自由に決めることができます。毎時間、彼女はどれか 1 つの山を選び、その山から K 本のバナナを食べます。もし山に残っているバナナが K 本未満であれば、その山をすべて食べきり、その時間内にはそれ以上何も食べません。

ココはできるだけゆっくりバナナを食べたいのですが、同時に警備員が戻ってくる前にすべてのバナナを食べ終えたいとも考えています。このとき、H 時間以内にすべてのバナナを食べ切ることができる最小の整数 K を求めてください。

たとえば、入力が [3,6,7,11]、H = 8 の場合、出力は 4 になります。

解法の考え方：二分探索

この問題は二分探索（バイナリサーチ）を使うことで効率的に解くことができます。食べる速度 K が大きいほど必要な時間は短くなり、K が小さいほど時間がかかるため、「条件を満たす最小の K」を二分探索で絞り込むのが有効です。

具体的には、以下の手順に従います。

• 判定用メソッド ok() を定義します。引数として配列 a、候補となる速度 x、制限時間 h を受け取ります。
• time := 0 と初期化します。
• i を 0 から配列 a のサイズまでループします。
  • time := time + a[i] / x（切り捨て除算）
  • a[i] % x が 0 でない場合（余りが出る場合）、time にさらに 1 を加算します。
• 最後に time <= H であれば true を返します。
• メインメソッドでは次のように処理します。
• n := piles 配列のサイズ、low := 1、high := 0 と初期化します。
• i を 0 から n − 1 までループし、high := max(piles[i], high) として山の最大値を求めます。
• low < high の間、以下を繰り返します。
  • mid := low + (high − low) / 2
  • ok(piles, mid, H) が true なら high := mid、そうでなければ low := mid + 1
• 最終的に high を答えとして返します。

探索範囲の下限は 1（最低でも 1 本/時）、上限は山の中の最大値（それ以上速く食べても無駄になるだけ）である点がポイントです。

C++ 実装例

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
    public:
    bool ok(vector <int>& a, int x, int H){
        int time = 0;
        for(int i = 0; i < a.size(); i++){
            time += a[i] / x;
            time += (a[i] % x ? 1 : 0);
        }
        return time <= H;
    }
    int minEatingSpeed(vector<int>& piles, int H) {
        int n = piles.size();
        lli low = 1;
        lli sum = 0;
        lli high = 0;
        for(int i = 0; i < n; i++)high = max((lli)piles[i], high);
        while(low < high){
            int mid = low + (high - low) / 2;
            if(ok(piles, mid, H)){
                high = mid;
            }else{
                low = mid + 1;
            }
        }
        return high;
    }
};
main(){
    vector<int> v = {3,6,7,11};
    Solution ob;
    cout << (ob.minEatingSpeed(v, 8));
}

入力

[3,6,7,11]
8

出力

4

計算量について

判定関数 ok() は 1 回あたり O(N)、二分探索は O(log M) 回（M は山の最大サイズ）繰り返されるため、全体の計算量は O(N log M) となります。すべての速度候補を順に試す O(N × M) の総当たり方式と比べ、大幅に高速に動作するのがこの解法の強みです。