B - Trapezoid Sum
Bが解けなかったよ。。というわけで僕みたいなアホにもわかる解説を書いてみる。
計算量考慮しないといけないけど
これは数学の公式を覚えてるか、変動する上限下限に対応できるいもす法を知ってるかじゃないとなので、まあいまのレベルじゃ無理っぽい。
(これの回答をいもす法で解くのもいい機会なので、勉強してまた後でメモります。)
n~m
の範囲での和を求める式
これだけですよ?こんなん知らん。。笑
詳しくは下記で!
mathwords.net
で、これはわかったんですが、解説を見ると、
って式も登場してます。これは何か?ってのがいまいちよくわかりませんでした。
しかし、これはサンプルを考えればすぐわかります。
3 5
のインプットがきたとき、
1-3の和は1,2,3の6
です。
3-5の和は3,4,5の12
です。
しかし、例えば5
を上記の式に当てはめると、で15
となり、回答に必要の無い1,2(和:3)
も含まれてしまいます。
この余分な1,2の和を求めるために式に当てはめると、 となります。
これは、右と同意になります。
そのため、 3-5
のような範囲の和を求める場合は、となるわけですね〜〜〜
あとは、これを回数分ループし、足し合わせていくだけです。
import java.util.Scanner; public class Main201 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); long ans = 0; for(int i=0; i<n; i++) { long a = sc.nextLong(); long b = sc.nextLong(); ans += b*(b+1)/2 - (a-1)*a/2; } System.out.println(ans); } }