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]になるように気をつける．

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³)になり間に合う．

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に進めたかもしれないですが，ここ最近で最高レベルに集中出来たので良かったと思います．