競プロで水色を取得するため、下記サイトを順次進めている。
AtCoder 版!蟻本 (初級編)
全探索の練習問題である ABC 051 B Sum of Three Integers に取り組んでいるのだが、まともにforで回していたら実行時間制限に引っかかる。
最初のコード
問題文は上記を確認していただくとして、一番最初のコードはこちら。
K, S = map(int, input().split())
count = 0
for x in range(0, K+1):
for y in range(0, K+1):
for z in range(0, K+1):
if x+y+z == S:
count += 1
print(count)
案の定実行時間制限に引っかかった。
改善1
と、いうことで改善してみた。
Sに一致するようなzの値はx, y, Sから一通りだけ求まるので、敢えて条件に合致しないzを計算する必要がない。
そこで、こんな感じに書き換えた。
K, S = map(int, input().split())
count = 0
for x in range(0, K+1):
for y in range(0, K+1):
z = S-x-y
if x + y + z == S and 0 <= z <= K:
count += 1
print(count)
if文の条件式を見ていただきたい。
条件を満たすようなzは既に計算済みで、and条件に含める必要はないのに敢えて書いているのだ!!
とはいえ、大して計算速度に影響しないだろうと希望的観測で提出してみたところ、実行時間制限に引っかかった。
参考に実行時間制限に引っかからずアクセプトされたテストデータの最大時間は
subtask_1_03.txt: 1984 ms
であった。
改善2
単純に冗長な条件を消した。
K, S = map(int, input().split())
count = 0
for x in range(0, K+1):
for y in range(0, K+1):
z = S-x-y
if 0 <= z <= K:
count += 1
print(count)
このコードはアクセプトされたのだが、先程と同じテストデータの実行時間は
subtask_1_03.txt: 1235 ms
となり。700msほど短い。
たった1つ冗長な条件を外すだけで700msも短くなるとは、、、。