Google Code Jam 2011 Round2

GCJ2011 Round2(6/4 23:00~01:30)

Round2に進めただけでも，進歩を感じましたが，欲を出して，Tシャツを狙いに行きました．

■A. Airport Walkways

K[m]の道がある．あなたは，普段は速度S[m/s]で歩くが，（トータルで）t[s]だけ速度R[m/s]で走ることが出来る．
さらに道のいくつかの部分には，動く歩道が設置されており，その速度があなたの歩くor走る速度に上乗せされる．
最短何秒でK[m]移動することが出来るか．

どこ走るかがポイント．答えは，動く歩道の速度+歩く速度が小さいところをより優先する．
あとは，走った時間が正確にt[s]になるように気をつける．

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. import static java.lang.Math.*;  
7. import static java.util.Arrays.*;  
8.   
9. public class A{  
10.  Scanner sc=new Scanner(System.in);  
11.   
12.  int INF=1<<28;  
13.  double EPS=1e-9;  
14.   
15.  int caze;  
16.  int TT;  
17.  int x, s, r, t, n;  
18.  int[] b, e, w;  
19.   
20.  void run(){  
21.   TT=sc.nextInt();  
22.   for(caze=1; caze<=TT; caze++){  
23.    x=sc.nextInt();  
24.    s=sc.nextInt();  
25.    r=sc.nextInt();  
26.    t=sc.nextInt();  
27.    n=sc.nextInt();  
28.    b=new int[n];  
29.    e=new int[n];  
30.    w=new int[n];  
31.    for(int i=0; i<n; i++){  
32.     b[i]=sc.nextInt();  
33.     e[i]=sc.nextInt();  
34.     w[i]=sc.nextInt();  
35.    }  
36.    solve();  
37.   }  
38.  }  
39.   
40.  void solve(){  
41.   int[] v=new int[x];  
42.   fill(v, s);  
43.   for(int j=0; j<n; j++){  
44.    for(int i=b[j]; i<e[j]; i++){  
45.     v[i]+=w[j];  
46.    }  
47.   }  
48.   PriorityQueue<Integer> que=new PriorityQueue<Integer>();  
49.   for(int i=0; i<x; i++){  
50.    que.offer(v[i]);  
51.   }  
52.   double d=r-s;  
53.   double remain=t;  
54.   double ans=0;  
55.   for(int i=0; i<x; i++){  
56.    int u=que.poll();  
57.    if(1.0/(u+d)>remain+EPS){  
58.     double p=remain*(u+d);  
59.     ans+=remain+(1.0-p)/u;  
60.     remain=0;  
61.    }else{  
62.     remain-=1.0/(u+d);  
63.     ans+=1.0/(u+d);  
64.    }  
65.   }  
66.   answer(ans+"");  
67.  }  
68.   
69.  void answer(String s){  
70.   println("Case #"+caze+": "+s);  
71.  }  
72.   
73.  void println(String s){  
74.   System.out.println(s);  
75.  }  
76.   
77.  void print(String s){  
78.   System.out.print(s);  
79.  }  
80.   
81.  void debug(Object... os){  
82.   System.err.println(Arrays.deepToString(os));  
83.  }  
84.   
85.  public static void main(String[] args){  
86.   try{  
87.    System.setIn(new FileInputStream(  
88.      "D:/contest_workspace/gcj_2011_round2/dat/A-large.in"));  
89.    System.setOut(new PrintStream(new FileOutputStream(  
90.      "D:/contest_workspace/gcj_2011_round2/dat/A-large.out")));  
91.   }catch(Exception e){}  
92.   
93.   new A().run();  
94.   System.out.flush();  
95.   System.out.close();  
96.  }  
97. }  

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

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

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

 int INF=1<<28;
 double EPS=1e-9;

 int caze;
 int TT;
 int x, s, r, t, n;
 int[] b, e, w;

 void run(){
  TT=sc.nextInt();
  for(caze=1; caze<=TT; caze++){
   x=sc.nextInt();
   s=sc.nextInt();
   r=sc.nextInt();
   t=sc.nextInt();
   n=sc.nextInt();
   b=new int[n];
   e=new int[n];
   w=new int[n];
   for(int i=0; i<n; i++){
    b[i]=sc.nextInt();
    e[i]=sc.nextInt();
    w[i]=sc.nextInt();
   }
   solve();
  }
 }

 void solve(){
  int[] v=new int[x];
  fill(v, s);
  for(int j=0; j<n; j++){
   for(int i=b[j]; i<e[j]; i++){
    v[i]+=w[j];
   }
  }
  PriorityQueue<Integer> que=new PriorityQueue<Integer>();
  for(int i=0; i<x; i++){
   que.offer(v[i]);
  }
  double d=r-s;
  double remain=t;
  double ans=0;
  for(int i=0; i<x; i++){
   int u=que.poll();
   if(1.0/(u+d)>remain+EPS){
    double p=remain*(u+d);
    ans+=remain+(1.0-p)/u;
    remain=0;
   }else{
    remain-=1.0/(u+d);
    ans+=1.0/(u+d);
   }
  }
  answer(ans+"");
 }

 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_round2/dat/A-large.in"));
   System.setOut(new PrintStream(new FileOutputStream(
     "D:/contest_workspace/gcj_2011_round2/dat/A-large.out")));
  }catch(Exception e){}

  new A().run();
  System.out.flush();
  System.out.close();
 }
}

■B. Spinning Blade

全探索で解ける．
愚直に実装すると，(x₁, y₁)-(x₁, y₁) からなる長方形の重心を求めるための計算量は， O(n⁵)となり(8分間では)絶対に間に合わない．
そこで，部分和を使う．
MX1(i, j)=Σ_0≦k≦ia(k, j)k
MY1(i, j)=Σ_0≦k≦ja(i, k)k
とする．
これで，ある行 or 列に対するある範囲の質量×位置の総和がO(1)で求まるため， 総計算量は、O(n⁴)になる．しかし，n=500なので，これでも厳しい．
最終的に，
MX2(i, j)=Σ_0≦k≦iMX1(i, k)
MY2(i, j)=Σ_0≦k≦jMY1(k, j)
とすると，
MX1(i, j) or MY1(i, j)は(1, 1)-(i, j)からなる長方形のxおよびy座標に関する質量×位置の総和になる．(1, 1)-(i, j)の長方形の総質量も同様にして求められるようにすれば，1クエリをO(1)で求めることが出来るため結局，総計算量がO(n³)になり間に合う．

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. import static java.lang.Math.*;  
7. import static java.util.Arrays.*;  
8.   
9. public class B{  
10.  Scanner sc=new Scanner(System.in);  
11.   
12.  int INF=1<<28;  
13.  double EPS=1e-9;  
14.   
15.  int caze;  
16.  int t;  
17.  int m, n, d;  
18.  long[][] a;  
19.   
20.  void run(){  
21.   t=sc.nextInt();  
22.   for(caze=1; caze<=t; caze++){  
23.    n=sc.nextInt();  
24.    m=sc.nextInt();  
25.    d=sc.nextInt();  
26.    a=new long[n][m];  
27.    for(int j=0; j<n; j++){  
28.     String s=sc.next();  
29.     for(int i=0; i<m; i++){  
30.      a[j][i]=s.charAt(i)-'0'+d;  
31.     }  
32.    }  
33.    solve();  
34.   }  
35.  }  
36.   
37.  long[][] mx1, mx2, my1, my2, m1, m2;  
38.  double gx, gy, g;  
39.   
40.  void solve(){  
41.   mx1=new long[n][m];  
42.   mx2=new long[n][m];  
43.   my1=new long[n][m];  
44.   my2=new long[n][m];  
45.   m1=new long[n][m];  
46.   m2=new long[n][m];  
47.   
48.   for(int j=0; j<n; j++){  
49.    mx1[j][0]=a[j][0]*0;  
50.    m1[j][0]=a[j][0];  
51.    for(int i=1; i<m; i++){  
52.     mx1[j][i]=mx1[j][i-1]+a[j][i]*i;  
53.     m1[j][i]=m1[j][i-1]+a[j][i];  
54.    }  
55.   }  
56.   
57.   for(int i=0; i<m; i++){  
58.    mx2[0][i]=mx1[0][i];  
59.    m2[0][i]=m1[0][i];  
60.    for(int j=1; j<n; j++){  
61.     mx2[j][i]=mx2[j-1][i]+mx1[j][i];  
62.     m2[j][i]=m2[j-1][i]+m1[j][i];  
63.    }  
64.   }  
65.   
66.   for(int i=0; i<m; i++){  
67.    my1[0][i]=a[0][i]*0;  
68.    for(int j=1; j<n; j++){  
69.     my1[j][i]=my1[j-1][i]+a[j][i]*j;  
70.    }  
71.   }  
72.   
73.   for(int j=0; j<n; j++){  
74.    my2[j][0]=my1[j][0];  
75.    for(int i=1; i<m; i++){  
76.     my2[j][i]=my2[j][i-1]+my1[j][i];  
77.    }  
78.   }  
79.   
80.   // 1クエリO(1)  
81.   int ans=0;  
82.   for(int y=0; y<n; y++){  
83.    for(int x=0; x<m; x++){  
84.     for(int w=3; x+w<=m&&y+w<=n; w++){  
85.      calc(x, y, w);  
86.      double mx=x+(w-1)/2.;  
87.      double my=y+(w-1)/2.;  
88.      if(abs(mx-gx)<EPS&&abs(my-gy)<EPS){  
89.       ans=max(ans, w);  
90.      }  
91.     }  
92.    }  
93.   }  
94.   answer(ans>0?(ans+""):"IMPOSSIBLE");  
95.   debug(ans);  
96.  }  
97.   
98.  void calc(int x, int y, int w){  
99.   gx=mx2[y+w-1][x+w-1];  
100.   gy=my2[y+w-1][x+w-1];  
101.   g=m2[y+w-1][x+w-1];  
102.   if(x>0){  
103.    gx-=mx2[y+w-1][x-1];  
104.    gy-=my2[y+w-1][x-1];  
105.    g-=m2[y+w-1][x-1];  
106.   }  
107.   if(y>0){  
108.    gx-=mx2[y-1][x+w-1];  
109.    gy-=my2[y-1][x+w-1];  
110.    g-=m2[y-1][x+w-1];  
111.   }  
112.   if(x>0&&y>0){  
113.    gx+=mx2[y-1][x-1];  
114.    gy+=my2[y-1][x-1];  
115.    g+=m2[y-1][x-1];  
116.   }  
117.   gx-=a[y][x]*x+a[y][x+w-1]*(x+w-1)+a[y+w-1][x]*x+a[y+w-1][x+w-1]*(x+w-1);  
118.   gy-=a[y][x]*y+a[y][x+w-1]*y+a[y+w-1][x]*(y+w-1)+a[y+w-1][x+w-1]*(y+w-1);  
119.   g-=a[y][x]+a[y][x+w-1]+a[y+w-1][x]+a[y+w-1][x+w-1];  
120.   gx/=g;  
121.   gy/=g;  
122.  }  
123.   
124.  void answer(String s){  
125.   println("Case #"+caze+": "+s);  
126.  }  
127.   
128.  void println(String s){  
129.   System.out.println(s);  
130.  }  
131.   
132.  void print(String s){  
133.   System.out.print(s);  
134.  }  
135.   
136.  void debug(Object... os){  
137.   System.err.println(Arrays.deepToString(os));  
138.  }  
139.   
140.  public static void main(String[] args){  
141.   try{  
142.    System.setIn(new FileInputStream(  
143.      "D:/contest_workspace/gcj_2011_round2/dat/B-large.in"));  
144.    System.setOut(new PrintStream(new FileOutputStream(  
145.      "D:/contest_workspace/gcj_2011_round2/dat/B-large.out")));  
146.   }catch(Exception e){}  
147.   
148.   new B().run();  
149.   System.out.flush();  
150.   System.out.close();  
151.  }  
152. }  

import java.util.*;
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);

 int INF=1<<28;
 double EPS=1e-9;

 int caze;
 int t;
 int m, n, d;
 long[][] a;

 void run(){
  t=sc.nextInt();
  for(caze=1; caze<=t; caze++){
   n=sc.nextInt();
   m=sc.nextInt();
   d=sc.nextInt();
   a=new long[n][m];
   for(int j=0; j<n; j++){
    String s=sc.next();
    for(int i=0; i<m; i++){
     a[j][i]=s.charAt(i)-'0'+d;
    }
   }
   solve();
  }
 }

 long[][] mx1, mx2, my1, my2, m1, m2;
 double gx, gy, g;

 void solve(){
  mx1=new long[n][m];
  mx2=new long[n][m];
  my1=new long[n][m];
  my2=new long[n][m];
  m1=new long[n][m];
  m2=new long[n][m];

  for(int j=0; j<n; j++){
   mx1[j][0]=a[j][0]*0;
   m1[j][0]=a[j][0];
   for(int i=1; i<m; i++){
    mx1[j][i]=mx1[j][i-1]+a[j][i]*i;
    m1[j][i]=m1[j][i-1]+a[j][i];
   }
  }

  for(int i=0; i<m; i++){
   mx2[0][i]=mx1[0][i];
   m2[0][i]=m1[0][i];
   for(int j=1; j<n; j++){
    mx2[j][i]=mx2[j-1][i]+mx1[j][i];
    m2[j][i]=m2[j-1][i]+m1[j][i];
   }
  }

  for(int i=0; i<m; i++){
   my1[0][i]=a[0][i]*0;
   for(int j=1; j<n; j++){
    my1[j][i]=my1[j-1][i]+a[j][i]*j;
   }
  }

  for(int j=0; j<n; j++){
   my2[j][0]=my1[j][0];
   for(int i=1; i<m; i++){
    my2[j][i]=my2[j][i-1]+my1[j][i];
   }
  }

  // 1クエリO(1)
  int ans=0;
  for(int y=0; y<n; y++){
   for(int x=0; x<m; x++){
    for(int w=3; x+w<=m&&y+w<=n; w++){
     calc(x, y, w);
     double mx=x+(w-1)/2.;
     double my=y+(w-1)/2.;
     if(abs(mx-gx)<EPS&&abs(my-gy)<EPS){
      ans=max(ans, w);
     }
    }
   }
  }
  answer(ans>0?(ans+""):"IMPOSSIBLE");
  debug(ans);
 }

 void calc(int x, int y, int w){
  gx=mx2[y+w-1][x+w-1];
  gy=my2[y+w-1][x+w-1];
  g=m2[y+w-1][x+w-1];
  if(x>0){
   gx-=mx2[y+w-1][x-1];
   gy-=my2[y+w-1][x-1];
   g-=m2[y+w-1][x-1];
  }
  if(y>0){
   gx-=mx2[y-1][x+w-1];
   gy-=my2[y-1][x+w-1];
   g-=m2[y-1][x+w-1];
  }
  if(x>0&&y>0){
   gx+=mx2[y-1][x-1];
   gy+=my2[y-1][x-1];
   g+=m2[y-1][x-1];
  }
  gx-=a[y][x]*x+a[y][x+w-1]*(x+w-1)+a[y+w-1][x]*x+a[y+w-1][x+w-1]*(x+w-1);
  gy-=a[y][x]*y+a[y][x+w-1]*y+a[y+w-1][x]*(y+w-1)+a[y+w-1][x+w-1]*(y+w-1);
  g-=a[y][x]+a[y][x+w-1]+a[y+w-1][x]+a[y+w-1][x+w-1];
  gx/=g;
  gy/=g;
 }

 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_round2/dat/B-large.in"));
   System.setOut(new PrintStream(new FileOutputStream(
     "D:/contest_workspace/gcj_2011_round2/dat/B-large.out")));
  }catch(Exception e){}

  new B().run();
  System.out.flush();
  System.out.close();
 }
}

■Result 38pts. 756th 念願のTシャツゲットです．もう少し頑張れば，Round3に進めたかもしれないですが，ここ最近で最高レベルに集中出来たので良かったと思います．