二分探索法の応用～クラス分けをしてみよう

第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 人にする方法があるため、残念ながら最適な答えを出すことができていません。