AtCoder ARC #073 : F - Many Moves

方針はすぐ立ったけど、手間取りすぎた。
http://arc073.contest.atcoder.jp/tasks/arc073_d

問題

1～Nのマスが一直線にならんでおり、初期状態でA,Bのマスにコマがある。

ここでQ個のクエリが与えられる。
各クエリはマスの番号X[i]からなる。
クエリのたびに２つのコマのうちいずれかをX[i]に移動しなければならない。
その際、コマを1移動するのに1コストがかかる。

全クエリを処理するための最小コストを答えよ。

解法

このタイプの問題は、クエリX[i+1]の際、片方の駒は必ず前のクエリの完了後の位置X[i]にいるので、もう片方の駒がどこにいるのかを管理していくとよい。

以下を考える。
f(i,x) := i番目のクエリ完了後、駒がX[i]とxにいるときの総コストの最小値

次のクエリの結果は以下の最小値になる

• 前回と同じ駒を動かす場合
  • f(i+1,y) = f(i,y) + |X[i+1]-X[i]|
• 前回と別の駒を動かす場合(y=X[i+1]の時のみ)
  • f(i+1,y) = min(f(i,x) + |x-y|)

後者の最小値は、g(i,x)=f(i,x)-xおよびh(i,x)=f(i,x)+xのうち最小値を求めるSegTreeを用いて求めることができる。
また、前者の処理はそれらのSegTreeの全要素に同じ値を加算できるようにすればよい。

static ll const def=1LL<<60;
template<class V,int NV> class SegTree_3 {
public:
	vector<V> val, ma;
	SegTree_3(){
		int i;
		val.resize(NV*2,0); ma.resize(NV*2,0);
		FOR(i,NV) val[i+NV]=ma[i+NV]=0;
		for(i=NV-1;i>=1;i--) ma[i]=min(ma[2*i],ma[2*i+1]);
	};
	
	V getval(int x,int y,int l=0,int r=NV,int k=1) {
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return ma[k];
		return val[k]+min(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	
	void update(int x,int y, V v,int l=0,int r=NV,int k=1) {
		if(l>=r) return;
		if(x<=l && r<=y) {
			val[k]+=v;
			ma[k]+=v;
		}
		else if(l < y && x < r) {
			update(x,y,v,l,(l+r)/2,k*2);
			update(x,y,v,(l+r)/2,r,k*2+1);
			ma[k]=val[k]+min(ma[k*2],ma[k*2+1]);
		}
	}
};

int N,Q,A,B;
SegTree_3<ll,1<<20> stl,str;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q>>A>>B;
	for(i=1;i<=N;i++) {
		if(i!=B) {
			stl.update(i,i+1,(1LL<<50)+i);
			str.update(i,i+1,(1LL<<50)-i);
		}
		else {
			stl.update(i,i+1,i);
			str.update(i,i+1,-i);
		}
	}
	ll pre=A;
	while(Q--) {
		ll X;
		cin>>X;
		
		// move other
		ll mi=min(stl.getval(X,N+1)-X,str.getval(1,X+1)+X);
		// move pre
		stl.update(1,N+1,abs(X-pre));
		str.update(1,N+1,abs(X-pre));
		
		// move other
		ll x=stl.getval(pre,pre+1)-pre;
		if(mi<x) stl.update(pre,pre+1,mi-x);
		x=str.getval(pre,pre+1)+pre;
		if(mi<x) str.update(pre,pre+1,mi-x);
		
		pre=X;
	}
	
	ll ret=1LL<<60;
	for(i=1;i<=N;i++) ret=min(ret,stl.getval(i,i+1)-i);
	for(i=1;i<=N;i++) ret=min(ret,str.getval(i,i+1)+i);
	cout<<ret<<endl;
	
}

まとめ

SegTreeのデバッグが大変。