Codeforces #243 Div1 C. Sereja and Two Sequences

一見典型問題に見せかけて妙な制限がかかった問題。
http://codeforces.com/contest/425/problem/C

問題

２つの数列A,Bが与えられる。
ここで初期エネルギーSを持っている状態でゲームを行う。
ゲームでは以下の処理を行える。

• エネルギーEを消費し、AとBのprefixを取り除く。
  • １回取り除くことにコインを１枚得る権利を得る。
  • 取り除く両prefixの最後の要素は同じ数字でないといけない。
• 今まで取り除いたA,Bの要素数分のエネルギーを消費し、コインを得る権利を確定し、ゲームを終了する。

当然ゲーム中エネルギーが負になってはならない。
最適な処理を行ったとき、コインを最大何枚得られるか。

解法

最後ゲームを抜けるときに取り除いた要素数分のエネルギーが必要なので、prefixはできるだけ要素を取り除く数が少なくなるようにしていきたい。

A,Bの要素数は多いが、S/Eは高々300なので得られるコインは300枚である。
この問題はDPで処理していけばよい。

j回目のコインを取る際、A[i]と合わせて取り除くBのprefixは、(j-1)回目のコインを取り除く際A[0]～A[i-1]と一緒に取り除いた位置の最小値をkとして、B[k]以降でA[i]と同じ値を持つもっともkに近いindexである。
A[i]と合わせて取り除くB[l]が決まったら、その段階で権利確定ができるかチェックすればよい。

コインを得る回数がS/E、要素数がN、最小index判定がlogNなのでO(N*(S/E)*logN)とそこそこ重め。

int N,M,S,E;
ll A[100001],B[100001];
vector<int> SB[100001];
int dpdp[401][100001];

void solve() {
	int f,i,j,k,l,x,y;
	cin>>N>>M>>S>>E;
	FOR(i,N) cin>>A[i];
	FOR(i,M) {
		cin>>B[i];
		SB[B[i]].push_back(i);
	}
	FOR(x,301) FOR(y,100001) dpdp[x][y]=1000000;
	FOR(y,100001) dpdp[0][y]=0;
	int ma=0;
	FOR(x,301) {
		int mi=(x>0)?(dpdp[x][x-1]+1):0;
		for(y=x;y<N;y++) {
			vector<int>::iterator it=lower_bound(SB[A[y]].begin(),SB[A[y]].end(),mi);
			if(it==SB[A[y]].end()) {
				dpdp[x+1][y]=1000000;
			}
			else {
				dpdp[x+1][y]=*it;
				k=(x+1)*E+(y+1)+(*it+1);
				if(k<=S) ma=max(ma,x+1);
			}
			mi=min(mi,dpdp[x][y]+1);
		}
	}
	_P("%d\n",ma);
}

まとめ

これは解法は割とすぐ思いついたけど、実装で途中indexが1ずれたりが頻発して時間食った。
ともあれ本番に解けてよかった。