第4回では、探索範囲を半減させていくことで素早く答えを求める「二分探索法」を紹介しました。このアルゴリズムは値の検索に利用されることが多いのですが、実はもっと広い範囲に適用することができます。今回はその一例として、塾のクラス分けを行う問題を考えてみましょう。

第4回「二分探索法とは」はこちらから

クラス分けの問題

ある塾でクラス分けのテストが行われ、成績分布は以下の表のようになりました。あなたはこの塾の生徒を、テストの点数が高い順に A・B・C・D・E の 5 つのクラスに分割することを考えています。ただし、同じ点数の人は同じクラスに割り当てなければなりません。あまりにも人数の少ないクラスがあると授業が活発にならないので、クラスの人数の最小値をできるだけ大きくするようにしたいと思います。どのような分け方にすればよいでしょうか。

自然な解法 [1]

自然な解法の一つは、次のような分け方です。

  • A クラス以上が 20 人にできるだけ近くなるように、A クラスの基準点を決める
  • B クラス以上が 40 人にできるだけ近くなるように、B クラスの基準点を決める
  • C クラス以上が 60 人にできるだけ近くなるように、C クラスの基準点を決める
  • D クラス以上が 80 人にできるだけ近くなるように、D クラスの基準点を決める

この方法を使うと以下のように、A～E クラスの人数が 18 人、25 人、13 人、24 人、20 人となります。最も小規模なクラスの人数は 13 人ですが、実際は 18 人にする方法があるため、残念ながら最適な答えを出すことができていません。

自然な解法 [2]

もう一つの自然な解法としては、次のようなものが思い付きやすいでしょう。

  • まず、A クラスが 20 人にできるだけ近くなるように、A クラスの基準点を決める
  • 次に、B クラスが 20 人にできるだけ近くなるように、B クラスの基準点を決める
  • 次に、C クラスが 20 人にできるだけ近くなるように、C クラスの基準点を決める
  • 次に、D クラスが 20 人にできるだけ近くなるように、D クラスの基準点を決める

この方法を使うと以下のようになり、A～E クラスの人数が 18 人、18 人、20 人、17 人、27 人となります。最も小規模なクラスの人数は 17 人であり、これでも最適な答えを出すことができていません。では、一体どうすればよいのでしょうか。

最適な答えを求めるには?

いきなり最適な答えを出すのは難しいので、まずは「クラスの人数の最小値を x 人以上にすることはできるか」という判定問題を考えましょう。これは次のようにして解くことができます。

  • まず、A クラスの人数が x 人以上となるギリギリの点数を基準点に設定する
  • 次に、B クラスの人数が x 人以上となるギリギリの点数を基準点に設定する
  • 次に、C クラスの人数が x 人以上となるギリギリの点数を基準点に設定する
  • 次に、D クラスの人数が x 人以上となるギリギリの点数を基準点に設定する
  • どのクラスの人数も x 人以上であれば答えは Yes、そうでなければ No である

例えば x=10 のとき、以下のようにクラス分けされます。各クラスの人数は 10 人、15 人、11 人、12 人、52 人となり、どのクラスも 10 人以上となるため、答えは Yes です。

この判定問題が解ければ、x を二分探索することで最適な答えを出すことができます。例えば、最適解における「最も小規模なクラスの人数 Answer」が 0～20 の間であることが分かっているとき、次の表のように計算すると、Answer=18 が得られます。

　回数　 　Answer の範囲　 　質問　 　結果　
　0　 　0～20（中央=10）　 　クラスの人数の最小値を x=10 人以上にできるか？　 　Yes　
　1　 　10～20（中央=15）　 　クラスの人数の最小値を x=15 人以上にできるか？　 　Yes　
　2　 　15～20（中央=18）　 　クラスの人数の最小値を x=18 人以上にできるか？　 　Yes　
　3　 　18～20（中央=19）　 　クラスの人数の最小値を x=19 人以上にできるか？　 　No　
　4　 　18　 　-　 　-　

下図は二分探索が行われる過程を示しています。答えが「いまあり得る範囲の中央」以上かどうかを調べることで、探索範囲を 1 手で半減させています。

このような方法を使うと、点数の種類数を N、答えとしてあり得る最大値を L とするとき、計算量 O(N log L) で最適解を出すことができます※。

　＊　＊　＊　

ここまでの説明をまとめると、「答えは x 以上ですか？」という質問に答えられるような問題では、x を二分探索することによって高速に最適解を求められる場合があります。これは、特に「〇〇の最小値をできるだけ大きくしてください」という問題で利用されることが多いテクニックです。以下に、AtCoderで無料公開されている例題をいくつか挙げておきますので、興味のある人はぜひ解いてみてください。

前回・今回と2回にわたり、二分探索法とその応用について解説しました。二分探索の基本的な考え方と、活用イメージをつかんでいただけたでしょうか。次回は 1 手先のみを考える「貪欲法」というアルゴリズムを紹介しますので、楽しみにお待ちください。

※例えば、L の値として （塾生の人数） ÷ （クラスの数） などが考えられます。今回の例では L=100÷5=20 となります。