Codeforces #380 Div1 A. Road to Cinema

この回は妙に順位がよかった。
http://codeforces.com/contest/737/problem/A

問題

今いる場所からS離れた場所に時間T内で移動したい。
その際、車で移動する。
車は以下の２つのモードを任意に切り替え可能である。

• 通常走行：距離１を進むのに時間２・燃料１かかる
• 加速走行：距離１を進むのに時間１・燃料２かかる

目的地までの間にいくつかガソリンスタンドがある。
そこでは車の燃料タンクを一瞬で満タンにできる。

ここでいくつかの車のレンタル候補があり、車のレンタル費と燃料タンクの容量が与えられる。
時間内に目的地に着くに必要な最安値の車を求めよ。

解法

以下のいずれでもよい。

• 二分探索などで時間内に間に合う最小の燃料タンクの容量を求め、それ以上のタンクを持つ最安の車を答える。
• ガソリンスタンド間の距離を昇順にソートしておき、累積和と二分探索で各車に対しかかる時間を求める。

以下のコードは後者。

int N;
ll K,S,T;
ll C[202020],V[202020];
ll G[202020],GS[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K>>S>>T;
	
	FOR(i,N) cin>>C[i]>>V[i];
	FOR(i,K) cin>>G[i];
	G[K]=S;
	K++;
	sort(G,G+K);
	for(i=K-1;i>=1;i--) G[i]-=G[i-1];
	
	sort(G,G+K);
	FOR(i,K) GS[i+1]=GS[i]+G[i];
	
	int mi=1<<30;
	FOR(i,N) if(mi>C[i] && V[i]>=G[K-1]) {
		x = lower_bound(G,G+K,V[i]/2+1)-G;
		
		ll t=S+(2*(GS[K]-GS[x])-(K-x)*V[i]);
		if(t<=T) mi=C[i];
		
	}
	if(mi==1<<30) mi=-1;
	cout<<mi<<endl;
	
}

まとめ

前者の方がわかりやすいけど、コード量はあまり変わらなさそう。