Zepto Code Rush 2014 : D. Pudding Monsters

Zepto Code Rush、DとEの配点は同じだけどDの方が正答者が少ないね。
http://codeforces.com/contest/436/problem/D

問題

1次元で無限に並ぶセルがある。
このうちN個のセルにモンスターがおり、またM個のセルが特別なセルである。

プレイヤーは以下の条件を満たすようにモンスターを移動できる。

• モンスターを選択し、左右のどちらかに動かそうとすると、そのモンスターは他のモンスターにぶつかるまで移動を続ける。
• 隣接マスにいるモンスター同士は連結し、以後の移動は同時に移動しなければならない。

モンスターをうまく動かし、M個の特別セルのうちできるだけ多くのセルにモンスターが乗るようにせよ。

解法

Editorialを見て解いた。
まず、隣接セルのモンスターがくっつく、という条件を外してみ見てみる。

以下のように変数を取る。

• sum(l,r) : 座標l～rの間の特別セルの数
• Z[i] : 左からi番目までのモンスターで占められる最大の特別セル数
• D[i] : 左からi番目までのモンスターで占められ、かつi番目のモンスターが動かない場合のる最大の特別セル数

以下のようにDP出来る。

• i番目のモンスターの座標をr、その左側にある特別セルの座標をlとする。i番より手前のj番のモンスターのZ[j]を用いてD[i]を更新していく。
  • D[i]=max(D[i], Z[i-(r-l)]+sum(l,r))でD[i]を更新できる。これはi番目より左側のモンスターを右に寄せようとすると、座標lをモンスターで占めるには(i-(r-l)+1)～(i-1)番目のモンスターを右に寄せないといけないので、このようになる。
• 次にi番目のモンスターの座標をl、その右にある特別セルの座標をlとする。i番より後のk番のモンスターのZ[k]を、D[i]を使い更新していく。
  • Z[i+(r-l)]=max(Z[i+(r-l)], D[i]+sum(l+1,r))で更新すればよい。

上記の考えは、モンスターがくっつく場合を考慮していない。
そのため、Z[i-(r-l)]やZ[i+(r-l)]を選ぶ場合、i-(r-l)番やi+(r-l)番がもともと連結したモンスターの一部である場合は、その連結モンスター全体を選択するようにしなければならない。

int N,M;
int A[100005],B[3000],st[100005],en[100005];
int dp[100005],S[300005];

void solve() {
	int f,i,j,k,l,x,y;
	cin>>N>>M;
	FOR(i,N) cin>>A[i];
	FOR(i,M) cin>>B[i],S[B[i]]++;
	sort(A,A+N);
	sort(B,B+M);
	
	FOR(i,200001) S[i+1]+=S[i];
	en[N]=N;
	for(i=1;i<N;i++) st[i]=(A[i-1]+1==A[i])?st[i-1]:i;
	for(i=N-1;i>=0;i--) en[i]=(A[i+1]-1==A[i])?en[i+1]:i+1;
	
	FOR(i,N) if(st[i]==i) {
		int D=dp[i]+S[A[i]]-S[A[i]-1];
		
		FOR(j,M) if(B[j]<A[i]) {
			x=i-(A[i]-B[j]);
			if(x>=0) D=max(D,dp[st[x]]+S[A[i]]-S[B[j]-1]);
		}
		dp[en[i]]=max(dp[en[i]],D);
		FOR(j,M) if(B[j]>=A[i]) {
			x=i+(B[j]-A[i]);
			if(x<N) dp[en[x]]=max(dp[en[x]],D+S[B[j]]-S[A[i]]);
		}
	}
	cout << dp[N] << endl;
}

まとめ

うーん、このDPはちょっと思いつくのが大変そうだ。
連結条件がますますややこしくしている。