固定して全探索

問題

$ N $ 人の生徒がいます。

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

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

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

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

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

[制約]
🔹$ 1 \leqq N \leqq 300 $
🔹$ 1 \leqq K \leqq 100 $
🔹$ 1 \leqq A_i \leqq 100 $
🔹$ 1 \leqq B_i \leqq 100 $

解き方・ソースコード

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

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

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

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

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

制約から $ A_i, B_i $ とも $ 100 $以下ですので、$ (a,b) $ の組としては $ 100 \times 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人の生徒が参加できるということが分かりました。