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 解はこちら
サンプルの計算を表にしてみます.
丸をつけたのが各行の最小値です.なんとなく左上から右下に最小値が移動している気がしますが,証明しておきます.
最小値が左下から右下へと移動するとは限らない場合というのは,最小値が左下 (右上) から右上 (左下) に移動するような場合が存在するということです.このような場合が存在しないことを背理法で示します. 証明が誤っていたので,正しい証明ができるまで非表示にしておきます.
「最小値は左上から右下へ動く」場合に使える高速化テクとして,最小値を取り得ない部分を削りながら再帰的に最小値を埋めていく方法があります.monotone minima などと呼ばれているようです.
monotone minima については以下の記事がわかりやすかったです.
- 図などで概要を抑える
- アルゴリズムの詳細を学ぶ
このテクを使うと全体の時間計算量が $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 を学んだ.線形で解く方法もあるらしい.