AtCoder ABC 214 B – How many? Python解説

スポンサーリンク

How many?

a+b+c≤S かつ a×b×c≤T を満たす非負整数の組 (a,b,c) はいくつありますか?

AtCoder Beginner Contest「How many?」

問題の条件を満たす組み合わせの数を求めたいので、全探索をしていきます。
探索する範囲はa + b + c <= Sまでですが、今回は3重ループを使うので、少しでも計算量を抑えるべく、1番目のループはs + 1、2番目のループはs – a + 1、3番目のループはs – ( a + b) + 1と探索する範囲を工夫していきます。

s, t = map(int, input().split())

cnt = 0

for a in range(s + 1):
    for b in range(s - a + 1):
        for c in range(s - (a + b) + 1):
            if a + b + c <= s and a * b * c <= t:
                cnt += 1
            else:
                break

print(cnt)

先述した通り、3重ループを使っての全探索をしていきます。
あとは、if a + b + c <= s and a * b * c <= tの条件を満たす数を調べて完了です。

AtCoderB問題

Posted by cheese