現在の目標
今日のおはなし
結論
計算方法が合っていても, 現実的な時間内に終わらないとダメ.
解いた問題
答えは出せるけど, 実行時間 2sec が満足できなかった解答
TLE_answer.py
# coding: utf-8
a, b, x = map(int, input().split())
cnt = 0
n = b - a + 1
for i in range(n):
if (a+i)%x==0:
cnt += 1
print(cnt)
総当たりだと, b が大きくなった時に制限時間内に処理が終わらず Out でした.
AC だった解答
解説をみたところ,
a 以上 b 以下の整数のうち条件を満たすものの個数を求める問題です．このような問題では，
「f(n) := 0 以上 n 以下の整数のうち条件を満たすものの個数」
と定義しておくと，答えは f(b)−f(a−1) で求まるので楽です．
とありました. 文章だけではよくわからなったので, 図示してみると理解できました（plantUML 使ってみたかっただけです↓）.
for 文で a ~ b の区間を総当たりするのではなく, b の個数から a の個数を引けば, 所望の範囲の個数が求められるという話ですね（日本語が正確でない点はご容赦ください）. 当然といえば当然のことです.
AC_answer.py
# coding: utf-8
a, b, x = map(int, input().split())
f_a = (a-1)//x + 1 if a>=1 else 0
f_b = b//x + 1
print(f_b - f_a)
いまはコード書くだけで楽しいのですが, 少しずつ実行時間にも気をつけないといけませんね.
むすび
制約を見て, 力技が通用するか確認しよう.