kmjp's blog

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

Codeforces ECR #022 : D. Two Melodies

この回はいろいろとグダグダ。
http://codeforces.com/contest/813/problem/D

問題

N要素の数列Aが与えられる。
ここから以下の条件を満たす2つの部分列を取りたい。(いずれにも含まれない要素があってもよい)

  • 両部分列のもととなるindexは重複しない
  • 部分列において隣接要素同士の差は±1であるか7の倍数である

両部分列の要素数の最大値を求めよ。

解法

f(x,y) := 数列を先頭から見てy番目までを2つの部分列に振り分けたとき、末尾がx,y番目の要素である部分列の要素数の総和

次に(y+1)番目以降の要素を2つのどちらかの末尾に追加することを考える。
(y+1)~N番目を追加できるか総当たりするとO(N^3)になるが、実際は以下それぞれを満たす6つの最小のzだけチェックすればよい。
事前にそのようなzを求めておけば、全体をO(N^2)で処理することができる。

  • A[z]=A[x]+1
  • A[z]=A[x]-1
  • A[z]=A[x] (mod 7)
  • A[z]=A[y]+1
  • A[z]=A[y]-1
  • A[z]=A[y] (mod 7)

ただO(N^2)とはいえちょっと重めなので注意。

int N;
int A[5050],B[5050];
short cand[5050][5050][3];
int dp[5050][5050];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i], B[i]=A[i]%7;
	
	for(x=1;x<=N;x++) {
		dp[0][x]=1;
		cand[0][x][0]=cand[0][x][1]=cand[0][x][2]=x;
		cand[x][N+1][0]=cand[x][N+1][1]=cand[x][N+1][2]=N+1;
		for(y=N;y>x;y--) {
			cand[x][y][0]=cand[x][y+1][0];
			cand[x][y][1]=cand[x][y+1][1];
			cand[x][y][2]=cand[x][y+1][2];
			if(A[x-1]-A[y-1]==1) cand[x][y][0]=y;
			if(A[x-1]-A[y-1]==-1) cand[x][y][1]=y;
			if(B[x-1]==B[y-1]) cand[x][y][2]=y;
		}
	}
	
	int ma=0;
	for(y=0;y<N+1;y++) {
		FOR(x,y) {
			dp[x][y]=max(dp[x][y],dp[0][x]+1);
			ma=max(ma,dp[x][y]);
			FOR(i,3) {
				j=cand[x][y+1][i];
				if(j<=N) dp[y][j]=max(dp[y][j],dp[x][y]+1);
				j=cand[y][y+1][i];
				if(j<=N) dp[x][j]=max(dp[x][j],dp[x][y]+1);
			}
		}
	}
	cout<<ma<<endl;
	
	
}

まとめ

なぜミスった。