dwangoプログラミングコンテスト予選 : D - タクシー

うーん、うまく三分探索できなかった。
http://dwango2015-prelims.contest.atcoder.jp/tasks/dwango2015_prelims_4

問題

円形の道路上にN個の都市があり、イベントを行う。
各都市に対し、位置・参加者数・会場の席数が与えられる。

全都市の参加者数の和と会場の席数の和は等しい。
よって、一部参加者が他の町に移動することによって全参加者をイベント会場に収容可能である。

参加者が道路を１移動するのにコストが１かかるとする。
全参加者をイベント会場に収容するのに必要な最小コストを答えよ。

解法

参加者とキャパシティが両方ある都市は相殺させておく。

部分点1解法

参加者と席をそれぞれ人数分列挙し、都市順に並べる。
例えば入力例１なら、(相殺分を除き)参加者の都市は{4,21,27,27}、空き席の都市は{0,0,0,19}である。

総参加者数をSとすると、(0-indexとして)i番目の参加者が(i+x)%S番目の席に座ると考える。
各xに対して参加者の都市と空き席の都市の移動距離の総和を取ればよい。
1回総和を取るのにO(S)、xがS通りなのでO(S^2)で解ける。

満点解法

基本的な考え方は部分点と同じである。
Sが大きいのでO(S^2)では解けないため、三分探索でxを絞り込んでいく。
移動距離の総和も尺取法の要領でO(S)ではなくO(N)で行うと、O(N*logS)で済む。

xに対する総コストは周期Sの周期関数となるので、探索範囲は0～(S-1)ではなく-(S-1)～(S-1)にしておくと良い。

三分探索以外に、xを1ずらしたときに総コストが小さくなる方向にずらしていく手法もある。

int N,L;
ll tot=0;
vector<pair<ll,ll> > BB,CC;
ll mi=1LL<<62;

ll dodo(ll v) {
	int i,x,y;
	ll cx=0,cy=0;
	if(v<0) v+=tot;

	FOR(y,CC.size()) {
		if(v>=CC[y].first) v-=CC[y].first;
		else {
			cy=CC[y].first-v;
			break;
		}
	}
	
	ll ret=0;
	
	for(x=0,cx=BB[x].first ;;) {
		ll m=min(cx,cy);
		ret += m*min(abs(BB[x].second-CC[y].second),L-abs(BB[x].second-CC[y].second));
		cx-=m;
		cy-=m;
		if(cx==0) {
			if(++x>=BB.size()) break;
			cx=BB[x].first;
		}
		if(cy==0) {
			if(++y>=CC.size()) y=0;
			cy=CC[y].first;
		}
	}
	mi=min(mi,ret);
	return ret;
}

void test(ll LL,ll RR) {
	
	if(RR-LL<=9) {
		for(ll x=LL;x<=RR;x++) dodo(x);
		return;
	}
	
	ll m1=(2*LL+RR)/3;
	ll m2=(LL+2*RR)/3;
	ll d1=dodo(m1),d2=dodo(m2);
	if(d1<d2) test(LL,m2);
	else if(d1>d2) test(m1,RR);
	else test(m1,m2);
}
void solve() {
	int i,j,k,l,r,x,y,z; string s;
	
	cin>>N>>L;
	FOR(i,N) {
		cin>>r>>y>>z;
		x=min(y,z);
		tot+=y-x;
		if(y>x) BB.push_back(make_pair(y-x,r));
		if(z>x) CC.push_back(make_pair(z-x,r));
	}
	dodo(-tot+1);
	dodo(tot-1);
	test(-tot+1,tot-1);
	cout<<mi<<endl;
}

まとめ

三分探索までは思いついたのに、探索範囲を0～(S-1)にして失敗。