Google Code Jam 2011 Round1B

せめて，Bは解いておこうかと．

■B. Revenge of the Hot Dogs

ご想像のとおり二分探索．
時間tに対して，各ホットドッグ屋がD離れることが出来るかを判定する必要がある．
これは，ホットドッグ屋を左から見ていき，可能な限り左に寄せていくことで判定できる．
二分探索の上限の見積もりが甘くLargeでWAってしまった…．

import java.util.*;
import java.util.Map.Entry;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class B{
 Scanner sc=new Scanner(System.in);

 long INF=1L<<40;
 double EPS=1e-9;

 int caze;
 int n, d;
 R[] rs;

 void run(){
  int tt=sc.nextInt();
  for(caze=1; caze<=tt; caze++){
   n=sc.nextInt();
   d=sc.nextInt();
   rs=new R[n];
   for(int i=0; i<n; i++){
    int p=sc.nextInt();
    int m=sc.nextInt();
    rs[i]=new R(p, m);
   }
   solve();
  }
 }

 void solve(){
  long left=0, right=INF;
  for(int i=0; i<n; i++){
   rs[i].p*=2;
  }
  d*=2;

  sort(rs, new Comparator<R>(){
   @Override
   public int compare(R r1, R r2){
    return r1.p-r2.p;
   }
  });

  for(int i=0; i<1000; i++){
   long mid=(left+right)/2;
   if(check(mid)){
    right=mid;
   }else{
    left=mid;
   }
  }
  debug(right, right/2.0);
  answer(String.format("%.1f", right/2.0));
 }

 boolean check(long t){
  long left=-INF;
  for(int j=0; j<n; j++){
   for(int i=0; i<rs[j].m; i++){
    if(rs[j].p+t<left+d){
     return false;
    }
    left=max(left+d, rs[j].p-t);
    // [left+d, INF) and [p-t , p+t]
   }
  }
  return true;
 }

 class R{
  int p, m;
  R(int p, int m){
   this.p=p;
   this.m=m;
  }
 }

 void answer(String s){
  println("Case #"+caze+": "+s);
 }

 void println(String s){
  System.out.println(s);
 }

 void print(String s){
  System.out.print(s);
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 public static void main(String[] args){
  try{
   System.setIn(new FileInputStream(
     "D:/contest_workspace/gcj_2011_round1b/dat/B-large.in"));
   System.setOut(new PrintStream(new FileOutputStream(
     "D:/contest_workspace/gcj_2011_round1b/dat/B-large.out")));
  }catch(Exception e){}
  new B().run();
  System.out.flush();
  System.out.close();
 }
}