ITP1_7_B How many ways?の問題の解説を復習としてまとめようと思い書いていきます。
ここからアクセスできます。
①考え方
1~nまでの数の中から重複のないように3つ選び、その総和がxになったケースを数えるプログラムを書くことでACになります。
ではどのようにしたらよいでしょうか？
ここで真っ先に思いついて欲しいのが
全探索 !!
これを使うことで解くことができます。
あと考えやすいっていうのもありますね。
ではここから全探索を使って考えていきましょう！
整数i, j, kを用意します。
どのように探索するかと言いますと
1 <= i <= n,
i+1 <= j <= n,
j+1 <= k <= n
の範囲を探索します。
その中でi+j+k = xになるケースを数えることで解くことが出来ました。
jとkはなんで1からじゃないの？って話なんですが、重複なしで選びたいので、 i < j < kとなるようにしておきたいからです。
でここからなんですが、もっと軽くしたい（計算量を小さくしたい）と思います。
どのようにするかというと、
kを探索しないようにすることです。
えっ、どういうこと？って思いますよね。
でもできるんです。
このことにお気づきでしょうか？
i, j, xが決まっているのでkは一意に定まる
ということです。
なのでkを求めてそれがj < k <= nであるケースを数えることでACになります。
よって、O(N^3) → O(N^2)に軽くすることができました。
最初に解説したものはsolution1に、先程解説したものはsolution2に実装例が載っています。言語はPythonです。
②提出したコード
solution1
ans = 0
while True:
n, x = map(int, input().split())
if n == 0 and x == 0:
break
for i in range(1, n+1):
for j in range(i+1, n+1):
for k in range(j+1, n+1):
if i + j + k == x:
ans += 1
print(ans)
ans = 0
solution2
ans = 0
while True:
n, x = map(int, input().split())
if n == 0 and x == 0:
break
for i in range(1, n):
for j in range(i+1, n):
k = x - i - j
if i < j < k and k <= n:
ans += 1
print(ans)
ans = 0
③まとめ
この問題は全探索とはどんなものかというのを理解するのにとっておきの問題だと思いますので、是非解いてみてください。参考文献に問題のリンクと自分がよく閲覧している記事を紹介しておきます。
④参考文献