Codeforces #687 Div1 D. Cakes for Clones

シンプルな問題設定ながら、変わった解き味で良い。
https://codeforces.com/contest/1456/problem/D

問題

1次元の数直線上でキャラクターを動かす。
キャラクターは初期状態で原点におり、速度１で左右に移動できる。

ここで、数直線上にN個のケーキが登場する。
ケーキが登場する場所と時間はわかっており、ケーキは一瞬しか登場しないので、ケーキを取るにはその時点でその場所にいなければならない。

キャラクターを操作して全部のケーキを回収したいのだが、ここでキャラクターは移動以外にクローンを生成するという行動をとれる。
クローンを生成すると、キャラクターの現在位置にキャラが生成され、その後そのクローンは動かない。
もしケーキが出現したとき、クローンがその座標に存在するなら、ケーキを回収できる。

クローンを同時に2体出現させることはできない。
2体目を出現させると、1体目は消滅する。

最適に移動とクローン生成を行った場合、全ケーキを回収可能か判定せよ。

解法

以下ケーキの番号は時間順にソート済みとする。
dp(i,j) := j番目のケーキの位置にクローンを生成した状態で、i番目までのケーキを回収した状態にできるかの真偽値
mt(i,j) := i番目までのケーキを回収した状態において、j番目のケーキの位置に到達する最小時刻

上記2つの値を更新していこう。
最終的にdp(N-1,N)がTrueであるか、mt(N-1,N)がN個めのケーキの登場時刻以前であれば条件を満たす。

int N;

pair<int,int> P[5050];
ll T[5050];
ll X[5050];

ll mt[5050];
int dp[5050][5050];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>P[i+1].first>>P[i+1].second;
	}
	N++;
	sort(P,P+N);
	FOR(i,N) {
		T[i]=P[i].first;
		X[i]=P[i].second;
	}
	
	FOR(i,N) mt[i]=1LL<<60;
	mt[0]=0;
	FOR(i,N-1) {
		if(mt[i]<=T[i]) {
			mt[i+1]=min(mt[i+1],max(T[i],mt[i]+abs(X[i+1]-X[i])));
			for(j=i+2;j<N;j++) {
				ll arrive=max(T[i],mt[i]+abs(X[j]-X[i]));
				ll deadline=T[i+1]-abs(X[j]-X[i+1]);
				if(arrive<=deadline) dp[i+1][j]=1;
			}
		}
		if(dp[i][i+1]&&i+2<N) {
			mt[i+2]=min(mt[i+2],max(T[i+1],T[i]+abs(X[i+2]-X[i])));
			for(j=i+3;j<N;j++) {
				ll arrive=max(T[i+1],T[i]+abs(X[j]-X[i]));
				ll deadline=T[i+2]-abs(X[j]-X[i+2]);
				if(arrive<=deadline) dp[i+2][j]=1;
			}
		}
		for(j=i+2;j<N;j++) if(dp[i][j]) {
			if(T[i+1]-T[i]>=abs(X[i+1]-X[i])) dp[i+1][j]=1;
		}
	}
	
	if(mt[N-1]<=T[N-1]||dp[N-2][N-1]) cout<<"YES"<<endl;
	else cout<<"NO"<<endl;
	
}

まとめ

シンプルながら割と解法を考えるのが難しくて、本番の正答率は低め。