kmjp's blog

競技プログラミング参加記です

Google Code Jam 2015 Round 1B : C. Hiking Deer

GCJ

よい問題設定。
https://code.google.com/codejam/contest/8224486/dashboard#s=p2

問題

1周360度分の円形のコースがある。
あなたは始点から初めてコースを1周周り始点に戻るように走りたい。
その際、走る速度は任意のタイミングで任意に調節できる。

このコードには、他に多数の集団が走っている。
ある集団は、あなたの出発時に始点からD[i]の位置におり、H[i]人で構成されていて、各人は角度1度あたりM[i]～M[i]+H[i]-1だけ時間がかかる(バラバラな)速度で走っている。

あなたは1周する間に、人と出会う買う数を出来るだけ少なくなるように走りたい。
最小で何人と出会う走り方ができるか。

解法

この問題は(恐らく入力の都合で)他人のパラメータが集合で与えられる。
ただ、本質的に集合であることに意味はないので、集合をばらしてN人(N=sum(H[i]))が初期D[i]度の位置にいて1度あたりM[i]の速度で走っている、と考える。

各人が最初に始点を通過する時刻をT[i]とする。
あなたがT[i]-eps時間でゴールするように走ると、以下の人とすれ違う事になる。

  • T[i]より遅い時間にゴールする人を1回ずつ追い抜く。
  • T[i]より速くゴールする人について、T[i]時点で始点をR[i]回通過してるとすると、(R[i]-1)回ずつ追い抜かれる。

よって上記2値の和が最小となるようなiを求めればよい。
前者は容易に計算できる。後者は各人をT[i]の小さい順にソートし、以下の手順で計算できる。

T[i]の人がゴールするまでには、T[i-1]の人がゴールするまでに抜かれた人にも当然抜かれる。
あとはT[i-1]～T[i]の時間にさらに何人に抜かれるかを加算する。
i番の人を処理する場合、0～(i-1)番の人が次に始点に到着する時刻をpriority_queueで管理する。
その時刻がT[i]より早い人がいる場合、その都度追い越された回数を加算して、次にもう1周するタイミングをpriority_queueに追加していく。

すごく遅い人がいると、その間に早い人に何周も追い越され、priority_queueの更新処理回数が非常に大きくなる可能性がある。
ただし、この問題では時刻T[0]-epsに到着するように走ることで解が(N-1)以下となることが確定するので、追い越された回数が(N-1)回を超えたら以降は処理を打ち切ってよい。

int N;
ll D[1010],H[1010],M[1010];
pair<ll,ll> P[505000];
int slower[505000];

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cin>>N;
	x=0;
	FOR(i,N) {
		cin>>D[i]>>H[i]>>M[i];
		FOR(j,H[i]) {
			P[x].second=M[i]+j;
			P[x].first=(360-D[i])*(M[i]+j);
			x++;
		}
	}
	N=x;
	sort(P,P+N);
	
	for(i=N-1;i>=0;i--) {
		if(P[i].first==P[i+1].first) slower[i]=slower[i+1];
		else slower[i]=N-1-i;
	}
	
	ll mi=N;
	ll faster=0;
	priority_queue<pair<ll,ll> > Q;
	FOR(i,N) {
		while(Q.size()) {
			auto r=Q.top();
			if(-r.first>P[i].first) break;
			if(++faster>N) break;
			Q.pop();
			Q.push(make_pair(r.first-360LL*r.second,r.second));
		}
		
		Q.push(make_pair(-P[i].first-360LL*P[i].second,P[i].second));
		mi=min(mi,faster + slower[i]);
		if(faster>N) break;
	}
	
	_P("Case #%d: %lld\n",_loop,mi);
}

まとめ

ちょっとややこしいけど、面白かったです。