NoiminのNoise

競技プログラミング (多め) とWeb (たまに) ,自然言語処理 (ブログではまだ)。数式の書き方を一気に KaTeX に変えようとして記事を全削除してインポートし直すなどしたので,過去にブックマークされた記事は URL が変わってしまっている可能性があります…….

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

問題文: C - スペースエクスプローラー高橋君

公式解説: https://img.atcoder.jp/colopl2018-final/editorial.pdf

問題概要

長さ $N \leq 10^5$ の整数列 $a_1, a_2, \cdots, a_N (a_i \leq 10^{12}) $ が与えられる.

各 $i (1 \leq i \leq N)$ について, $\min_j (a_j + (i-j)^2)$ を求めよ.

解法概要

Convex-Hull Trick を使わずに解いてみます. Convex-Hull Trick 解はこちら

サンプルの計算を表にしてみます.

f:id:noimin:20200126235809j:plain
Sample 3 を手計算した表

丸をつけたのが各行の最小値です.なんとなく左上から右下に最小値が移動している気がしますが,証明しておきます.

最小値が左下から右下へと移動するとは限らない場合というのは,最小値が左下 (右上) から右上 (左下) に移動するような場合が存在するということです.このような場合が存在しないことを背理法で示します. 証明が誤っていたので,正しい証明ができるまで非表示にしておきます.

「最小値は左上から右下へ動く」場合に使える高速化テクとして,最小値を取り得ない部分を削りながら再帰的に最小値を埋めていく方法があります.monotone minima などと呼ばれているようです.

monotone minima については以下の記事がわかりやすかったです.

  • 図などで概要を抑える

ferin-tech.hatenablog.com

topcoder.g.hatena.ne.jp

このテクを使うと全体の時間計算量が $O(N \log N)$ に抑えられます.すごい.

ソースコード

#include <iostream>
#include <vector>

using namespace std;

using ll =  long long;

constexpr ll LINF = 1LL << 60;
constexpr int N_MAX = 200000;

int n;
vector<ll> a(N_MAX);
vector<ll> b(N_MAX, LINF);  // i番目のキャノンを使うときの最小値
vector<ll> bj(N_MAX, -1);  //  b[i] をとるjの値

void rec(int si, int sj, int ti, int tj) {
    if(si >= ti || sj >= tj) return;

    ll mi = (si+ti)/2;
    for(ll j=sj;j<tj;++j) {
        if(b[mi] > a[j] + (j-mi)*(j-mi)) {
            b[mi] = a[j] + (j-mi)*(j-mi);
            bj[mi] = j;
        }
    }

    rec(si, sj, mi, bj[mi]+1);
    rec(mi+1, bj[mi], ti, tj);
}

int main() {
    cin >> n;
    for(int i=0;i<n;++i) cin >> a[i];
    rec(0, 0, n, n);
    ll j = bj[0];
    for(ll i=0;i<n;++i) {
        if(b[i] == LINF) {
            b[i] = a[j] + (j-i) * (j-i);
        } else {
            j = bj[i];
        }
        cout << b[i] << endl;
    }
}

所感

これも rsk0315 さんに勧めてもらった問題.monotone minima を学んだ.線形で解く方法もあるらしい.