問題
白・青・赤の3枚のカードがあります。
それぞれのカードに $ 1 $ 以上 $ N $ 以下の整数を書きます。
3枚のカードの合計を $ K $ 以下にするような書き方は何通りあるか求めてください。
[制約]
🔹$ 1 \leqq N \leqq 3000 $
🔹$ 3 \leqq K \leqq 9000 $
解き方・ソースコード
この問題を解く方法として3枚のカードの書き方を全探索することが考えられます。
ただしこの方法だと計算量が $ O(N^3) $ となり制約の上限 $ N=3000 $ の場合、270億通りを調べる必要があり計算にとても時間がかかってしまいます。
そこで計算量を減らすために2枚のカードが決まれば残りの1枚が決まるという方法をとります。
🔹白色のカードに書き込む整数を $ x $ とする。
🔹青色のカードに書き込む整数を $ y $ とする。
🔹赤色のカードに書き込む数字は $ K - x - y $ となる。
この方法ですと3枚全部ではなく2枚の書き方のみを全探索するという解法が成り立ちます。
計算量は $ O(N^2) $ であり、十分に実行が可能です。
[Google Colaboratory]
1 | #--------- 入力例1 --------- |
[実行結果(入力例1)]
解: 7
合計を6にする方法は次の7種類あります。
白 | 青 | 赤 |
---|---|---|
3 | 2 | 1 |
3 | 1 | 2 |
2 | 3 | 1 |
2 | 2 | 2 |
2 | 1 | 3 |
1 | 3 | 2 |
1 | 2 | 3 |
[実行結果(入力例2)]
解: 6498498