問題
N 人の生徒がいます。
各生徒には体力と気力を表す整数値が定めてられており、生徒 i(1≦i≦N) の体力は Ai、気力は Bi です。
生徒のうち何人かを選んでバスケットボールをすることにしました。
もし参加者のレベル差が大きい場合、一部の人だけが活躍してもつまらないので、次の条件を満たすようにすることにしました。
🔹どの2人の参加者も、体力の差が K 以下である。
🔹どの2人の参加者も、気力の差が K 以下である。
最大何人でバスケットボールをすることができるのかを求めて下さい。
[制約]
🔹1≦N≦300
🔹1≦K≦100
🔹1≦Ai≦100
🔹1≦Bi≦100
解き方・ソースコード
この問題では、参加者の選び方を 2N 通り全探索する方法が思いつきますが、計算量を考えると現実的ではありません。
そこで、参加者の体力の下限値 a、参加者の気力の下限値 b を仮に決めてみます。
このとき、以下の2つの条件を満たす生徒だけがバスケットボールに参加することができます。
🔹体力が a 以上 a+K 以下である。
🔹気力が b 以上 b+K 以下である。
整数の組 (a,b) を全探索し、その中で参加可能な生徒数が最大となるものを解とします。
制約から Ai,Bi とも 100以下ですので、(a,b) の組としては 100×100=10000 通りを全探索すれば十分だということになります。
単純に全探索すると計算量が膨大になってしまう問題でも、何を全探索するか(どの値を固定して考えるか)を変えるだけで、とても効率がよくなることがあります。
[Google Colaboratory]
1 | #--------- 入力例 ---------- |
[実行結果]
解: 3
上記の入力例だと、最大3人の生徒が参加できるということが分かりました。