この回はいろいろとグダグダ。
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; }
まとめ
なぜミスった。