C++で最小ページ数を割り当てる方法｜二分探索による効率的な解法

「最小ページ数の割り当て（Allocate Minimum Number of Pages）」は、競技プログラミングや技術面接で頻出する古典的なアルゴリズム問題の一つです。この記事では、問題の内容を詳しく解説し、二分探索を用いた効率的な解法をC++のサンプルコードとともに紹介します。

問題文

n冊の異なる本のページ数が与えられます。また、これらの本を割り当てる対象としてm人の学生がいます。本はページ数の昇順に並べられており、各学生には連続した本のみを割り当てることができます。プログラムは、一人の学生が読むことになる最大ページ数を返しますが、その最大値ができるだけ小さくなるような割り当てを行う必要があります。

まずは具体例を見ながら、この問題をより深く理解していきましょう。

入力 : books[] = {13 , 43, 65, 87, 92}
   m = 2
出力 : 179

解説

この例では、2人の学生が本を読むことになります。本を2人に分配する方法としては、以下の4パターンが考えられます。

ケース1 − [13] 、[43, 65, 87, 92]

この場合、一人の学生が読む最大ページ数は 13 / 287 ページとなります。

ケース2 − [13, 43] 、[65, 87, 92]

この場合、一人の学生が読む最大ページ数は 56 / 244 ページとなります。

ケース3 − [13, 43, 65] 、[87, 92]

この場合、一人の学生が読む最大ページ数は 121 / 179 ページとなります。

ケース4 − [13, 43, 65, 87] 、[92]

この場合、一人の学生が読む最大ページ数は 208 / 92 ページとなります。

これら4つのケースの中で、「一人あたりの最大ページ数」が最も小さくなるのはケース3の 179 です。したがって、この問題の答えは179となります。

この例で問題のイメージはつかめたと思います。次に、その背後にあるロジックを理解し、実際にプログラムを作成していきましょう。

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

この問題を解くためのシンプルかつ効果的なアプローチが、二分探索（バイナリサーチ）の活用です。

まず、探索範囲の下限（minimum）を0、上限（maximum）を全ての本のページ数の合計として初期化します。そして、この範囲の中間値（mid）を暫定的な答えとして設定し、アルゴリズムの進行に合わせて更新していきます。

次に、midの値を使って最終的な解が存在する可能性を調べます。具体的には、「各学生がmidページまでしか読めないという制約のもとで、m人以下の学生に全ての本を割り当てられるか？」を判定します。もし現在のmidで割り当てが可能であれば、答えはmid以下の範囲に存在する可能性があるため、下半分（minimum〜mid）をさらに探索します。逆に不可能であれば、midでは足りないということなので、上半分（mid〜maximum）を探索します。

この手法により、答えとなり得る最小の「最大ページ数」を効率的に求めることができます。計算量は O(n log Σpages) となり、全ての割り当てパターンを試す総当たり法と比べて大幅に高速です。

ただし、注意点として、学生の人数が増えるにつれて、このアルゴリズムが返す解の信頼性が低下する傾向がある点には留意しておきましょう。

C++での実装例

#include<bits/stdc++.h>
using namespace std;
bool isPossible(int arr[], int n, int m, int curr_min) ;
int min_pages(int arr[], int n, int m) ;
int main(){
   int n = 5;
   int books[] = {13 , 43, 65, 87, 92};
   cout<<"本のページ数 :\n";
   for(int i = 0 ; i< n; i++){
      cout<<books[i]<<"\t";
   }
   int m = 2;
   cout<<"\n最小ページ数 = "<<min_pages(books, n, m)<<endl;
   return 0;
}
bool isPossible(int arr[], int n, int m, int curr_min){
   int studentsRequired = 1;
   int curr_sum = 0;
   for (int i = 0; i < n; i++){
      if (arr[i] > curr_min)
         return false;
      if (curr_sum + arr[i] > curr_min){
         studentsRequired++;
         curr_sum = arr[i];
         if (studentsRequired > m)
            return false;
      }
      else
         curr_sum += arr[i];
   }
   return true;
}
int min_pages(int arr[], int n, int m){
   long long sum = 0;
   if (n < m)
      return -1;
   for (int i = 0; i < n; i++)
      sum += arr[i];
   int minimum = 0, maximum = sum;
   int result = INT_MAX;
   while (minimum <= maximum){
      int mid = (minimum + maximum) / 2;
      if (isPossible(arr, n, m, mid)){
         result = min(result, mid);
         maximum = mid - 1;
      }
      else
         minimum = mid + 1;
   }
   return result;
}

isPossible関数の仕組み

isPossible関数は、「各学生がcurr_minページまで読める」という条件のもとで、m人以下の学生にすべての本を割り振れるかどうかを判定します。ある本のページ数がcurr_minを超えていれば、その本はどの学生にも割り当てられないためfalseを返します。また、現在の合計に次の本を加えるとcurr_minを超える場合は、割り当てを新しい学生に切り替えます。必要な学生数がmを超えた時点でfalseを返し、最後まで処理できればtrueを返します。

min_pages関数の仕組み

min_pages関数が二分探索の本体です。本の冊数nが学生数mより少ない場合は、全員に最低1冊ずつ割り当てることができないため-1を返します。その後、探索範囲 [0, 全ページ数の合計] に対して二分探索を実行し、割り当てが可能な最小のmid値をresultとして記録しながら絞り込んでいきます。ループ終了時のresultが、求めるべき「最小化された最大ページ数」です。

実行結果

本のページ数 :
13	43	65	87	92
最小ページ数 = 179