COLOCON -Colopl programming contest 2018- Final C - スペースエクスプローラー高橋君
問題ページ
C - スペースエクスプローラー高橋君
CHTで解いてたけどmonotone minimaで解けるらしいので解くことにした
考えたこと
- f(i,j) = (i番のキャノンで区画jを破壊するエネルギー)
- 最小値がどんどん右下に移動していくのはそれはそう
- monotone minimaが成り立っているっぽい
- 貼ると通る Totally Monotone Matrix Searching (SMAWK algorithm) - 週刊 spaghetti_source - TopCoder部
#include <bits/stdc++.h> using namespace std; using ll = long long; #define int ll using VI = vector<int>; using VVI = vector<VI>; using PII = pair<int, int>; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) #define ALL(x) x.begin(), x.end() #define PB push_back const ll LLINF = (1LL<<60); const int INF = (1LL<<30); const int MOD = 1000000007; template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); } template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); } template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; } template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); } template<class S,class T> ostream &operator <<(ostream& out,const pair<S,T>& a){ out<<'('<<a.first<<','<<a.second<<')'; return out; } template<class T> ostream &operator <<(ostream& out,const vector<T>& a){ out<<'['; REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';} out<<']'; return out; } int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // monotone minima // O(NlogN) // verify: https://beta.atcoder.jp/contests/colopl2018-final-open/tasks/colopl2018_final_c const int MAX_N = 200010; int minima[MAX_N]; int a[MAX_N]; int f(int i, int j) { return a[j] + (j-i)*(j-i); } void monotoneMinima(int ib, int ie, int jb, int je) { if(ib > ie) return; if(ib == ie) { int jm = jb; int fm = f(ib, jm), fj; for(int j=jb+1; j<=je; ++j) { if(fm > (fj = f(ib, j))) { fm = fj; jm = j; } } minima[ib] = jm; return; } int im = (ib+ie)/2; monotoneMinima(im, im, jb, je); monotoneMinima(ib, im-1, jb, minima[im]); monotoneMinima(im+1, ie, minima[im], je); } signed main(void) { int n; cin >> n; REP(i, n) cin >> a[i]; monotoneMinima(0, n-1, 0, n-1); REP(i, n) cout << f(i, minima[i]) << endl; return 0; }