Codeforces #384 Div2 E. Vladik and cards

想定解と異なりそう。
http://codeforces.com/contest/743/problem/E

問題

1～8で構成された数列がある。
以下の条件を満たす部分列のうち、最長の長さを答えよ。

• 1～8の登場回数の差は、それぞれ高々1まで。
• 同じ数字はすべて連続してあらわれる。

解法

自分は以下のようにした。

• next_permutationで1～8の登場順を総当たり
• まずは1～8の登場回数が等しい場合を考え、それぞれ可能な最大登場数を求める。
  • 1～8をそれぞれ登場回数を1増やすかどうかを2^8通り総当たりしながら、そのような数列が取れるかチェックする

各数字の登場順と登場回数がわかったとき、元の数列からそのような部分列が取り出せるか高速に判定できなければならない。
そのため自分は以下を前処理で作成した。
f(p,d,c) := 元の数列のp個目の要素まで抜き出すかどうか判定した状態で、以降数値dをc個とり出すには、最短で数列の何要素目までを取り込まなければならないか。

cはダブリングの要領で2の累乗のみ求めてもよいが、今回Nは1000と小さいので、O(N^2*D) (Dは数字の種類)で全部列挙した。
よって自分のコードは前処理でO(N^2*D)、本処理でO(D!*(N+2^D*D))程度かかる。(Nは最大登場数を1ずつデクリメントしながらチェックしているためで、二分探索すればlogNにできる)

int N;
int A[1010];
int nex[1010][8][130];
int V[10];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i+1], A[i+1]--;
	FOR(i,8) nex[N][i][1]=nex[N+1][i][1]=N+1;
	FOR(i,8) nex[N][i][0]=N, nex[N+1][i][0]=N+1;
	for(i=N-1;i>=0;i--) {
		FOR(x,8) {
			nex[i][x][0]=i;
			if(A[i+1]==x) nex[i][x][1]=i+1;
			else nex[i][x][1]=nex[i+1][x][1];
		}
	}
	
	for(i=2;i<=128;i++) {
		FOR(x,N+2) {
			FOR(y,8) nex[x][y][i]=nex[nex[x][y][i-1]][y][1];
		}
	}
	
	int ma=0;
	FOR(i,8) V[i]=i;
	do {
		for(i=125;i>=1;i--) {
			x=0;
			FOR(y,8) x=nex[x][V[y]][i];
			if(x<=N) break;
		}
		
		int len=i,mask;
		ma=max(ma,len*8);
		FOR(mask,256) {
			x=0;
			FOR(y,8) x=nex[x][V[y]][len+((mask&(1<<y))>0)];
			if(x<=N) ma=max(ma,len*8+__builtin_popcount(mask));
		}
		
		
	} while(next_permutation(V,V+8));
	
	
	cout<<ma<<endl;
	
	
	
}

まとめ

想定解はまだ確認していない。