ABC解説

【pythonでABC181を解説】B - Trapezoid Sum

問題概要

問題ページ

B - Trapezoid Sum
B - Trapezoid Sum

問題ページへ移動する

問題文

何も書かれていない黒板があります。
高橋くんは \(N\) 回の操作を行い、黒板に整数を書きます。

\(i\) 回目の操作では、 \(A_i\) 以上 \(B_i\) 以下の整数すべてを \(1\) 個ずつ、合計 \(B_i - A_i + 1\) 個の整数を書きます。

\(N\) 回の操作を終えたときの、黒板に書かれた整数の合計を求めてください。

制約

  • 入力はすべて整数
  • \(1 \leq N \leq 10^5\)
  • \(1 \leq A_i \leq B_i \leq 10^6\)

問題の考察

制約が

  • \(1 \leq N \leq 10^5\)
  • \(1 \leq A_i \leq B_i \leq 10^6\)

と大きいのでfor文で全て計算すると間に合わない。

連続する数の和は、等差数列の和の公式で求めれば計算量\(O(1\))で求められる。

等差数列の公式の和

\(等差数列の和=\)\(\displaystyle \frac{項数(初項+末項)}{2}\)\(=\)\(\displaystyle \frac{(b_i - a_i + 1)(a_i+b_i)}{2}\)

各\(a_i,b_i\)に対して、等差数列の和の公式で合計を求めたものを合計したものを出力すれば良い。

たびすけ
たびすけ
等差数列の和の公式は競技プログラミングでも頻繁に使用するので覚えておきましょう！

ACコード

import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    t = 0
    for i in range(n):
        a, b = list(map(int, input().rstrip('\n').split()))
        t += (b - a + 1) * (a + b) // 2
    print(t)


if __name__ == '__main__':
    solve()

-ABC解説
-