スペースエクスプローラー高橋君 [COLOCON -Colopl programming contest 2018- Final C]

https://beta.atcoder.jp/contests/colopl2018-final-open/tasks/colopl2018_final_c

前提知識

• CHT : Convex Hull Trick

解法

https://beta.atcoder.jp/contests/colopl2018-final-open/submissions/1997374

今回の問題はCHTを知っていれば解ける。
各iについて全てのjについての「a[j] + (j - i)^2」の最小値が答えになる。
a[j] + (j - i)^2 = a[j] + j^2 - 2ij + i^2
と変形ができる。ここでjで変化するのは「-2ji + (a[j] + j^2)」の部分。
これはiについて1次関数の形になる。
よって、N個の１次関数があり、全ての１次関数のiに値を代入した時の最小値が高速に得られればいい。
これはCHTそのままである。
その為、CHTに「-2ji + (a[j] + j^2)」を全部入れて、iを代入した時の最小値をそれぞれ求めて答えるだけ。

int N;
ll A[201010];
CHT<ll> cht;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    cht.init(N);
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, N) cht.add(-2 * i, A[i] + 1LL * i * i);
    rep(i, 0, N) {
        ll ans = cht.get(i) + 1LL * i * i;
        printf("%lld\n", ans);
    }
}