kmjp's blog

競技プログラミング参加記です

AtCoder ARC #130 : E - Increasing Minimum

これは本番解いておきたかったなぁ。
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;
	}
}

まとめ

近いようなところまでは行ったけど、詰め切れなかった。