ABC162 D - RGB Triplets (400)
RGBの数の累積和を取る
それぞれの地点について自身をjとした場合に成り立つ組み合わせを累積和から求める
i,kの間隔を1つずつ広げていって条件を満たしていた場合は組み合わせの数から引く
成り立つ組み合わせは先にRGBのそれぞれの数の積でも求まるらしい
累積和を求めるところとそれぞれの地点で組み合わせの数を求めるところは$ O(N)
i,kの間隔を全て求めるのが$ O(N)でN回行うので$ O(N^2)でここが一番重い
問題: https://atcoder.jp/contests/abc162/tasks/abc162_d
提出: https://atcoder.jp/contests/abc162/submissions/11809922
#ABC162 #400pt #D #ABC #AtCoder
#O(N^2)