JOI Kakisemi Contest 2019：E - 偏りの無いビル

問題

https://www.hackerrank.com/contests/joi-kakisemi-contest-2019/challenges/challenge-2156

解法

小課題１

|H_1 - H_2| >= 2 を判定すればよい．

小課題３

N <= 2000, A_i <= 30 より全探索で解ける．O(N^2)．

あとの小課題は A_i <= 10^9 となるので座標圧縮をしたい．ここで，差が 1 のところはそのまま，2 以上のところは差が 2 になるように座標圧縮をする．これで O(N^2) まで計算量を落とすことができる．

小課題５

A_i <= A_(i + 1) より A は単調増加．差が 2 以上であるところで区切ると，この区切った境界を挟んだ部分列は答えに含まれない．よって，境界間で答えを数える．各境界間の区間の長さを l とすると，C(l, 2) + l がその区間での答えになる部分列の個数となる．この和を求めればよい．

小課題６

{ A } = (2, 4, 3, 6, 6, 3, 5, 2) を考える．max = 6, min = 2, 種類数 cnt = 5 であるから，答えは (max - min) - cnt = -1 ．これが答えとなる必要十分条件になる．

部分列の左端 L を固定して考える．部分列の右端 R を右に動かしていったとき，max, min, 種類数 が更新されるのは新しい数が出現するときのみ．なので，新しい数がどの位置で出現するのかを求めればよい．O(N * 30 * logN)．

小課題７～９

(max - min - cnt) を記録していくことを考える．ある数が出現したとき，その数が出現した位置よりも後の区間の (max - min - cnt) の値が全て +1 される．これを Range-Add のセグ木におく．ここで，区間更新した区間の数だけこれより先に加算しなければいけなくなる区間の数は減る．なので，区間更新の回数は 2 * N に抑えられる．遅延セグ木を使うと O(NlogN) になる．これを定数倍高速化すると満点が得られる．