Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

January 2011 Challenge 4問目 - Flu Shot Lineup (この記事を編集する[管理者用])

Source

codechef January 2011 Challenge 4問目
Problem Statement
January 2011 Challengeの参加記録

問題概要

半直線上 (x≧0) にN人 (10000以下) の人がいる.
それぞれの人がD以下だけ動いて,最も近い2人の距離をT (1000000以下) 以上にできる.
N人の初期位置とTが与えられたとき,Dの最小値を求める問題.

解法

取り敢えず,答えに対して2分探索.
Dだけ動いて,最も近い2人の距離をT以上にできるかどうかは,左の人から,できるだけ左で,左の人とT以下になるまで近づかないようにできるだけ左に移動するgreedyで確かめられる.

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

int n;
double in[10010], D;

int is_ok(double m){
  int i; double now;

  now = in[0] - m;
  if(now<0) now = 0;
  REP(i,1,n){
    now += D;
    if(now > in[i]+m) return 0;
    if(now < in[i]-m) now = in[i]-m;
  }

  return 1;
}

int main(){
  int i,j,k;
  double a,b,c;
  int size;

  scanf("%d",&size);
  while(size--){
    scanf("%d%lf",&n,&D);
    rep(i,n) scanf("%lf",in+i);
    a = 0; b = n*D;
    while(b-a > 1e-5){
      c = (a+b)/2;
      if(is_ok(c)) b=c; else a=c;
    }
    printf("%.4lf\n",(a+b)/2);
  }

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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