これは本番解いておきたかったなぁ。
https://atcoder.jp/contests/arc130/tasks/arc130_e
問題
N要素の正整数列Aに対し、以下のように整数列Iを作る。
- Aの最小値を取る要素を1つ選び、そのindexをIに追加する。最小値を取る要素が複数ある場合、どれをとっても良い。
- その後、選んだ要素をインクリメントする。
こうして得られたIが与えられる。
そのようなIを生成できるAの初期値のうち、辞書順最小のものを求めよ。
解法
Editorialとは違うけど、賢いなと思った方を見かけたので紹介。
Iを、各要素I[i]を選んだ時の値A[I[i]]が等しい状態毎に、複数の区間に区切ることを考える。
その場合、以下を満たさなければならない。
- 区間内で同じindexは1回しか登場しない。
- 最後の区間を除くと、手前の区間に登場するindexの集合は、そのあとの区間に登場するindexの集合の部分集合である。
- 複数の区切り方がある場合、最後の区間が短いほど良い
これを踏まえて以下を考える。
f(k) := Iのprefix k要素までを見たとき、k要素目と(k+1)要素目の間に上記の区切りが作れるかの真偽値
最後の条件より、f(k)=Trueとなる最大のkを選びたい。
f(k)がTrueとなるのは以下の場合。
Iのprefix k個に現れるuniqueなindexがm個とすると、I[(k-m)....(k-1)]の各要素がそのuniqueなm個になっていて、かつf(k-m)がTrueの場合である。
あとはf(k)=Trueとなる最大のkを選べば、k回処理を行った時点でAの全要素は等しいため、そこからIにそって巻き戻すことでAの初期値を得られる。
int N,K; int I[303030]; int las[303030]; int C[303030]; int num[303030]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>K; int uni=0; int pre=0; ok[0]=1; for(i=1;i<=K;i++) { cin>>I[i]; x=--I[i]; if(las[x]==0) uni++; pre=max(pre,las[x]); las[x]=i; if(i-pre==uni) num[i]=num[pre]+1; else num[i]=1<<30; } int minnum=1<<20; int tar=-1; for(i=pre;i<=K;i++) if(num[i]<=minnum) minnum=num[i], tar=i; if(tar==-1) { cout<<-1<<endl; } else { int mi=0; for(i=1;i<=tar;i++) { C[I[i]]--; mi=min(mi,C[I[i]]); } FOR(i,N) cout<<(C[i]-(mi-1))<<" "; cout<<endl; } }
まとめ
近いようなところまでは行ったけど、詰め切れなかった。