AGC029 C - Lexicographic constraints
ICPCっぽさを感じるね。
考察
二部探索をする、「K種類の文字で実現可能か」について考える。
愚直にやろうとすると10＾9桁考えなくてはいけなくなるのでRun Lengthといわれる(であろう)実装をする。
aaabbbabbccbbbb
を
a3b3a1b2c2b4
とかく奴です。
実際'a'は最下位のとき以外省略するみたいな書き方をしています。
コード
#include <bits/stdc++.h> using namespace std; #define REP(i,n) for(ll (i) = (0);(i) < (n);++i) #define REV(i,n) for(ll (i) = (n) - 1;(i) >= 0;--i) #define PB push_back #define EB emplace_back #define MP make_pair #define FI first #define SE second #define SHOW1d(v,n) {REP(WW,n)cerr << v[WW] << ' ';cerr << endl << endl;} #define SHOW2d(v,WW,HH) {REP(W_,WW){REP(H_,HH)cerr << v[W_][H_] << ' ';cerr << endl;}cerr << endl;} #define ALL(v) v.begin(),v.end() #define Decimal fixed<<setprecision(20) #define INF 1000000000 #define LLINF 1000000000000000000LL #define MOD 1000000007 typedef long long ll; typedef pair<ll,ll> P; bool naoppy(vector<ll> &v, ll mid) { vector<P> now; now.EB(0,-1); REP(i,v.size()){ if(now.back().FI < v[i]){ now.EB(v[i],0); } else { if(mid <= 1)return false; while(now.back().FI > v[i])now.pop_back(); if(now.back().FI < v[i])now.EB(v[i],0); int tmp = now.back().FI; int top = now.back().FI; while(now.back().FI == top && now.back().SE == mid - 1){ top = now.back().FI - 1; now.pop_back(); } if(now.back().FI != top)now.EB(top,0); now.back().SE++; if(now.back().FI != tmp)now.EB(tmp,0); if(now.front().SE > -1)return false; } //REP(i,now.size())cout << "(" << now[i].FI << "," << now[i].SE << ") ";cout << endl; } return true; } int main(){ ll n;cin >> n; vector<ll> v(n); REP(i,n)cin >> v[i]; ll l = 0; ll r = 222222; while(r - l > 1){ ll mid = (l + r) / 2; if(naoppy(v,mid))r = mid; else l = mid; } cout << r << endl; return 0; }
上のコードについて、入力が
10 2 2 3 3 3 2 2 2 1 2
で、K = 3の時を見てみると、コメントされたところは
(0,-1) (2,0) (0,-1) (2,1) (0,-1) (2,1) (3,0) (0,-1) (2,1) (3,1) (0,-1) (2,1) (3,2) (0,-1) (2,2) (0,-1) (1,1) (2,0) (0,-1) (1,1) (2,1) (0,-1) (1,2) (0,-1) (1,2) (2,0)
と出力される。(a, b)はa番目の文字がbというもの、書いていない桁はb=0です。
文字に置き換えると
aa ab aba abb abc ac ba bb c ca
という感じでK=3で達成可能とわかる。
この実装では0桁目が-1でなくなったら失敗となります。
