Codeforces #217 Div2. E. Summer Reading

方針はともかくえらく実装が面倒だった。
http://codeforces.com/contest/370/problem/E

問題

以下の条件を満たす整数列を考える。

• 先頭要素は1から始まり、隣接要素は同じ値かもしくは1増える
• 同じ数字は、2～5個の範囲でなければならない。

整数列のうち幾つかの要素が指定された場合、上記条件を満たす整数列が構築可能なら、そのうち最大要素が最大である数列を示せ。

解法

要素が指定されたindexを昇順にDPしていく。
状態としては、各indexまでにその数値は何回使われているか。

i番目の要素A[i]の次に指定されているのがj番目の要素A[j]の時、A[i]～A[i+4]までは同じ要素である可能性があり、同様にA[j-4]～A[j]からA[j]までは同じ要素である可能性がある。
A[i]～A[i+x]が同じ要素で、A[j-y]～A[j]が同じだとすると、間の要素A[i+x+1]～A[j-y-1]は*1個あり、その間の数値は(A[i]+1)～(A[j]-1)個登場するので、要素数が数字の種類の２倍～５倍に収まるかを確かめていけばよい。

最後にDPの経路復元を行う。
※I fixed a mistakes int the code. Thank you for teach me, FrankSong!

int N,A[300000];
int state[6][300000];
vector<int> P;

void solve() {
	int f,i,j,k,l,x,y;
	
	P.push_back(0);
	cin>>N;
	FOR(x,N) {
		cin>>A[x+1];
		if(A[x+1]) P.push_back(x+1);
	}
	if(P.size()==1) {
		_P("%d\n",N/2);
		FOR(i,N/2) _P("%d %d ",i+1,i+1);
		if(N%2) _P("%d",N/2);
		_P("\n");
		return;
	}
	
	state[5][0]=1;
	for(i=1;i<P.size();i++) {
		if(A[P[i-1]]>A[P[i]]) return _P("-1\n");
		if(A[P[i-1]]==A[P[i]]) {
			for(x=P[i-1]+1;x<P[i];x++) A[x]=A[P[i]];
			for(y=1;y<=5;y++) if(state[y][P[i-1]] && y+(P[i]-P[i-1])<=5) state[y+(P[i]-P[i-1])][P[i]] |= 1<<y;
		}
		else {
			FOR(x,5) for(y=1;y<=5;y++) {
				l=P[i]-P[i-1]-x-y;
				if(l>=2*(A[P[i]]-A[P[i-1]]-1) && l<=5*(A[P[i]]-A[P[i-1]]-1)) {
					for(j=1;j<=5;j++) if(state[j][P[i-1]] && x+j>=2 && x+j<=5) state[y][P[i]] |= 1<<(x*6+j);
				}
			}
		}
	}
	
	int r=0;
	for(x=1;x<=5;x++) {
		if(state[x][P.back()]==0) continue;
		y=N-P.back();
		if(x==1 && y==0) continue;
		if(x==1) y--;
		if(x==5 && y==1) continue;
		y=A[P.back()]+y/2;
		if(y>r) l=x,r=y;
	}
	if(r==0) return _P("-1\n");
	
	_P("%d\n",r);
	x=P.back()+1;
	if(l==1) A[x]=A[x-1],x++;
	if((N-x+1)%2) A[x]=A[x-1],x++;
	while(x<N) A[x]=A[x+1]=A[x-1]+1,x+=2;
	
	for(i=P.size()-1;i>0;i--) {
		if(A[P[i-1]]==A[P[i]]){ l-=P[i]-P[i-1]; continue;}
		FOR(x,l) A[P[i]-x]=A[P[i]];
		FOR(x,30) if(state[l][P[i]] & (1<<x)) {
			y=x/6;
			FOR(j,y) A[P[i-1]+j+1]=A[P[i-1]];
			for(j=P[i-1]+y+1;j<=P[i]-l;j++) {
				A[j]=A[P[i-1]]+1+ (A[P[i]]-(A[P[i-1]]+1))*(j-(P[i-1]+y))/(P[i]-l+1-(P[i-1]+y));
			}
			l=x%6;
			break;
		}
	}
	FOR(x,N) _P("%d ",A[x+1]);
	_P("\n");
}

まとめ

意外と実行時間はかからなかった。

*1:j-y)-(i+x+1