Codeforces #860 : Div2 E. Multitest Generator

本番中に解き切れず。
https://codeforces.com/contest/1798/problem/E

問題

数列Bがtestであるとは、B[0]=|B|-1であることをいう。
BがMultitestであるとは、B[1...|B|-1]をB[0]個に分割したとき、それぞれがtestであることをいう。

数列Aが与えられる。Aの各suffixに対し、それがMultitestであるためには最小何要素書き換えればよいか求めよ。

解法

B[0]=1、B[1]=|B|-2とするとこれはMultitestなので、解は2以下である。
あとは、0,1要素の書き換えで良いか判定すればよい。

Aのsuffixを短い順に処理していく。
A[i]を先頭としてAのsuffixをtestの連結とするとき、何要素書き換えればよいかを管理しよう。
その値があれば、A[i-1]を先頭とする場合の解が容易に求められる。

int T,N,A[303030];
int C[303030],F[303030];
int ret[302020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) cin>>A[i];
		set<int> S={0};
		for(i=N-1;i>=1;i--) {
			x=i+A[i]+1;
			F[i]=*S.rbegin()+1;
			if(x>N) C[i]=-1<<20;
			else if(x==N) C[i]=1;
			else {
				C[i]=C[x]+1;
				F[i]=max(F[i],F[x]+1);
			}
			
			if(C[i]==A[i-1]) {
				ret[i-1]=0;
			}
			else if(C[i]>=1) {
				ret[i-1]=1;
			}
			else if(F[i]>=A[i-1]) {
				ret[i-1]=1;
			}
			else {
				ret[i-1]=2;
			}
			
			S.insert(C[i]);
		}
		FOR(i,N-1) cout<<ret[i]<<" ";
		cout<<endl;
	}
}

まとめ

問題設定がややこしくてなんか面倒な問題。