ABC181 B問題 Trapezoid Sum 算数の問題を解く

算数系の問題のABC181を解いて解説します。

A, Bという数字の組み合わせがN個あって、それぞれの組み合わせでA以上、B以下の整数を列挙します。
列挙した整数の合計を出力する問題です。

atcoder.jp

問題文のまま解こうとすると、A, Bの数字の組み合わせを読み込んで、
そこでA〜Bまでの整数が入った配列を作って、その配列の合計値を足すようなイメージです。

N = int(input())
ans = 0
for _ in range(N):
  l, u = map(int, input().split())
  ans += sum(range(l, u + 1))
print(ans)

そうすると0.2秒タイムオーバーになってしまいました。

Nの範囲がでAとBの範囲がなので、最悪のケースでは計算量がとかになりそうなので、無理ですね。

そこでAとBから計算して、合計値を求めることを考えます。
ここからは算数の問題です。
Aが18、Bが21の場合、まず2つの数列をイメージします。
18から21までの数列と逆順にした21から18までの数列です。
それを足し合わせると、18+21、19+20、20+19、21+18となって、39が並びます。
39が全部であるので、合計はとなります。

イメージ図

ということで、がAからBまでの数列を足した合計値になります。

N = int(input())
ans = 0
for _ in range(N):
  l, u = map(int, input().split())
  ans += int((l + u)*(u - l + 1) / 2)
print(ans)

簡単な算数の問題だったのですが、何も考えずタイムオーバーするコードを最初に書いてしまったのは反省。。。