Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2326-957ae68f
この記事にトラックバックする(FC2ブログユーザー)

ARC 008 C - THE☆たこ焼き祭り2012 (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #008
問題文

問題概要

N人 (1000以下) の人が2次元平面上にいる.移動できない.
それぞれの人は,投げることができる最大スピードと,受け取る事ができる最大スピードが設定されている.
番号0の人がたこ焼きをN個持っている.
たこ焼きを投げたら,次に投げるまでに1秒以上間隔を開けなくてはいけない.
全員にたこ焼きを配り終わる最小必要時間を求める問題.

解法

ダイクストラで各人に配布するのに必要な最小時間を求める.(1人だけに配るとして)
後は,遠い人から最短パスにそっと投げていけば良い.
最短パスなので,番号0の人が1秒おきに投げるなら,他の人は受け取るのに1秒は間隔が開くので他の人はすぐ投げれる.
自分には投げなくて良いことに注意.

Cによるスパゲッティなソースコード
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define EPS 1e-10
void doubleSort(double d[],int s){int i,j;double k1,k2,t;if(s<=1)return;k1=(d[0]+d[s-1])/2.0;k2=k1+EPS;k1-=EPS;i=-1;j=s;for(;;){while(d[++i]<k1);while(d[--j]>k2);if(i>=j)break;t=d[i];d[i]=d[j];d[j]=t;}doubleSort(d,i);doubleSort(d+j+1,s-j-1);}

double dd(double x, double y){ return sqrt(x*x+y*y); }

double x[1100], y[1100], t[1100], r[1100];
double edge[1100][1100];
double dist[1100];
int vis[1100];

int main(){
  int i,j,k,l,m,n;
  double d, tmp, mx, res;

  scanf("%d",&n);
  rep(i,n) scanf("%lf%lf%lf%lf",x+i,y+i,t+i,r+i);

  rep(i,n) rep(j,n){
    if(i==j){ edge[i][j] = 0; continue; }
    d = dd(x[i]-x[j],y[i]-y[j]);
    mx = t[i]; if(mx > r[j]) mx = r[j];
    edge[i][j] = d/mx;
  }

  rep(i,n) dist[i] = 1e100, vis[i] = 0;
  dist[0] = 0;

  for(;;){
    mx = 1e200; k = -1;
    rep(i,n) if(!vis[i] && dist[i] < mx) mx = dist[i], k = i;
    if(k==-1) break;

    vis[k] = 1;
    rep(i,n) if(!vis[i]){
      if(dist[i] > dist[k] + edge[k][i]) dist[i] = dist[k] + edge[k][i];
    }
  }

  doubleSort(dist, n);

  res = 0;
  REP(i,1,n) if(res < dist[i]+n-i-1) res = dist[i]+n-i-1;
  printf("%.10f\n",res);

  return 0;
}

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2326-957ae68f
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。