全探索

問題

白・青・赤の３枚のカードがあります。

それぞれのカードに $ 1 $ 以上 $ N $ 以下の整数を書きます。

３枚のカードの合計を $ K $ 以下にするような書き方は何通りあるか求めてください。

[制約]
🔹$ 1 \leqq N \leqq 3000 $
🔹$ 3 \leqq K \leqq 9000 $

解き方・ソースコード

この問題を解く方法として３枚のカードの書き方を全探索することが考えられます。

ただしこの方法だと計算量が $ O(N^3) $ となり制約の上限 $ N=3000 $ の場合、270億通りを調べる必要があり計算にとても時間がかかってしまいます。

そこで計算量を減らすために２枚のカードが決まれば残りの１枚が決まるという方法をとります。

🔹白色のカードに書き込む整数を $ x $ とする。
🔹青色のカードに書き込む整数を $ y $ とする。
🔹赤色のカードに書き込む数字は $ K - x - y $ となる。

この方法ですと３枚全部ではなく２枚の書き方のみを全探索するという解法が成り立ちます。

計算量は $ O(N^2) $ であり、十分に実行が可能です。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#--------- 入力例1 ---------
N = 3   # カードに記入できる数字の最大値
K = 6   # 合計値
#--------- 入力例2 ---------
# N = 3000   # カードに記入できる数字の最大値
# K = 4000   # 合計値
#---------------------------
Answer = 0
# 全探索
for x in range(1, N + 1):
    for y in range(1, N + 1):
        z = K - x - y
        if z >= 1 and z <= N:
            Answer += 1

# 出力
print('解：', Answer)

[実行結果（入力例1）]

解： 7

合計を6にする方法は次の7種類あります。

白青赤
321
312
231
222
213
132
123

[実行結果（入力例2）]

解： 6498498