固定して全探索

問題

N 人の生徒がいます。

各生徒には体力と気力を表す整数値が定めてられており、生徒 i(1≦i≦N) の体力は Ai、気力は Bi です。

生徒のうち何人かを選んでバスケットボールをすることにしました。

もし参加者のレベル差が大きい場合、一部の人だけが活躍してもつまらないので、次の条件を満たすようにすることにしました。

🔹どの２人の参加者も、体力の差が K 以下である。
🔹どの２人の参加者も、気力の差が K 以下である。

最大何人でバスケットボールをすることができるのかを求めて下さい。

[制約]
🔹1≦N≦300
🔹1≦K≦100
🔹1≦Ai≦100
🔹1≦Bi≦100

解き方・ソースコード

この問題では、参加者の選び方を 2N 通り全探索する方法が思いつきますが、計算量を考えると現実的ではありません。

そこで、参加者の体力の下限値 a、参加者の気力の下限値 b を仮に決めてみます。

このとき、以下の２つの条件を満たす生徒だけがバスケットボールに参加することができます。

🔹体力が a 以上 a+K 以下である。
🔹気力が b 以上 b+K 以下である。

整数の組 (a,b) を全探索し、その中で参加可能な生徒数が最大となるものを解とします。

制約から Ai,Bi とも 100以下ですので、(a,b) の組としては 100×100=10000 通りを全探索すれば十分だということになります。

単純に全探索すると計算量が膨大になってしまう問題でも、何を全探索するか（どの値を固定して考えるか）を変えるだけで、とても効率がよくなることがあります。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#--------- 入力例 ----------
N = 4       # 生徒数
K = 30      # 体力と気力の差
A = [20, 10, 50, 30]    # 生徒の体力
B = [30, 40, 10, 60]    # 生徒の気力
#---------------------------
# 整数の組 (a, b) が決まったときの、参加可能な生徒数を求める
def GetScore(a, b, A, B, K):
    cnt = 0
    for i in range(N):
        if a <= A[i] <= a + K and b <= B[i] <= b + K:
            cnt += 1
    return cnt
# (a, b) の組を全探索
Answer = 0
for a in range(1, 101):
    for b in range(1, 101):
        Score = GetScore(a, b, A, B, K)
        Answer = max(Answer, Score)
# 出力
print('解：', Answer)

[実行結果]

解： 3

上記の入力例だと、最大3人の生徒が参加できるということが分かりました。