COLOCON 2018 final C - スペースエクスプローラー高橋君
問題概要
N個の整数 {a_i} (i=1,2,..,N) が与えられる.
各 i = 1,2,..,N について min_(1<=j<=N) (a_j + (j-i)2) を求めよ.
1 <= N <= 2*105, 1 <= a_i <= 1012
解法
a_j + (j-i)2 = i2 + (-2ji + j2 + a_j) より,
各iについて, (-2ji + j2 + a_j)を最小化すれば良い.
これはiの一次関数なため,Convex Hull Trickを使って全体でO(N)でできる.
簡単に言うと,最小値を達成する区間があるような直線を
傾きで降順ソートして持っておき,(今回の場合は-2iがそのまま降順になっているためソート不要)
左から走査していくと各直線を毎回見る必要はないと言うもの.
詳しい解説はこことか.
メモ
Convex Hull Trickを知らなかったので今度からできるように.
コード
#include "bits/stdc++.h" #define ALL(g) (g).begin(),(g).end() #define REP(i, x, n) for(int i = x; i < n; i++) #define rep(i,n) REP(i,0,n) #define RREP(i, x, n) for(int i = x; i >= n; i--) #define rrep(i, n) RREP(i,n,0) #define pb push_back using namespace std; using ll = long long; using P = pair<int,int>; const int mod=1e9+7,INF=1<<30; const double EPS=1e-12,PI=3.1415926535897932384626; const ll LINF=1LL<<60, lmod = 1e9+7; const int MAX_N = 100005; template<class Data> struct ConvexHullTrick { deque<pair<Data, Data>> l; bool check(pair<Data, Data> l3) { // l2(lの末尾)が不必要か const auto l1 = *prev(end(l), 2); const auto l2 = *prev(end(l), 1); Data a = (l2.first - l1.first) * (l3.second - l2.second); Data b = (l2.second - l1.second) * (l3.first - l2.first); return a >= b; } bool empty() const { return l.empty(); } void add(Data a, Data b) { // 傾きが単調減少するように if (!empty()) assert (l.back().first >= a); pair<Data, Data> n(a, b); while ((int)l.size() >= 2 && check(n)) l.pop_back(); l.emplace_back(n); } Data f(int k, Data x) { return l[k].first * x + l[k].second; } Data minimum(Data x) { // xが単調増加するように assert (!empty()); while ((int)l.size() >= 2 && f(0, x) >= f(1, x)) l.pop_front(); return f(0, x); } }; ConvexHullTrick<ll> cht; int main(){ int N; cin >> N; for(ll j = 1LL; j <= ll(N); j++){ ll a; scanf("%lld",&a); cht.add(-2*j,j*j+a); } for(ll i = 1LL; i <= ll(N); i++){ cout << i*i+cht.minimum(i) << endl; } return 0; }