AtCoder ARC #114 : D - Moving Pieces on Line

手間取りすぎた。
https://atcoder.jp/contests/arc114/tasks/arc114_d

問題

1次元の数直線上に、いくつかの駒がある。
各駒を直線に沿って任意に動かすことを考える。

数直線の各区間において、駒の移動回数の偶奇が与えられる。
条件を満たす駒の総移動距離の最小値を求めよ。

解法

いわゆる耳DPとちょっと近いのかな？
ある区間を経由する駒の数は、右向きまたは左向きに経由するものがいくつかありうるが、右向きと左向きが両方同じ区間を通ることはない。
そこで、座標圧縮したのち、各区間を右向きまたは左向きに通る駒数を総当たりし、総移動距離の最小値を求めよう。
O(N(N+K))とちょっと重いが何とか間に合う。

int N,K;
ll A[5050],T[5050];

ll FL[5050],FR[5050];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	vector<pair<int,int>> ev;
	FOR(i,N) {
		cin>>A[i];
		ev.push_back({A[i],-1});
	}
	FOR(i,K) {
		cin>>T[i];
		ev.push_back({T[i],i});
	}
	
	sort(ALL(ev));
	FOR(i,5050) FL[i]=1LL<<60;
	FOR(i,5050) FR[i]=1LL<<60;
	FL[0]=FR[0]=0;
	
	int pre=-1LL<<30;
	int blue=0;
	FORR(e,ev) {
		
		if(e.first!=pre) {
			if(blue==0) {
				for(i=1;i<=N;i+=2) FL[i]=FR[i]=1LL<<60;
				for(i=0;i<=N;i+=2) {
					FL[i]+=i*1LL*(e.first-pre);
					FR[i]+=i*1LL*(e.first-pre);
				}
			}
			else {
				for(i=0;i<=N;i+=2) FL[i]=FR[i]=1LL<<60;
				for(i=1;i<=N;i+=2) {
					FL[i]+=i*1LL*(e.first-pre);
					FR[i]+=i*1LL*(e.first-pre);
				}
			}
		}
		
		// Rを減らす
		for(i=N;i>=0;i--) FR[i]=min(FR[i],FR[i+1]);
		FL[0]=FR[0]=min(FL[0],FR[0]);
		// Lを増やす
		FOR(i,N) FL[i+1]=min(FL[i],FL[i+1]);
		
		if(e.second>=0) {
			blue^=1;
		}
		else {
			// Lを回収
			FOR(i,N) FL[i]=min(FL[i],FL[i+1]);
			// Rを増やす
			for(i=N;i>=1;i--) FR[i]=min(FR[i-1],FR[i]);
		}
		pre=e.first;
	}
	
	
	ll ret=FL[0];
	FOR(i,N+1) ret=min(ret,FR[i]);
	if(ret>=1LL<<60) ret=-1;
	cout<<ret<<endl;
}

まとめ

N,Kが割と大きいので、O(N(N+K))に走るのにちょっと手間取ったんだよね…。