AtCoder ARC #008 : C - THE☆たこ焼き祭り2012

今回はこれで問題文読み落としして時間を消費しすぎた…。
http://arc008.contest.atcoder.jp/tasks/arc008_3

N個の点の座標と、たこ焼きを投げる速さが与えられる。
始点から１秒に１個たこ焼きが生成されるので、「始点以外の」全員にたこ焼きが行きわたる時間を求める。

回答は割と単純で、まず始点から全部の点までの最短到達時間をダイクストラで求める。
時間がかかる順に、先に生成されたたこ焼きを渡すので、M番目に遠い点には、始点からの到達時間＋(N-1-M)の時間がかかる。
この時間の最大値を求めればよい。

１度に１個しかたこ焼きを投げられない、ということについて問題文で延々説明があるけど、自分は本問には関係ない。
というのも、中継点はたこ焼きを受け取るとすぐに次の点にたこ焼きを投げるし、遠い順にたこ焼きを配置するので途中の点が２個たこ焼きを持つことはない。

問題は、始点自体はたこ焼きを持たなくてよいこと。
自分はこれを読み間違いして6WA位やらかした。maxrandとかいうデータセットだったので精度のミスかと散々見た挙句、終了後に気づいた。
問題文中、「全員」「全員の参加者」という言い回しが多く、始点が対象外だと気付かなかったのよ…

ほかにも同じ間違いをした人は結構いたようだ。

int N;
int X[1001],Y[1001],T[1001],R[1001];
double MT[1001][1001];
double tim[1001];
double ma=1e23;
int fix[1001];



void solve() {
	int m,d,i,w,j;
	
	N=GETi();
	FOR(i,N){
		X[i]=GETi();
		Y[i]=GETi();
		T[i]=GETi();
		R[i]=GETi();
	}
	
	FOR(i,N){
		tim[i]=ma;
		FOR(j,N){
			if(i==j) {
				MT[i][j]=0;
			}
			else {
				double v=min(T[i],R[j]);
				double dx=(X[i]-X[j]);
				double dy=(Y[i]-Y[j]);
				double dist = sqrt(dx*dx+dy*dy);
				MT[i][j]=dist / v;
			}
		}
	}
	
	ZERO(fix);
	tim[0]=0;
	int mv=0;
	while(mv>=0) {
		int v,fv=-1;
		double mc=ma;
		
		fix[mv]=1;
		FOR(v,N) {
			if(v==mv) continue;
			tim[v]=min(tim[v],tim[mv]+MT[mv][v]);
			if(!fix[v] && (fv==-1 || tim[v]<tim[fv])){ fv=v;}
		}
		mv=fv;
	}
	
	double minf=0;
	sort(tim,tim+N);
	FOR(i,N) if(i>0) minf = max(minf, tim[i]+(N-1-i));
	
	_P("%.12f\n",(double)minf);
}

まとめ

AといいCといい問題文はちゃんと読もう、ということで。