Google Code Jam 2011 Round1B

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

■B. Revenge of the Hot Dogs

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

view plainprint?

1. import java.util.*;  
2. import java.util.Map.Entry;  
3. import java.lang.*;  
4. import java.math.*;  
5. import java.io.*;  
6.   
7. import static java.lang.Math.*;  
8. import static java.util.Arrays.*;  
9.   
10. public class B{  
11.  Scanner sc=new Scanner(System.in);  
12.   
13.  long INF=1L<<40;  
14.  double EPS=1e-9;  
15.   
16.  int caze;  
17.  int n, d;  
18.  R[] rs;  
19.   
20.  void run(){  
21.   int tt=sc.nextInt();  
22.   for(caze=1; caze<=tt; caze++){  
23.    n=sc.nextInt();  
24.    d=sc.nextInt();  
25.    rs=new R[n];  
26.    for(int i=0; i<n; i++){  
27.     int p=sc.nextInt();  
28.     int m=sc.nextInt();  
29.     rs[i]=new R(p, m);  
30.    }  
31.    solve();  
32.   }  
33.  }  
34.   
35.  void solve(){  
36.   long left=0, right=INF;  
37.   for(int i=0; i<n; i++){  
38.    rs[i].p*=2;  
39.   }  
40.   d*=2;  
41.   
42.   sort(rs, new Comparator<R>(){  
43.    @Override  
44.    public int compare(R r1, R r2){  
45.     return r1.p-r2.p;  
46.    }  
47.   });  
48.   
49.   for(int i=0; i<1000; i++){  
50.    long mid=(left+right)/2;  
51.    if(check(mid)){  
52.     right=mid;  
53.    }else{  
54.     left=mid;  
55.    }  
56.   }  
57.   debug(right, right/2.0);  
58.   answer(String.format("%.1f", right/2.0));  
59.  }  
60.   
61.  boolean check(long t){  
62.   long left=-INF;  
63.   for(int j=0; j<n; j++){  
64.    for(int i=0; i<rs[j].m; i++){  
65.     if(rs[j].p+t<left+d){  
66.      return false;  
67.     }  
68.     left=max(left+d, rs[j].p-t);  
69.     // [left+d, INF) and [p-t , p+t]  
70.    }  
71.   }  
72.   return true;  
73.  }  
74.   
75.  class R{  
76.   int p, m;  
77.   R(int p, int m){  
78.    this.p=p;  
79.    this.m=m;  
80.   }  
81.  }  
82.   
83.  void answer(String s){  
84.   println("Case #"+caze+": "+s);  
85.  }  
86.   
87.  void println(String s){  
88.   System.out.println(s);  
89.  }  
90.   
91.  void print(String s){  
92.   System.out.print(s);  
93.  }  
94.   
95.  void debug(Object... os){  
96.   System.err.println(Arrays.deepToString(os));  
97.  }  
98.   
99.  public static void main(String[] args){  
100.   try{  
101.    System.setIn(new FileInputStream(  
102.      "D:/contest_workspace/gcj_2011_round1b/dat/B-large.in"));  
103.    System.setOut(new PrintStream(new FileOutputStream(  
104.      "D:/contest_workspace/gcj_2011_round1b/dat/B-large.out")));  
105.   }catch(Exception e){}  
106.   new B().run();  
107.   System.out.flush();  
108.   System.out.close();  
109.  }  
110. }  

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();
 }
}