2011年6月29日水曜日

TCO Algorithm Round2

TCO Algorithm Round2(6/26 1:00~3:00)

驚異の悪運によりRound1を通過することが出来ていましたが,果してRound2は….

■GuessTheNumberGame(Easy)

ある数字Mを1~Nまでの数で割り切れるかどうかを表す文字列を考える. 例えばM=4,N=5とすると4は1,2,4で割り切れ,3,5では割り切れないので, YYNYN となる. さて,N=5のとき, YNNYN となるようなMは存在しないため, この文字列は無効である(4で割り切れて、2で割り切れないから). 長さMの文字列で,有効なものは何種類あるか. 2種類以上の素数の積からなる合成数は, 素因数のY or Nで一意に決まってしまうので,考慮しない. 例えば, YYY--XならX=Y YYN--XならX=N YNY--XならX=N YNN--XならX=N となる. 次に,ある素数の冪乗を考える. 例えば,M=9とすると,2の冪乗は2,4,8まで.この3つに着目した有効な文字列は, NNN YNN YYN YYY の4種類. つまり,p1, p2,…, prについて有効な文字列はr+1種類. あとは,それらを掛け合わせるだけ.
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

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

public class GuessTheNumberGame {
 // long INF=1L<<48;
 int INF=1<<28;
 double EPS=1e-9;

 public int possibleClues(int n) {
  long res=1;
  long mod=1000000007;
  boolean[] isP=new boolean[n+1];
  int[] p=new int[n+1];
  fill(isP,true);
  isP[0]=isP[1]=false;
  int k=0;
  for(int j=0;j<=n;j++){
   if(!isP[j]){
    continue;
   }
   p[k++]=j;
   for(int i=j*2;i<=n;i+=j){
    isP[i]=false;
   }
  }
  // debug(p);
  for(int i=0;i<k;i++){
   int c=0;
   for(long m=1;m<=n;m*=p[i]){
    c++;
   }
   // debug(i,p[i],c);
   res=(res*c)%mod;
  }
  return (int)res;
 }

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

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

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

■Challenge Phase

撃墜無し.

■Result

o-- +0/-0
196.11pts. 341th
辛くも逃げきることが出来ました.

■Rating

1431 -> 1530
Round3進出+初YellowCoderです. 今年のICPCは国内予選で落ちてしまったので,中々にショックでしたが, 代わりにGoogleとTopCoder両方のTシャツをゲットできそうです.

2011年6月23日木曜日

Aizu Online Judge 1149 Cut the Cakes

■1149 Cut the Cakes

やればできる.
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

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

public class Main{

 Scanner sc=new Scanner(System.in);

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

 int n, w, h;
 int[] ps, ss;

 void run(){
  for(;;){
   n=sc.nextInt();
   w=sc.nextInt();
   h=sc.nextInt();
   if((n|w|h)==0){
    break;
   }
   ps=new int[n];
   ss=new int[n];
   for(int i=0; i<n; i++){
    ps[i]=sc.nextInt()-1;
    ss[i]=sc.nextInt();
   }
   solve();
  }
 }

 void solve(){
  LinkedList<R> list=new LinkedList<R>();
  list.add(new R(0, 0, w, h));
  for(int i=0; i<n; i++){
   R r=list.remove(ps[i]);
   debug(i, r.x, r.y, r.w, r.h);
   int x=r.x, y=r.y;
   for(int k=0; k<ss[i]; k++){
    if(y==r.y&&x<r.x+r.w){
     x++;
    }else if(x==r.x+r.w&&y<r.y+r.h){
     y++;
    }else if(y==r.y+r.h&&x>r.x){
     x--;
    }else if(x==r.x&&y>r.y){
     y--;
    }else{
     debug("Error!");
    }
    // debug(x,y);
   }
   debug(x, y);
   R r1=null, r2=null;
   if(x==r.x||x==r.x+r.w){
    r1=new R(r.x, r.y, r.w, y-r.y);
    r2=new R(r.x, r.y+r1.h, r.w, r.h-r1.h);
   }else{
    r1=new R(r.x, r.y, x-r.x, r.h);
    r2=new R(r.x+r1.w, r.y, r.w-r1.w, r.h);
   }
   debug("r1", r1.x, r1.y, r1.w, r1.h);
   debug("r2", r2.x, r2.y, r2.w, r2.h);
   if(r1.w*r1.h<r2.w*r2.h){
    list.add(r1);
    list.add(r2);
   }else{
    list.add(r2);
    list.add(r1);
   }
  }
  R[] rs=list.toArray(new R[0]);
  sort(rs);
  String ans="";
  for(R r : rs){
   ans+=(r.w*r.h)+" ";
   debug(r.x, r.y, r.w, r.h, r.w*r.h);
  }
  println(ans.substring(0, ans.length()-1));
 }

 class R implements Comparable<R>{
  int x, y, w, h;

  R(int x, int y, int w, int h){
   this.x=x;
   this.y=y;
   this.w=w;
   this.h=h;
  }

  @Override
  public int compareTo(R r){
   return w*h-r.w*r.h;
  }
 }

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

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

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

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

Aizu Online Judge 1131 Unit Fraction Partition

■1131 Unit Fraction Partition

自明な+ちょっと工夫した枝刈りでAC.
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

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

public class Main{

 Scanner sc=new Scanner(System.in);

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

 int p0, q0, maxA, maxN;
 int ans;

 void run(){
  for(;;){
   p0=sc.nextInt();
   q0=sc.nextInt();
   maxA=sc.nextInt();
   maxN=sc.nextInt();
   if((p0|q0|maxA|maxN)==0){
    break;
   }
   solve();
  }
 }

 void solve(){
  int gcd=gcd(p0, q0);
  p0/=gcd;
  q0/=gcd;
  ans=0;
  dfs(0, 1, 1, 1, 0);
  // debug(ans);
  println(""+ans);
 }

 void dfs(int p, int q, int qNow, int a, int n){
  if(n>maxN){
   return;
  }
  if(a>maxA){
   return;
  }
  if(p*q0-q*p0>0){
   return;
  }
  {
   int p2=maxN-n;
   int q2=qNow;
   int pp=p*q2+q*p2;
   int qq=q*q2;
   if(pp*q0-qq*p0<0){
    return;
   }
  }
  // debug(p,q,qNow,a,n);
  if(p==p0&&q==q0){
   ans++;
   return;
  }
  for(int i=qNow; i*a<=maxA; i++){
   int p2=p*i+q;
   int q2=q*i;
   int gcd=gcd(p2, q2);
   p2/=gcd;
   q2/=gcd;
   dfs(p2, q2, i, i*a, n+1);
  }
 }

 int gcd(int m, int n){
  for(; m!=0;){
   int t=n%m;
   n=m;
   m=t;
  }
  return n;
 }

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

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

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

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

2011年6月20日月曜日

Aizu Online Judge 1156 Twirling Robot

■1156 Twirling Robot

(x座標,y座標,方向ベクトル)を状態としたDijkstra.コストのつけ方が特殊だが,少し注意すれば特に問題無い.
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

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

public class Main{

 Scanner sc=new Scanner(System.in);

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

 int m, n;
 int[][] a;
 int[] c;

 void run(){
  for(;;){
   m=sc.nextInt();
   n=sc.nextInt();
   if((m|n)==0){
    break;
   }
   a=new int[n][m];
   for(int j=0; j<n; j++){
    for(int i=0; i<m; i++){
     a[j][i]=sc.nextInt();
    }
   }
   c=new int[4];
   for(int i=0; i<4; i++){
    c[i]=sc.nextInt();
   }
   solve();
  }
 }

 void solve(){
  int[][][] d=new int[n][m][4];
  for(int j=0; j<n; j++){
   for(int i=0; i<m; i++){
    fill(d[j][i], INF);
   }
  }
  int[] dx={1, 0, -1, 0};
  int[] dy={0, 1, 0, -1};
  PriorityQueue<P> que=new PriorityQueue<P>();
  que.offer(new P(0, 0, 0));
  d[0][0][0]=0;
  for(; !que.isEmpty();){
   P p=que.poll();
   if(p.d>d[p.y][p.x][p.v]){
    continue;
   }
   int[] cost=c.clone();
   if(a[p.y][p.x]!=4){
    cost[a[p.y][p.x]]=0;
   }
   for(int i=0; i<4; i++){
    P q=new P(p.x, p.y, (p.v+i)%4);
    q.x+=dx[q.v];
    q.y+=dy[q.v];
    if(q.x<0||q.x>=m||q.y<0||q.y>=n){
     continue;
    }
    if(d[q.y][q.x][q.v]>d[p.y][p.x][p.v]+cost[i]){
     q.d=d[q.y][q.x][q.v]=d[p.y][p.x][p.v]+cost[i];
     que.offer(q);
    }
   }
  }
  int ans=INF;
  for(int i=0; i<4; i++){
   ans=min(ans, d[n-1][m-1][i]);
  }
  println(ans+"");
 }

 class P implements Comparable<P>{
  int x, y, v;
  int d;

  P(int x, int y, int v){
   this.x=x;
   this.y=y;
   this.v=v;
  }

  @Override
  public int compareTo(P p){
   return d-p.d;
  }
 }

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

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

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

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

Aizu Online Judge 1136 Polygonal Line Search

■1136 Polygonal Line Search

回転および平行移動を適用したということは,各々の線分ベクトルを0,90,180,270°の何れかの角度回転させたことになる.従って,元の折れ線の内の1つの線分ベクトルと,探す対象の折れ線の内の1つの線分ベクトルを見れば何度回転させたか分かる.あとは,残りの線分ベクトルを回転させ,元の折れ線の線分ベクトルに一致するかを見ていけば良い.
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

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

public class Main{

 Scanner sc=new Scanner(System.in);

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

 int n;
 int[] m;
 int[][] xs, ys;

 void run(){
  for(;;){
   n=sc.nextInt();
   if(n==0){
    break;
   }
   m=new int[n+1];
   xs=new int[n+1][];
   ys=new int[n+1][];
   for(int j=0; j<=n; j++){
    m[j]=sc.nextInt();
    xs[j]=new int[m[j]];
    ys[j]=new int[m[j]];
    for(int i=0; i<m[j]; i++){
     xs[j][i]=sc.nextInt();
     ys[j][i]=sc.nextInt();
    }
   }
   solve();
  }
 }

 void solve(){
  for(int i=1; i<=n; i++){
   if(m[0]==m[i]&&match(m[0], xs[0], ys[0], xs[i], ys[i])){
    println(i+"");
   }
  }
  println("+++++");
 }

 boolean match(int m, int[] xs1, int[] ys1, int[] xs2, int[] ys2){
  int[][][] a={{{1, 0}, {0, 1}}, {{0, -1}, {1, 0}}, {{-1, 0}, {0, -1}},
    {{0, 1}, {-1, 0}}};

  int k1=-1, k2=-1;
  for(int j=0; j<4; j++){
   int vx1=xs1[1]-xs1[0];
   int vy1=ys1[1]-ys1[0];
   int vx2=xs2[1]-xs2[0];
   int vy2=ys2[1]-ys2[0];
   if(vx1*a[j][0][0]+vy1*a[j][0][1]==vx2
     &&vx1*a[j][1][0]+vy1*a[j][1][1]==vy2){
    k1=j;
   }
   int vx3=xs2[m-2]-xs2[m-1];
   int vy3=ys2[m-2]-ys2[m-1];
   if(vx1*a[j][0][0]+vy1*a[j][0][1]==vx3
     &&vx1*a[j][1][0]+vy1*a[j][1][1]==vy3){
    k2=j;
   }
  }

  boolean f1=k1!=-1, f2=k2!=-1;
  for(int i=0; i<m-1; i++){
   int vx1=xs1[i+1]-xs1[i];
   int vy1=ys1[i+1]-ys1[i];
   int vx2=xs2[i+1]-xs2[i];
   int vy2=ys2[i+1]-ys2[i];
   int vx3=xs2[m-i-2]-xs2[m-i-1];
   int vy3=ys2[m-i-2]-ys2[m-i-1];
   if(k1!=-1){
    f1&=vx1*a[k1][0][0]+vy1*a[k1][0][1]==vx2
      &&vx1*a[k1][1][0]+vy1*a[k1][1][1]==vy2;
   }
   if(k2!=-1){
    f2&=vx1*a[k2][0][0]+vy1*a[k2][0][1]==vx3
      &&vx1*a[k2][1][0]+vy1*a[k2][1][1]==vy3;
   }
  }

  return f1||f2;
 }

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

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

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

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

CodeChef June Cook-off 2011

CodeChef June Cook-off 2011(6/20 1:00~3:30)

■Correctness of Knight Move

やるだけ.出力をバッファリングしないとTLEします(しました).
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

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

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

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

 int n;
 String s;

 void run(){
  n=sc.nextInt();
  sc.nextLine();
  String[] ans={"Yes", "No", "Error"};
  for(int i=0; i<n; i++){
   s=sc.nextLine();
   println(ans[solve()]);
  }
  System.out.flush();
 }

 int solve(){
  boolean legal=true;
  if(s.length()!=5){
   return 2;
  }
  legal&='a'<=s.charAt(0)&&s.charAt(0)<='h';
  legal&='1'<=s.charAt(1)&&s.charAt(1)<='8';
  legal&=s.charAt(2)=='-';
  legal&='a'<=s.charAt(3)&&s.charAt(3)<='h';
  legal&='1'<=s.charAt(4)&&s.charAt(4)<='8';
  if(!legal){
   return 2;
  }
  int x1=s.charAt(0)-'a';
  int y1=s.charAt(1)-'1';
  int x2=s.charAt(3)-'a';
  int y2=s.charAt(4)-'1';

  int dx=abs(x1-x2);
  int dy=abs(y1-y2);

  return (dx==1&&dy==2)||(dx==2&&dy==1)?0:1;
 }

 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){
  System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

■Super-plane

Dunnoの挙動は分岐無しなので,適当なループで解けます.コンテスト中は勘違いしていて,BFSをしようとしてTLE食らいまくっていました.さらに,Javaの入出力がバッファリングしてなかったため,少し調整しないと通りませんでした.
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

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

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

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

 int t, n;
 int cs, ts, cg, tg;
 E[] es;

 void run() throws Exception{
  BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
  t=Integer.parseInt(br.readLine());
  for(; t>0; t--){
   n=Integer.parseInt(br.readLine());
   es=new E[n];
   for(int i=0; i<n; i++){
    String[] ss=br.readLine().split(" ");
    int c1=Integer.parseInt(ss[0])-1;
    int t1=Integer.parseInt(ss[1]);
    int c2=Integer.parseInt(ss[2])-1;
    int t2=Integer.parseInt(ss[3]);
    es[i]=new E(c1, t1, c2, t2);
   }
   sort(es);
   String[] ss=br.readLine().split(" ");
   cs=Integer.parseInt(ss[0])-1;
   ts=Integer.parseInt(ss[1]);
   cg=Integer.parseInt(ss[2])-1;
   tg=Integer.parseInt(ss[3]);
   solve();
  }
  System.out.flush();
 }

 void solve(){
  P p=new P(cs, ts);
  boolean[] visited=new boolean[n];
  int ans=0;
  boolean ok=true;
  E key=new E(p.c, p.t, 0, 0);
  for(;; ans++){
   if(p.c==cg&&p.t<=tg){
    break;
   }
   key.c1=p.c;
   key.t1=p.t;
   int k=binarySearch(es, key);
   if(k<0){
    k=-1-k;
   }
   if(k==n){
    ok=false;
    break;
   }
   if(es[k].c1!=p.c){
    ok=false;
    break;
   }
   if(visited[k]){
    ok=false;
    break;
   }
   visited[k]=true;
   p.c=es[k].c2;
   p.t=es[k].t2;
  }
  if(ok){
   println("Yes "+ans);
  }else{
   println("No");
  }
 }

 class E implements Comparable<E>{
  int c1, t1, c2, t2;

  E(int c1, int t1, int c2, int t2){
   this.c1=c1;
   this.t1=t1;
   this.c2=c2;
   this.t2=t2;
  }

  @Override
  public int compareTo(E e){
   if(c1!=e.c1){
    return c1-e.c1;
   }else{
    return t1-e.t1;
   }
  }
 }

 class P implements Comparable<P>{
  int c, t;

  P(int c, int t){
   this.c=c;
   this.t=t;
  }

  @Override
  public int compareTo(P p){
   if(c!=p.c){
    return c-p.c;
   }else{
    return t-p.t;
   }
  }
 }

 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){
  System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  try{
   new Main().run();
  }catch(Exception e){
   e.printStackTrace();
  }
 }
}

■Result

--o--

またもやこれは酷い….CodeChefとは相性が悪いようです.C++に乗り換えるのも手だと思われます.

2011年6月19日日曜日

TCO Algorithm Round1

TCO Algorithm Round1(6/19 1:00~3:00)

■TripleStrings(Easy)

キューA,B,Cがある. 最初,キューAには'o'と'x'から構成される文字列(=init)が入っており,キューB,Cは空である. Aからポップした文字は,BとCにプッシュできる. B,Cからポップした文字は,Aにプッシュできる. キューA内の文字列をinitからgoalに変更するためのポップの回数の最小値を返せ.
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

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

public class TripleStrings {
 // long INF=1L<<48;
 int INF=1<<28;
 double EPS=1e-9;

 public int getMinimumOperations(String init, String goal) {
  int n=init.length();
  int max=0;
  for(int j=1;j<=n;j++){
   boolean f=true;
   for(int i=0;i<j;i++){
    f&=init.charAt(n-j+i)==goal.charAt(i);
   }
   if(f){
    max=max(max,j);
   }
  }
  return (n-max)*2;
 }

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

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

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

■Challenge Phase

撃墜無し.Challengeボタンをポチるコンマ数秒前に他の人に撃墜されました.

■Result

o-- +0/-0
232.61pts. 837th

■Rating

1414 -> 1431
残念….

2011年6月7日火曜日

Aizu Online Judge 1155 How can I satisfy thee? Let me count the ways...

■1155 How can I satisfy thee? Let me count the ways...

構文解析ゲー.変数への数の割り当て方は高々27通りなので,全部試せば良い.
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

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

// AC
public class Main{

 Scanner sc=new Scanner(System.in);

 String s;
 int[] map;

 void run(){
  for(;;){
   s=sc.next();
   if(s.equals(".")){
    break;
   }
   solve();
  }
 }

 void solve(){
  map=new int[256];
  map['0']=0;
  map['1']=1;
  map['2']=2;
  int ans=0;
  for(int p=0; p<3; p++){
   for(int q=0; q<3; q++){
    for(int r=0; r<3; r++){
     map['P']=p;
     map['Q']=q;
     map['R']=r;
     Result res=f(0);
     if(res.value==2){
      ans++;
     }
    }
   }
  }
  println(ans+"");
 }

 Result f(int p){
  // debug("f",p);
  if(Character.isDigit(s.charAt(p))||Character.isUpperCase(s.charAt(p))){
   return new Result(p+1, map[s.charAt(p)]);
  }else if(s.charAt(p)=='-'){
   Result r=f(p+1);
   r.value=2-r.value;
   return r;
  }else{
   Result r=f(p+1);
   Result r2=f(r.p+1); // skip '*' or '+'
   if(s.charAt(r.p)=='*'){
    r.value=min(r.value, r2.value);
   }else{ // '+'
    r.value=max(r.value, r2.value);
   }
   r.p=r2.p+1;
   return r;
  }
 }

 class Result{
  int p, value;

  Result(int p, int value){
   this.p=p;
   this.value=value;
  }
 }

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

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

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

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

Aizu Online Judge 1244 Molecular Formula

■1244 Molecular Formula

構文解析ゲー.
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

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

// AC
public class Main{

 Scanner sc=new Scanner(System.in);

 HashMap<String, Integer> map;
 String s;
 boolean unknown;

 void run(){
  map=new HashMap<String, Integer>();
  for(;;){
   String s=sc.next();
   if(s.equals("END_OF_FIRST_PART")){
    break;
   }
   int n=sc.nextInt();
   map.put(s, n);
  }
  for(;;){
   s=sc.next();
   if(s.equals("0")){
    break;
   }
   s+='\0';
   unknown=false;
   Result r=molecule(0);
   println(unknown?"UNKNOWN":r.value+"");
   debug(r.p, r.value);
  }
 }

 Result molecule(int p){
  debug("molecule", p);
  Result r=new Result(p, 0);
  for(;;){
   if(s.charAt(r.p)=='\0'||s.charAt(r.p)==')'){
    // end of molecule
    return r;
   }else if(s.charAt(r.p)=='('){
    Result r1=molecule(r.p+1);
    Result r2=number(r1.p+1); // skip '('
    r.value+=r1.value*r2.value;
    r.p=r2.p;
   }else{
    Result r1=atom(r.p);
    Result r2=number(r1.p);
    r.value+=r1.value*r2.value;
    r.p=r2.p;
   }
  }
 }

 Result atom(int p){
  debug("atom", p);
  String atom="";
  if(Character.isUpperCase(s.charAt(p))){
   atom+=s.charAt(p);
   p++;
   if(Character.isLowerCase(s.charAt(p))){
    atom+=s.charAt(p);
    p++;
   }
  }
  debug(atom);
  if(map.containsKey(atom)){
   return new Result(p, map.get(atom));
  }else{
   unknown=true;
   return new Result(p, 0);
  }
 }

 Result number(int p){
  debug("number", p);
  int value=0;
  if(Character.isDigit(s.charAt(p))){
   value=s.charAt(p)-'0';
   p++;
   if(Character.isDigit(s.charAt(p))){
    value=value*10+s.charAt(p)-'0';
    p++;
   }
  }else{
   return new Result(p, 1);
  }
  return new Result(p, value);
 }

 class Result{
  int p, value;

  Result(int p, int value){
   this.p=p;
   this.value=value;
  }
 }

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

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

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

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

Aizu Online Judge 1012 Operations with Finite Sets

■1012 Operations with Finite Sets

構文解析ゲー.
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

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

// AC
public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;
 TreeSet<Integer>[] sets;
 String exp;
 TreeSet<Integer> U;

 @SuppressWarnings("unchecked")
 void run(){
  for(; sc.hasNext();){
   sets=new TreeSet[256];
   for(char c='A'; c<='E'; c++){
    sets[c]=new TreeSet<Integer>();
   }
   U=new TreeSet<Integer>();
   for(;;){
    char c=sc.next().charAt(0);
    int n=sc.nextInt();
    if(c=='R'&&n==0){
     break;
    }
    for(int i=0; i<n; i++){
     int e=sc.nextInt();
     sets[c].add(e);
     U.add(e);
    }
   }
   exp=sc.next();
   solve();
  }
 }

 void solve(){
  exp+='\0';
  Result r=e(0);
  debug(r.set.toArray());
  if(r.set.size()==0){
   println("NULL");
  }else{
   for(Iterator<Integer> it=r.set.iterator(); it.hasNext();){
    print(it.next()+(it.hasNext()?" ":"\n"));
   }
  }
 }

 Result e(int p){
  debug("e", p);
  Result r=f(p);
  debug(r.set.toArray(), r.p);
  for(;;){
   if(op(exp.charAt(r.p))){
    Result r2=f(r.p+1);
    switch(exp.charAt(r.p)){
    case 'u': // or
     r.set.addAll(r2.set);
     break;
    case 'i': // and
     for(int e : U){
      if(r.set.contains(e)&&r2.set.contains(e)){}else{
       r.set.remove(e);
      }
     }
     break;
    case 'd': // diff
     r.set.removeAll(r2.set);
     break;
    case 's': // sym
     for(int e : U){
      if(r.set.contains(e)&&r2.set.contains(e)){
       r.set.remove(e);
      }else if(r2.set.contains(e)){
       r.set.add(e);
      }
     }
     break;
    }
    r.p=r2.p;
   }else{
    break;
   }
  }
  return r;
 }

 boolean op(char c){
  return c=='u'||c=='i'||c=='d'||c=='s';
 }

 Result f(int p){
  debug("f", p);
  if(exp.charAt(p)=='c'){
   Result r=f(p+1);
   TreeSet<Integer> c=new TreeSet<Integer>();
   for(int e : U){
    if(!r.set.contains(e)){
     c.add(e);
    }
   }
   r.set.clear();
   r.set.addAll(c);
   return r;
  }else{
   return t(p);
  }
 }

 Result t(int p){
  debug("t", p);
  if(exp.charAt(p)=='('){
   Result r=e(p+1);
   r.p++; // skip ')'
   return r;
  }else{
   Result r=new Result(p+1);
   r.set.addAll(sets[exp.charAt(p)]);
   return r;
  }
 }

 class Result{
  int p;
  TreeSet<Integer> set;

  Result(int p){
   this.p=p;
   set=new TreeSet<Integer>();
  }
 }

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

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

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

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

Aizu Online Judge 1162 Discrete Speed

■1162 Discrete Speed

拡張ダイクストラ.
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

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

// AC
public class Main{

 Scanner sc=new Scanner(System.in);

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

 int n, m;
 int s, g;
 LinkedList<E>[] es;

 @SuppressWarnings("unchecked")
 void run(){
  for(;;){
   n=sc.nextInt();
   m=sc.nextInt();
   if((n|m)==0){
    break;
   }
   es=new LinkedList[n];
   for(int i=0; i<n; i++){
    es[i]=new LinkedList<E>();
   }
   s=sc.nextInt()-1;
   g=sc.nextInt()-1;
   for(int i=0; i<m; i++){
    int x=sc.nextInt()-1;
    int y=sc.nextInt()-1;
    int d=sc.nextInt();
    int c=sc.nextInt();
    es[x].add(new E(y, d, c));
    es[y].add(new E(x, d, c));
   }
   solve();
  }
 }

 void solve(){
  // [前][今][前から今の速度]
  double[][][] d=new double[n][n][40];
  PriorityQueue<P> que=new PriorityQueue<P>();
  for(int j=0; j<n; j++){
   for(int i=0; i<n; i++){
    fill(d[j][i], INF);
   }
  }
  d[s][s][1]=0;
  que.offer(new P(s, s, 0, 0));
  for(; !que.isEmpty();){
   P p=que.poll();
   if(d[p.q][p.p][p.v]+EPS<p.d){
    continue;
   }
   for(E e : es[p.p]){
    if(p.q==e.to){
     continue;
    }
    for(int i=-1; i<=1; i++){
     if(p.v+i<=0||p.v+i>e.c){
      continue;
     }
     if(d[p.p][e.to][p.v+i]>p.d+(double)e.d/(p.v+i)+EPS){
      d[p.p][e.to][p.v+i]=p.d+(double)e.d/(p.v+i);
      que.offer(new P(p.p, e.to, p.v+i, d[p.p][e.to][p.v+i]));
     }
    }
   }
  }
  double min=INF;
  for(int i=0; i<n; i++){
   min=min(min, d[i][g][1]);
  }
  println(""+(min<INF/2?min:"unreachable"));
 }

 class E{
  int to, d, c;

  E(int to, int d, int c){
   this.to=to;
   this.d=d;
   this.c=c;
  }
 }

 class P implements Comparable<P>{
  int q, p, v;
  double d;

  P(int q, int p, int v, double d){
   this.q=q;
   this.p=p;
   this.v=v;
   this.d=d;
  }

  @Override
  public int compareTo(P p){
   if(d+EPS<p.d){
    return -1;
   }else if(d>p.d+EPS){
    return 1;
   }else{
    return 0;
   }
  }

 }

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

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

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

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

Aizu Online Judge 1161 Verbal Arithmetic

■1161 Verbal Arithmetic

非常に汚い探索による解法.
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

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

// AC
public class Main{

 Scanner sc=new Scanner(System.in);

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

 int n;
 String[] ss;

 void run(){
  for(;;){
   n=sc.nextInt();
   if(n==0){
    break;
   }
   ss=new String[n];
   for(int i=0; i<n; i++){
    ss[i]=sc.next();
   }
   solve();
  }
 }

 int size;
 int[] cs;
 int[] map;
 boolean[] used;
 int ans;

 void solve(){
  int[] a=new int[256];
  fill(a, -1);
  size=0;
  for(String s : ss){
   for(int i=0; i<s.length(); i++){
    if(a[s.charAt(i)]==-1){
     size++;
     a[s.charAt(i)]=INF;
    }
    a[s.charAt(i)]=min(a[s.charAt(i)], s.length()-1-i);
   }
  }
  cs=new int[size];
  for(int k=0, i=0; i<256; i++){
   if(a[i]>=0){
    cs[k++]=i+1000*a[i];
   }
  }
  sort(cs);

  used=new boolean[10];
  map=new int[256];
  fill(map, -1);
  ans=0;
  dfs(0);
  println(""+ans);
 }

 void dfs(int k){
  if(k==size){
   if(ok(8)){
    ans++;
   }
   return;
  }
  for(int i=0; i<10; i++){
   if(!used[i]){
    used[i]=true;
    map[cs[k]%1000]=i;
    if(ok(cs[k]/1000)){
     dfs(k+1);
    }
    map[cs[k]%1000]=-1;
    used[i]=false;
   }
  }
 }

 boolean ok(int d){
  int sum=0;
  for(int j=0; j<n; j++){
   if(map[ss[j].charAt(0)]==0&&ss[j].length()>1){
    return false;
   }
   int num=0;
   for(int i=max(0, d-ss[j].length()); i<d; i++){
    num=num*10+map[ss[j].charAt(ss[j].length()-d+i)];
   }
   if(j==n-1){
    sum-=num;
   }else{
    sum+=num;
   }
  }
  int mod=1;
  for(int i=0; i<d; i++){
   mod*=10;
  }
  return sum%mod==0;
 }

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

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

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

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}

Aizu Online Judge 1133 Water Tank

■1133 Water Tank

実装ゲー.
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import javax.swing.*;
import java.awt.*;

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

// AC
public class Main{

 Scanner sc=new Scanner(System.in);

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

 int d;
 int n;
 int[] x, h;
 int m;
 int[] f, dv;
 int l;
 int[] p, t;

 void run(){
  d=sc.nextInt();
  for(int k=0; k<d; k++){
   n=sc.nextInt()+1;
   x=new int[n+1];
   h=new int[n+1];
   x[0]=0;
   x[n]=100;
   h[0]=h[n]=50;
   for(int i=1; i<n; i++){
    x[i]=sc.nextInt();
    h[i]=sc.nextInt();
   }
   m=sc.nextInt();
   f=new int[m];
   dv=new int[m];
   for(int i=0; i<m; i++){
    f[i]=sc.nextInt();
    dv[i]=sc.nextInt();
   }
   l=sc.nextInt();
   p=new int[l];
   t=new int[l];
   for(int i=0; i<l; i++){
    p[i]=sc.nextInt();
    t[i]=sc.nextInt();
   }
   solve();
  }
 }

 double[] y, a;
 double time;

 void solve(){
  y=new double[n];
  a=new double[n];
  for(int j=0; j<m; j++){
   for(int i=0; i<n; i++){
    if(x[i]<f[j]&&f[j]<x[i+1]){
     a[i]+=dv[j]/30.0;
    }
   }
  }
  // Visualizer v=new Visualizer();

  double[] ans=new double[l];
  fill(ans, -1);

  for(time=0;;){
   double min=INF;
   for(int i=0; i<n; i++){
    if(a[i]>EPS){
     if(y[i]+EPS<h[i]){
      min=min(min, (h[i]-y[i])*(x[i+1]-x[i])/a[i]);
     }
     if(y[i]+EPS<h[i+1]){
      min=min(min, (h[i+1]-y[i])*(x[i+1]-x[i])/a[i]);
     }
    }
   }
   if(min==INF){
    for(;;);
   }
   for(int j=0; j<l; j++){
    if(time<t[j]+EPS&&t[j]+EPS<time+min){
     for(int i=0; i<n; i++){
      if(x[i]<p[j]&&p[j]<x[i+1]){
       ans[j]=min(y[i]+(t[j]-time)*a[i]/(x[i+1]-x[i]), 50);
      }
     }
    }
   }
   boolean all50=true;
   time+=min;
   for(int i=0; i<n; i++){
    y[i]+=min*a[i]/(x[i+1]-x[i]);
    all50&=abs(y[i]-50)<EPS;
   }
   // v.repaint();
   // sleep(1000);

   if(all50){
    break;
   }
   double[] a2=new double[n];

   for(int j=0; j<n; j++){
    boolean[] bottom=new boolean[n];
    int left, right;
    for(left=j; left>=0&&y[left]+EPS>h[left]; left--);
    for(right=j; right<n&&y[right]+EPS>h[right+1]; right++);

    if(y[left]+EPS<y[j]){
     for(int i=left; i<n&&abs(y[i]-y[left])<EPS; i++){
      bottom[i]=true;
     }
    }
    if(y[right]+EPS<y[j]){
     for(int i=right; i>=0&&abs(y[i]-y[right])<EPS; i--){
      bottom[i]=true;
     }
    }
    if(abs(y[left]-y[j])<EPS&&abs(y[right]-y[j])<EPS){
     for(int i=left; i<=right; i++){
      bottom[i]=true;
     }
    }
    int sum=0;
    for(int i=0; i<n; i++){
     if(bottom[i]){
      sum+=x[i+1]-x[i];
     }
    }
    for(int i=0; i<n; i++){
     if(bottom[i]){
      a2[i]+=a[j]/sum*(x[i+1]-x[i]);
     }
    }
   }
   a=a2.clone();
  }
  for(int i=0; i<l; i++){
   println(ans[i]+EPS<0?"50.0":ans[i]+"");
  }
 }

 void sleep(long millis){
  try{
   Thread.sleep(millis);
  }catch(InterruptedException e){
   e.printStackTrace();
  }
 }

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

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

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

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }

 public class Visualizer extends JFrame{
  Visualizer(){
   setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
   setVisible(true);
   getContentPane().add(new MainPanel(), BorderLayout.CENTER);
   pack();
  }

  class MainPanel extends JPanel{
   MainPanel(){
    setPreferredSize(new Dimension(512, 512));
   }

   public void paintComponent(Graphics g){
    int width=getWidth();
    int height=getHeight();
    for(int i=0; i<n; i++){
     g.setColor(Color.BLUE);
     g.fillRect(x[i]*4, height-(int)(y[i]*4), (x[i+1]-x[i])*4,
       (int)(y[i]*4));
     g.drawString(String.format("%.4f", a[i]), x[i]*4, height/2);
    }

    for(int i=0; i<=n; i++){
     g.setColor(Color.RED);
     g.drawLine(x[i]*4, height-h[i]*4, x[i]*4, height);
    }

    g.setColor(Color.BLACK);
    g.drawString(""+time, 100, 100);
   }
  }
 }
}

2011年6月6日月曜日

IPSC 2011

IPSC 2011(19:00~24:00)

ユニークな問題がたくさんありました.

■A - Against a rock play Spock

やるだけ.

■C - Candy for each guess

Easyだけなら全探索.Hannahは別に答えを変える必要な無く.最適なもの一つをひたすら用いればよい.

■D - Divide the rectangle

Easyだけ提出.

■F - Flipping coins

Easyだけ.全探索したら,本当に確率が50%を越えたので吃驚.

■M - My little puppy

わんちゃんが何か言ってくるので,それに対する正しい反応を返答する.
趣旨が分かりませんでしたが,面白かった(?)です.

■Result

6AC (A1 A2 C1 D1 F1 [M+++++])
256th

半端な順位です.

Bの解を,kinabaさんやuwiさんが画像でアップしていましたが,フラクタルな構造をしていました.思い付かなかった.

UAPC 2011

UAPC 2011(6/5 13:00~18:00)

GCJ疲れが影響して,惨敗しました.

■A. It's our delight!!

やるだけ.

■K. Rearranging Seats

合計席数が偶数なら絶対に存在する.逆に奇数では絶対に存在しない.

■Result

2AC 74th
駄目駄目でした.

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

全探索で解ける.
愚直に実装すると,(x1, y1)-(x1, y1) からなる長方形の重心を求めるための計算量は, O(n5)となり(8分間では)絶対に間に合わない.
そこで,部分和を使う.
MX1(i, j)=Σ0≦k≦ia(k, j)k
MY1(i, j)=Σ0≦k≦ja(i, k)k
とする.
これで,ある行 or 列に対するある範囲の質量×位置の総和がO(1)で求まるため, 総計算量は、O(n4)になる.しかし,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(n3)になり間に合う.
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に進めたかもしれないですが,ここ最近で最高レベルに集中出来たので良かったと思います.

TopCoder SRM 508

SRM 508(6/3 0:00~2:00)

■DivideAndShift(Easy)

答えをf(n,m)として,再帰的に解きました.
素因数分解をして,素数のべき乗ごとに再帰するので, 制限時間には余裕で間に合います.
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

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

public class DivideAndShift {
 int INF=1<<28;
 double EPS=1e-9;

 int rec(int n, int m){
  if(m==0){
   return 0;
  }
  HashMap<Integer,Integer> map=primeFactor(n);
  int res=min(m,n-m);
  for(int p:map.keySet()){
   if(p==1){
    continue;
   }
   res=min(res,rec(n/p,m%(n/p))+1);
  }
  return res;
 }

 public int getLeast(int n, int m) {
  return rec(n,m-1);
 }
 
 HashMap<Integer, Integer> primeFactor(int n){
  HashMap<Integer, Integer> map=new HashMap<Integer, Integer>();
  for(int i=2; i*i<=n; i++){
   int c=0;
   for(; n%i==0; n/=i)
    c++;
   if(c>0)
    map.put(i, c);
  }
  if(n!=1)
   map.put(n, 1);
  return map;
 }

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

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

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

■Challenge Phase

撃墜無し.

■Result

o-- +0/-0
125.55pts. 406th

■Rating

1365 -> 1414
微増.目標の1500にはいつ到達できるのか….