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種類． あとは，それらを掛け合わせるだけ．
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 GuessTheNumberGame {  
  10.  // long INF=1L<<48;  
  11.  int INF=1<<28;  
  12.  double EPS=1e-9;  
  13.   
  14.  public int possibleClues(int n) {  
  15.   long res=1;  
  16.   long mod=1000000007;  
  17.   boolean[] isP=new boolean[n+1];  
  18.   int[] p=new int[n+1];  
  19.   fill(isP,true);  
  20.   isP[0]=isP[1]=false;  
  21.   int k=0;  
  22.   for(int j=0;j<=n;j++){  
  23.    if(!isP[j]){  
  24.     continue;  
  25.    }  
  26.    p[k++]=j;  
  27.    for(int i=j*2;i<=n;i+=j){  
  28.     isP[i]=false;  
  29.    }  
  30.   }  
  31.   // debug(p);  
  32.   for(int i=0;i<k;i++){  
  33.    int c=0;  
  34.    for(long m=1;m<=n;m*=p[i]){  
  35.     c++;  
  36.    }  
  37.    // debug(i,p[i],c);  
  38.    res=(res*c)%mod;  
  39.   }  
  40.   return (int)res;  
  41.  }  
  42.   
  43.  void debug(Object...os){  
  44.   System.err.println(Arrays.deepToString(os));  
  45.  }  
  46.   
  47.  void print(String s){  
  48.   System.out.print(s);  
  49.  }  
  50.   
  51.  void println(String s){  
  52.   System.out.println(s);  
  53.  }  
  54. }  

■Challenge Phase

撃墜無し．

■Result

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

■Rating

1431 -> 1530
Round3進出+初YellowCoderです． 今年のICPCは国内予選で落ちてしまったので，中々にショックでしたが， 代わりにGoogleとTopCoder両方のTシャツをゲットできそうです．
投稿者 時刻: 0 件のコメント:
ラベル:

2011年6月23日木曜日

Aizu Online Judge 1149 Cut the Cakes

■1149 Cut the Cakes

やればできる．
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 Main{  
  10.   
  11.  Scanner sc=new Scanner(System.in);  
  12.   
  13.  int INF=1<<28;  
  14.  double EPS=1e-9;  
  15.   
  16.  int n, w, h;  
  17.  int[] ps, ss;  
  18.   
  19.  void run(){  
  20.   for(;;){  
  21.    n=sc.nextInt();  
  22.    w=sc.nextInt();  
  23.    h=sc.nextInt();  
  24.    if((n|w|h)==0){  
  25.     break;  
  26.    }  
  27.    ps=new int[n];  
  28.    ss=new int[n];  
  29.    for(int i=0; i<n; i++){  
  30.     ps[i]=sc.nextInt()-1;  
  31.     ss[i]=sc.nextInt();  
  32.    }  
  33.    solve();  
  34.   }  
  35.  }  
  36.   
  37.  void solve(){  
  38.   LinkedList<R> list=new LinkedList<R>();  
  39.   list.add(new R(0, 0, w, h));  
  40.   for(int i=0; i<n; i++){  
  41.    R r=list.remove(ps[i]);  
  42.    debug(i, r.x, r.y, r.w, r.h);  
  43.    int x=r.x, y=r.y;  
  44.    for(int k=0; k<ss[i]; k++){  
  45.     if(y==r.y&&x<r.x+r.w){  
  46.      x++;  
  47.     }else if(x==r.x+r.w&&y<r.y+r.h){  
  48.      y++;  
  49.     }else if(y==r.y+r.h&&x>r.x){  
  50.      x--;  
  51.     }else if(x==r.x&&y>r.y){  
  52.      y--;  
  53.     }else{  
  54.      debug("Error!");  
  55.     }  
  56.     // debug(x,y);  
  57.    }  
  58.    debug(x, y);  
  59.    R r1=null, r2=null;  
  60.    if(x==r.x||x==r.x+r.w){  
  61.     r1=new R(r.x, r.y, r.w, y-r.y);  
  62.     r2=new R(r.x, r.y+r1.h, r.w, r.h-r1.h);  
  63.    }else{  
  64.     r1=new R(r.x, r.y, x-r.x, r.h);  
  65.     r2=new R(r.x+r1.w, r.y, r.w-r1.w, r.h);  
  66.    }  
  67.    debug("r1", r1.x, r1.y, r1.w, r1.h);  
  68.    debug("r2", r2.x, r2.y, r2.w, r2.h);  
  69.    if(r1.w*r1.h<r2.w*r2.h){  
  70.     list.add(r1);  
  71.     list.add(r2);  
  72.    }else{  
  73.     list.add(r2);  
  74.     list.add(r1);  
  75.    }  
  76.   }  
  77.   R[] rs=list.toArray(new R[0]);  
  78.   sort(rs);  
  79.   String ans="";  
  80.   for(R r : rs){  
  81.    ans+=(r.w*r.h)+" ";  
  82.    debug(r.x, r.y, r.w, r.h, r.w*r.h);  
  83.   }  
  84.   println(ans.substring(0, ans.length()-1));  
  85.  }  
  86.   
  87.  class R implements Comparable<R>{  
  88.   int x, y, w, h;  
  89.   
  90.   R(int x, int y, int w, int h){  
  91.    this.x=x;  
  92.    this.y=y;  
  93.    this.w=w;  
  94.    this.h=h;  
  95.   }  
  96.   
  97.   @Override  
  98.   public int compareTo(R r){  
  99.    return w*h-r.w*r.h;  
  100.   }  
  101.  }  
  102.   
  103.  void debug(Object... os){  
  104.   // System.err.println(Arrays.deepToString(os));  
  105.  }  
  106.   
  107.  void print(String s){  
  108.   System.out.print(s);  
  109.  }  
  110.   
  111.  void println(String s){  
  112.   System.out.println(s);  
  113.  }  
  114.   
  115.  public static void main(String[] args){  
  116.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  117.   new Main().run();  
  118.  }  
  119. }  
投稿者 時刻: 0 件のコメント:
ラベル:

Aizu Online Judge 1131 Unit Fraction Partition

■1131 Unit Fraction Partition

自明な+ちょっと工夫した枝刈りでAC．
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 Main{  
  10.   
  11.  Scanner sc=new Scanner(System.in);  
  12.   
  13.  int INF=1<<28;  
  14.  double EPS=1e-9;  
  15.   
  16.  int p0, q0, maxA, maxN;  
  17.  int ans;  
  18.   
  19.  void run(){  
  20.   for(;;){  
  21.    p0=sc.nextInt();  
  22.    q0=sc.nextInt();  
  23.    maxA=sc.nextInt();  
  24.    maxN=sc.nextInt();  
  25.    if((p0|q0|maxA|maxN)==0){  
  26.     break;  
  27.    }  
  28.    solve();  
  29.   }  
  30.  }  
  31.   
  32.  void solve(){  
  33.   int gcd=gcd(p0, q0);  
  34.   p0/=gcd;  
  35.   q0/=gcd;  
  36.   ans=0;  
  37.   dfs(0, 1, 1, 1, 0);  
  38.   // debug(ans);  
  39.   println(""+ans);  
  40.  }  
  41.   
  42.  void dfs(int p, int q, int qNow, int a, int n){  
  43.   if(n>maxN){  
  44.    return;  
  45.   }  
  46.   if(a>maxA){  
  47.    return;  
  48.   }  
  49.   if(p*q0-q*p0>0){  
  50.    return;  
  51.   }  
  52.   {  
  53.    int p2=maxN-n;  
  54.    int q2=qNow;  
  55.    int pp=p*q2+q*p2;  
  56.    int qq=q*q2;  
  57.    if(pp*q0-qq*p0<0){  
  58.     return;  
  59.    }  
  60.   }  
  61.   // debug(p,q,qNow,a,n);  
  62.   if(p==p0&&q==q0){  
  63.    ans++;  
  64.    return;  
  65.   }  
  66.   for(int i=qNow; i*a<=maxA; i++){  
  67.    int p2=p*i+q;  
  68.    int q2=q*i;  
  69.    int gcd=gcd(p2, q2);  
  70.    p2/=gcd;  
  71.    q2/=gcd;  
  72.    dfs(p2, q2, i, i*a, n+1);  
  73.   }  
  74.  }  
  75.   
  76.  int gcd(int m, int n){  
  77.   for(; m!=0;){  
  78.    int t=n%m;  
  79.    n=m;  
  80.    m=t;  
  81.   }  
  82.   return n;  
  83.  }  
  84.   
  85.  void debug(Object... os){  
  86.   System.err.println(Arrays.deepToString(os));  
  87.  }  
  88.   
  89.  void print(String s){  
  90.   System.out.print(s);  
  91.  }  
  92.   
  93.  void println(String s){  
  94.   System.out.println(s);  
  95.  }  
  96.   
  97.  public static void main(String[] args){  
  98.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  99.   new Main().run();  
  100.  }  
  101. }  
投稿者 時刻: 0 件のコメント:
ラベル:

2011年6月20日月曜日

Aizu Online Judge 1156 Twirling Robot

■1156 Twirling Robot

(x座標，y座標，方向ベクトル)を状態としたDijkstra．コストのつけ方が特殊だが，少し注意すれば特に問題無い．
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 Main{  
  10.   
  11.  Scanner sc=new Scanner(System.in);  
  12.   
  13.  int INF=1<<28;  
  14.  double EPS=1e-9;  
  15.   
  16.  int m, n;  
  17.  int[][] a;  
  18.  int[] c;  
  19.   
  20.  void run(){  
  21.   for(;;){  
  22.    m=sc.nextInt();  
  23.    n=sc.nextInt();  
  24.    if((m|n)==0){  
  25.     break;  
  26.    }  
  27.    a=new int[n][m];  
  28.    for(int j=0; j<n; j++){  
  29.     for(int i=0; i<m; i++){  
  30.      a[j][i]=sc.nextInt();  
  31.     }  
  32.    }  
  33.    c=new int[4];  
  34.    for(int i=0; i<4; i++){  
  35.     c[i]=sc.nextInt();  
  36.    }  
  37.    solve();  
  38.   }  
  39.  }  
  40.   
  41.  void solve(){  
  42.   int[][][] d=new int[n][m][4];  
  43.   for(int j=0; j<n; j++){  
  44.    for(int i=0; i<m; i++){  
  45.     fill(d[j][i], INF);  
  46.    }  
  47.   }  
  48.   int[] dx={1, 0, -1, 0};  
  49.   int[] dy={0, 1, 0, -1};  
  50.   PriorityQueue<P> que=new PriorityQueue<P>();  
  51.   que.offer(new P(0, 0, 0));  
  52.   d[0][0][0]=0;  
  53.   for(; !que.isEmpty();){  
  54.    P p=que.poll();  
  55.    if(p.d>d[p.y][p.x][p.v]){  
  56.     continue;  
  57.    }  
  58.    int[] cost=c.clone();  
  59.    if(a[p.y][p.x]!=4){  
  60.     cost[a[p.y][p.x]]=0;  
  61.    }  
  62.    for(int i=0; i<4; i++){  
  63.     P q=new P(p.x, p.y, (p.v+i)%4);  
  64.     q.x+=dx[q.v];  
  65.     q.y+=dy[q.v];  
  66.     if(q.x<0||q.x>=m||q.y<0||q.y>=n){  
  67.      continue;  
  68.     }  
  69.     if(d[q.y][q.x][q.v]>d[p.y][p.x][p.v]+cost[i]){  
  70.      q.d=d[q.y][q.x][q.v]=d[p.y][p.x][p.v]+cost[i];  
  71.      que.offer(q);  
  72.     }  
  73.    }  
  74.   }  
  75.   int ans=INF;  
  76.   for(int i=0; i<4; i++){  
  77.    ans=min(ans, d[n-1][m-1][i]);  
  78.   }  
  79.   println(ans+"");  
  80.  }  
  81.   
  82.  class P implements Comparable<P>{  
  83.   int x, y, v;  
  84.   int d;  
  85.   
  86.   P(int x, int y, int v){  
  87.    this.x=x;  
  88.    this.y=y;  
  89.    this.v=v;  
  90.   }  
  91.   
  92.   @Override  
  93.   public int compareTo(P p){  
  94.    return d-p.d;  
  95.   }  
  96.  }  
  97.   
  98.  void debug(Object... os){  
  99.   System.err.println(Arrays.deepToString(os));  
  100.  }  
  101.   
  102.  void print(String s){  
  103.   System.out.print(s);  
  104.  }  
  105.   
  106.  void println(String s){  
  107.   System.out.println(s);  
  108.  }  
  109.   
  110.  public static void main(String[] args){  
  111.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  112.   new Main().run();  
  113.  }  
  114. }  
投稿者 時刻: 0 件のコメント:
ラベル:

Aizu Online Judge 1136 Polygonal Line Search

■1136 Polygonal Line Search

回転および平行移動を適用したということは，各々の線分ベクトルを0,90,180,270°の何れかの角度回転させたことになる．従って，元の折れ線の内の1つの線分ベクトルと，探す対象の折れ線の内の1つの線分ベクトルを見れば何度回転させたか分かる．あとは，残りの線分ベクトルを回転させ，元の折れ線の線分ベクトルに一致するかを見ていけば良い．
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 Main{  
  10.   
  11.  Scanner sc=new Scanner(System.in);  
  12.   
  13.  int INF=1<<28;  
  14.  double EPS=1e-9;  
  15.   
  16.  int n;  
  17.  int[] m;  
  18.  int[][] xs, ys;  
  19.   
  20.  void run(){  
  21.   for(;;){  
  22.    n=sc.nextInt();  
  23.    if(n==0){  
  24.     break;  
  25.    }  
  26.    m=new int[n+1];  
  27.    xs=new int[n+1][];  
  28.    ys=new int[n+1][];  
  29.    for(int j=0; j<=n; j++){  
  30.     m[j]=sc.nextInt();  
  31.     xs[j]=new int[m[j]];  
  32.     ys[j]=new int[m[j]];  
  33.     for(int i=0; i<m[j]; i++){  
  34.      xs[j][i]=sc.nextInt();  
  35.      ys[j][i]=sc.nextInt();  
  36.     }  
  37.    }  
  38.    solve();  
  39.   }  
  40.  }  
  41.   
  42.  void solve(){  
  43.   for(int i=1; i<=n; i++){  
  44.    if(m[0]==m[i]&&match(m[0], xs[0], ys[0], xs[i], ys[i])){  
  45.     println(i+"");  
  46.    }  
  47.   }  
  48.   println("+++++");  
  49.  }  
  50.   
  51.  boolean match(int m, int[] xs1, int[] ys1, int[] xs2, int[] ys2){  
  52.   int[][][] a={{{1, 0}, {0, 1}}, {{0, -1}, {1, 0}}, {{-1, 0}, {0, -1}},  
  53.     {{0, 1}, {-1, 0}}};  
  54.   
  55.   int k1=-1, k2=-1;  
  56.   for(int j=0; j<4; j++){  
  57.    int vx1=xs1[1]-xs1[0];  
  58.    int vy1=ys1[1]-ys1[0];  
  59.    int vx2=xs2[1]-xs2[0];  
  60.    int vy2=ys2[1]-ys2[0];  
  61.    if(vx1*a[j][0][0]+vy1*a[j][0][1]==vx2  
  62.      &&vx1*a[j][1][0]+vy1*a[j][1][1]==vy2){  
  63.     k1=j;  
  64.    }  
  65.    int vx3=xs2[m-2]-xs2[m-1];  
  66.    int vy3=ys2[m-2]-ys2[m-1];  
  67.    if(vx1*a[j][0][0]+vy1*a[j][0][1]==vx3  
  68.      &&vx1*a[j][1][0]+vy1*a[j][1][1]==vy3){  
  69.     k2=j;  
  70.    }  
  71.   }  
  72.   
  73.   boolean f1=k1!=-1, f2=k2!=-1;  
  74.   for(int i=0; i<m-1; i++){  
  75.    int vx1=xs1[i+1]-xs1[i];  
  76.    int vy1=ys1[i+1]-ys1[i];  
  77.    int vx2=xs2[i+1]-xs2[i];  
  78.    int vy2=ys2[i+1]-ys2[i];  
  79.    int vx3=xs2[m-i-2]-xs2[m-i-1];  
  80.    int vy3=ys2[m-i-2]-ys2[m-i-1];  
  81.    if(k1!=-1){  
  82.     f1&=vx1*a[k1][0][0]+vy1*a[k1][0][1]==vx2  
  83.       &&vx1*a[k1][1][0]+vy1*a[k1][1][1]==vy2;  
  84.    }  
  85.    if(k2!=-1){  
  86.     f2&=vx1*a[k2][0][0]+vy1*a[k2][0][1]==vx3  
  87.       &&vx1*a[k2][1][0]+vy1*a[k2][1][1]==vy3;  
  88.    }  
  89.   }  
  90.   
  91.   return f1||f2;  
  92.  }  
  93.   
  94.  void debug(Object... os){  
  95.   System.err.println(Arrays.deepToString(os));  
  96.  }  
  97.   
  98.  void print(String s){  
  99.   System.out.print(s);  
  100.  }  
  101.   
  102.  void println(String s){  
  103.   System.out.println(s);  
  104.  }  
  105.   
  106.  public static void main(String[] args){  
  107.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  108.   new Main().run();  
  109.  }  
  110. }  
投稿者 時刻: 0 件のコメント:
ラベル:

CodeChef June Cook-off 2011

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

■Correctness of Knight Move

やるだけ．出力をバッファリングしないとTLEします（しました）．
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 Main{  
  10.  Scanner sc=new Scanner(System.in);  
  11.   
  12.  int INF=1<<28;  
  13.  double EPS=1e-9;  
  14.   
  15.  int n;  
  16.  String s;  
  17.   
  18.  void run(){  
  19.   n=sc.nextInt();  
  20.   sc.nextLine();  
  21.   String[] ans={"Yes", "No", "Error"};  
  22.   for(int i=0; i<n; i++){  
  23.    s=sc.nextLine();  
  24.    println(ans[solve()]);  
  25.   }  
  26.   System.out.flush();  
  27.  }  
  28.   
  29.  int solve(){  
  30.   boolean legal=true;  
  31.   if(s.length()!=5){  
  32.    return 2;  
  33.   }  
  34.   legal&='a'<=s.charAt(0)&&s.charAt(0)<='h';  
  35.   legal&='1'<=s.charAt(1)&&s.charAt(1)<='8';  
  36.   legal&=s.charAt(2)=='-';  
  37.   legal&='a'<=s.charAt(3)&&s.charAt(3)<='h';  
  38.   legal&='1'<=s.charAt(4)&&s.charAt(4)<='8';  
  39.   if(!legal){  
  40.    return 2;  
  41.   }  
  42.   int x1=s.charAt(0)-'a';  
  43.   int y1=s.charAt(1)-'1';  
  44.   int x2=s.charAt(3)-'a';  
  45.   int y2=s.charAt(4)-'1';  
  46.   
  47.   int dx=abs(x1-x2);  
  48.   int dy=abs(y1-y2);  
  49.   
  50.   return (dx==1&&dy==2)||(dx==2&&dy==1)?0:1;  
  51.  }  
  52.   
  53.  void println(String s){  
  54.   System.out.println(s);  
  55.  }  
  56.   
  57.  void print(String s){  
  58.   System.out.print(s);  
  59.  }  
  60.   
  61.  void debug(Object... os){  
  62.   System.err.println(Arrays.deepToString(os));  
  63.  }  
  64.   
  65.  public static void main(String[] args){  
  66.   System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  67.   new Main().run();  
  68.  }  
  69. }  

■Super-plane

Dunnoの挙動は分岐無しなので，適当なループで解けます．コンテスト中は勘違いしていて，BFSをしようとしてTLE食らいまくっていました．さらに，Javaの入出力がバッファリングしてなかったため，少し調整しないと通りませんでした．
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 Main{  
  10.  // Scanner sc=new Scanner(System.in);  
  11.   
  12.  int INF=1<<28;  
  13.  double EPS=1e-9;  
  14.   
  15.  int t, n;  
  16.  int cs, ts, cg, tg;  
  17.  E[] es;  
  18.   
  19.  void run() throws Exception{  
  20.   BufferedReader br=new BufferedReader(new InputStreamReader(System.in));  
  21.   t=Integer.parseInt(br.readLine());  
  22.   for(; t>0; t--){  
  23.    n=Integer.parseInt(br.readLine());  
  24.    es=new E[n];  
  25.    for(int i=0; i<n; i++){  
  26.     String[] ss=br.readLine().split(" ");  
  27.     int c1=Integer.parseInt(ss[0])-1;  
  28.     int t1=Integer.parseInt(ss[1]);  
  29.     int c2=Integer.parseInt(ss[2])-1;  
  30.     int t2=Integer.parseInt(ss[3]);  
  31.     es[i]=new E(c1, t1, c2, t2);  
  32.    }  
  33.    sort(es);  
  34.    String[] ss=br.readLine().split(" ");  
  35.    cs=Integer.parseInt(ss[0])-1;  
  36.    ts=Integer.parseInt(ss[1]);  
  37.    cg=Integer.parseInt(ss[2])-1;  
  38.    tg=Integer.parseInt(ss[3]);  
  39.    solve();  
  40.   }  
  41.   System.out.flush();  
  42.  }  
  43.   
  44.  void solve(){  
  45.   P p=new P(cs, ts);  
  46.   boolean[] visited=new boolean[n];  
  47.   int ans=0;  
  48.   boolean ok=true;  
  49.   E key=new E(p.c, p.t, 0, 0);  
  50.   for(;; ans++){  
  51.    if(p.c==cg&&p.t<=tg){  
  52.     break;  
  53.    }  
  54.    key.c1=p.c;  
  55.    key.t1=p.t;  
  56.    int k=binarySearch(es, key);  
  57.    if(k<0){  
  58.     k=-1-k;  
  59.    }  
  60.    if(k==n){  
  61.     ok=false;  
  62.     break;  
  63.    }  
  64.    if(es[k].c1!=p.c){  
  65.     ok=false;  
  66.     break;  
  67.    }  
  68.    if(visited[k]){  
  69.     ok=false;  
  70.     break;  
  71.    }  
  72.    visited[k]=true;  
  73.    p.c=es[k].c2;  
  74.    p.t=es[k].t2;  
  75.   }  
  76.   if(ok){  
  77.    println("Yes "+ans);  
  78.   }else{  
  79.    println("No");  
  80.   }  
  81.  }  
  82.   
  83.  class E implements Comparable<E>{  
  84.   int c1, t1, c2, t2;  
  85.   
  86.   E(int c1, int t1, int c2, int t2){  
  87.    this.c1=c1;  
  88.    this.t1=t1;  
  89.    this.c2=c2;  
  90.    this.t2=t2;  
  91.   }  
  92.   
  93.   @Override  
  94.   public int compareTo(E e){  
  95.    if(c1!=e.c1){  
  96.     return c1-e.c1;  
  97.    }else{  
  98.     return t1-e.t1;  
  99.    }  
  100.   }  
  101.  }  
  102.   
  103.  class P implements Comparable<P>{  
  104.   int c, t;  
  105.   
  106.   P(int c, int t){  
  107.    this.c=c;  
  108.    this.t=t;  
  109.   }  
  110.   
  111.   @Override  
  112.   public int compareTo(P p){  
  113.    if(c!=p.c){  
  114.     return c-p.c;  
  115.    }else{  
  116.     return t-p.t;  
  117.    }  
  118.   }  
  119.  }  
  120.   
  121.  void println(String s){  
  122.   System.out.println(s);  
  123.  }  
  124.   
  125.  void print(String s){  
  126.   System.out.print(s);  
  127.  }  
  128.   
  129.  void debug(Object... os){  
  130.   System.err.println(Arrays.deepToString(os));  
  131.  }  
  132.   
  133.  public static void main(String[] args){  
  134.   System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  135.   try{  
  136.    new Main().run();  
  137.   }catch(Exception e){  
  138.    e.printStackTrace();  
  139.   }  
  140.  }  
  141. }  

■Result

--o--

またもやこれは酷い…．CodeChefとは相性が悪いようです．C++に乗り換えるのも手だと思われます．
投稿者 時刻: 0 件のコメント:
ラベル:

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に変更するためのポップの回数の最小値を返せ．
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 TripleStrings {  
  10.  // long INF=1L<<48;  
  11.  int INF=1<<28;  
  12.  double EPS=1e-9;  
  13.   
  14.  public int getMinimumOperations(String init, String goal) {  
  15.   int n=init.length();  
  16.   int max=0;  
  17.   for(int j=1;j<=n;j++){  
  18.    boolean f=true;  
  19.    for(int i=0;i<j;i++){  
  20.     f&=init.charAt(n-j+i)==goal.charAt(i);  
  21.    }  
  22.    if(f){  
  23.     max=max(max,j);  
  24.    }  
  25.   }  
  26.   return (n-max)*2;  
  27.  }  
  28.   
  29.  void debug(Object...os){  
  30.   System.err.println(Arrays.deepToString(os));  
  31.  }  
  32.   
  33.  void print(String s){  
  34.   System.out.print(s);  
  35.  }  
  36.   
  37.  void println(String s){  
  38.   System.out.println(s);  
  39.  }  
  40. }  

■Challenge Phase

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

■Result

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

■Rating

1414 -> 1431
残念…．
投稿者 時刻: 0 件のコメント:
ラベル:

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通りなので，全部試せば良い．
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. // AC  
  10. public class Main{  
  11.   
  12.  Scanner sc=new Scanner(System.in);  
  13.   
  14.  String s;  
  15.  int[] map;  
  16.   
  17.  void run(){  
  18.   for(;;){  
  19.    s=sc.next();  
  20.    if(s.equals(".")){  
  21.     break;  
  22.    }  
  23.    solve();  
  24.   }  
  25.  }  
  26.   
  27.  void solve(){  
  28.   map=new int[256];  
  29.   map['0']=0;  
  30.   map['1']=1;  
  31.   map['2']=2;  
  32.   int ans=0;  
  33.   for(int p=0; p<3; p++){  
  34.    for(int q=0; q<3; q++){  
  35.     for(int r=0; r<3; r++){  
  36.      map['P']=p;  
  37.      map['Q']=q;  
  38.      map['R']=r;  
  39.      Result res=f(0);  
  40.      if(res.value==2){  
  41.       ans++;  
  42.      }  
  43.     }  
  44.    }  
  45.   }  
  46.   println(ans+"");  
  47.  }  
  48.   
  49.  Result f(int p){  
  50.   // debug("f",p);  
  51.   if(Character.isDigit(s.charAt(p))||Character.isUpperCase(s.charAt(p))){  
  52.    return new Result(p+1, map[s.charAt(p)]);  
  53.   }else if(s.charAt(p)=='-'){  
  54.    Result r=f(p+1);  
  55.    r.value=2-r.value;  
  56.    return r;  
  57.   }else{  
  58.    Result r=f(p+1);  
  59.    Result r2=f(r.p+1); // skip '*' or '+'  
  60.    if(s.charAt(r.p)=='*'){  
  61.     r.value=min(r.value, r2.value);  
  62.    }else{ // '+'  
  63.     r.value=max(r.value, r2.value);  
  64.    }  
  65.    r.p=r2.p+1;  
  66.    return r;  
  67.   }  
  68.  }  
  69.   
  70.  class Result{  
  71.   int p, value;  
  72.   
  73.   Result(int p, int value){  
  74.    this.p=p;  
  75.    this.value=value;  
  76.   }  
  77.  }  
  78.   
  79.  void debug(Object... os){  
  80.   System.err.println(Arrays.deepToString(os));  
  81.  }  
  82.   
  83.  void print(String s){  
  84.   System.out.print(s);  
  85.  }  
  86.   
  87.  void println(String s){  
  88.   System.out.println(s);  
  89.  }  
  90.   
  91.  public static void main(String[] args){  
  92.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  93.   new Main().run();  
  94.  }  
  95. }  
投稿者 時刻: 0 件のコメント:
ラベル:

Aizu Online Judge 1244 Molecular Formula

■1244 Molecular Formula

構文解析ゲー．
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. // AC  
  10. public class Main{  
  11.   
  12.  Scanner sc=new Scanner(System.in);  
  13.   
  14.  HashMap<String, Integer> map;  
  15.  String s;  
  16.  boolean unknown;  
  17.   
  18.  void run(){  
  19.   map=new HashMap<String, Integer>();  
  20.   for(;;){  
  21.    String s=sc.next();  
  22.    if(s.equals("END_OF_FIRST_PART")){  
  23.     break;  
  24.    }  
  25.    int n=sc.nextInt();  
  26.    map.put(s, n);  
  27.   }  
  28.   for(;;){  
  29.    s=sc.next();  
  30.    if(s.equals("0")){  
  31.     break;  
  32.    }  
  33.    s+='\0';  
  34.    unknown=false;  
  35.    Result r=molecule(0);  
  36.    println(unknown?"UNKNOWN":r.value+"");  
  37.    debug(r.p, r.value);  
  38.   }  
  39.  }  
  40.   
  41.  Result molecule(int p){  
  42.   debug("molecule", p);  
  43.   Result r=new Result(p, 0);  
  44.   for(;;){  
  45.    if(s.charAt(r.p)=='\0'||s.charAt(r.p)==')'){  
  46.     // end of molecule  
  47.     return r;  
  48.    }else if(s.charAt(r.p)=='('){  
  49.     Result r1=molecule(r.p+1);  
  50.     Result r2=number(r1.p+1); // skip '('  
  51.     r.value+=r1.value*r2.value;  
  52.     r.p=r2.p;  
  53.    }else{  
  54.     Result r1=atom(r.p);  
  55.     Result r2=number(r1.p);  
  56.     r.value+=r1.value*r2.value;  
  57.     r.p=r2.p;  
  58.    }  
  59.   }  
  60.  }  
  61.   
  62.  Result atom(int p){  
  63.   debug("atom", p);  
  64.   String atom="";  
  65.   if(Character.isUpperCase(s.charAt(p))){  
  66.    atom+=s.charAt(p);  
  67.    p++;  
  68.    if(Character.isLowerCase(s.charAt(p))){  
  69.     atom+=s.charAt(p);  
  70.     p++;  
  71.    }  
  72.   }  
  73.   debug(atom);  
  74.   if(map.containsKey(atom)){  
  75.    return new Result(p, map.get(atom));  
  76.   }else{  
  77.    unknown=true;  
  78.    return new Result(p, 0);  
  79.   }  
  80.  }  
  81.   
  82.  Result number(int p){  
  83.   debug("number", p);  
  84.   int value=0;  
  85.   if(Character.isDigit(s.charAt(p))){  
  86.    value=s.charAt(p)-'0';  
  87.    p++;  
  88.    if(Character.isDigit(s.charAt(p))){  
  89.     value=value*10+s.charAt(p)-'0';  
  90.     p++;  
  91.    }  
  92.   }else{  
  93.    return new Result(p, 1);  
  94.   }  
  95.   return new Result(p, value);  
  96.  }  
  97.   
  98.  class Result{  
  99.   int p, value;  
  100.   
  101.   Result(int p, int value){  
  102.    this.p=p;  
  103.    this.value=value;  
  104.   }  
  105.  }  
  106.   
  107.  void debug(Object... os){  
  108.   // System.err.println(Arrays.deepToString(os));  
  109.  }  
  110.   
  111.  void print(String s){  
  112.   System.out.print(s);  
  113.  }  
  114.   
  115.  void println(String s){  
  116.   System.out.println(s);  
  117.  }  
  118.   
  119.  public static void main(String[] args){  
  120.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  121.   new Main().run();  
  122.  }  
  123. }  
投稿者 時刻: 0 件のコメント:
ラベル:

Aizu Online Judge 1012 Operations with Finite Sets

■1012 Operations with Finite Sets

構文解析ゲー．
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. // AC  
  10. public class Main{  
  11.   
  12.  Scanner sc=new Scanner(System.in);  
  13.   
  14.  int INF=1<<28;  
  15.  double EPS=1e-9;  
  16.  TreeSet<Integer>[] sets;  
  17.  String exp;  
  18.  TreeSet<Integer> U;  
  19.   
  20.  @SuppressWarnings("unchecked")  
  21.  void run(){  
  22.   for(; sc.hasNext();){  
  23.    sets=new TreeSet[256];  
  24.    for(char c='A'; c<='E'; c++){  
  25.     sets[c]=new TreeSet<Integer>();  
  26.    }  
  27.    U=new TreeSet<Integer>();  
  28.    for(;;){  
  29.     char c=sc.next().charAt(0);  
  30.     int n=sc.nextInt();  
  31.     if(c=='R'&&n==0){  
  32.      break;  
  33.     }  
  34.     for(int i=0; i<n; i++){  
  35.      int e=sc.nextInt();  
  36.      sets[c].add(e);  
  37.      U.add(e);  
  38.     }  
  39.    }  
  40.    exp=sc.next();  
  41.    solve();  
  42.   }  
  43.  }  
  44.   
  45.  void solve(){  
  46.   exp+='\0';  
  47.   Result r=e(0);  
  48.   debug(r.set.toArray());  
  49.   if(r.set.size()==0){  
  50.    println("NULL");  
  51.   }else{  
  52.    for(Iterator<Integer> it=r.set.iterator(); it.hasNext();){  
  53.     print(it.next()+(it.hasNext()?" ":"\n"));  
  54.    }  
  55.   }  
  56.  }  
  57.   
  58.  Result e(int p){  
  59.   debug("e", p);  
  60.   Result r=f(p);  
  61.   debug(r.set.toArray(), r.p);  
  62.   for(;;){  
  63.    if(op(exp.charAt(r.p))){  
  64.     Result r2=f(r.p+1);  
  65.     switch(exp.charAt(r.p)){  
  66.     case 'u': // or  
  67.      r.set.addAll(r2.set);  
  68.      break;  
  69.     case 'i': // and  
  70.      for(int e : U){  
  71.       if(r.set.contains(e)&&r2.set.contains(e)){}else{  
  72.        r.set.remove(e);  
  73.       }  
  74.      }  
  75.      break;  
  76.     case 'd': // diff  
  77.      r.set.removeAll(r2.set);  
  78.      break;  
  79.     case 's': // sym  
  80.      for(int e : U){  
  81.       if(r.set.contains(e)&&r2.set.contains(e)){  
  82.        r.set.remove(e);  
  83.       }else if(r2.set.contains(e)){  
  84.        r.set.add(e);  
  85.       }  
  86.      }  
  87.      break;  
  88.     }  
  89.     r.p=r2.p;  
  90.    }else{  
  91.     break;  
  92.    }  
  93.   }  
  94.   return r;  
  95.  }  
  96.   
  97.  boolean op(char c){  
  98.   return c=='u'||c=='i'||c=='d'||c=='s';  
  99.  }  
  100.   
  101.  Result f(int p){  
  102.   debug("f", p);  
  103.   if(exp.charAt(p)=='c'){  
  104.    Result r=f(p+1);  
  105.    TreeSet<Integer> c=new TreeSet<Integer>();  
  106.    for(int e : U){  
  107.     if(!r.set.contains(e)){  
  108.      c.add(e);  
  109.     }  
  110.    }  
  111.    r.set.clear();  
  112.    r.set.addAll(c);  
  113.    return r;  
  114.   }else{  
  115.    return t(p);  
  116.   }  
  117.  }  
  118.   
  119.  Result t(int p){  
  120.   debug("t", p);  
  121.   if(exp.charAt(p)=='('){  
  122.    Result r=e(p+1);  
  123.    r.p++; // skip ')'  
  124.    return r;  
  125.   }else{  
  126.    Result r=new Result(p+1);  
  127.    r.set.addAll(sets[exp.charAt(p)]);  
  128.    return r;  
  129.   }  
  130.  }  
  131.   
  132.  class Result{  
  133.   int p;  
  134.   TreeSet<Integer> set;  
  135.   
  136.   Result(int p){  
  137.    this.p=p;  
  138.    set=new TreeSet<Integer>();  
  139.   }  
  140.  }  
  141.   
  142.  void debug(Object... os){  
  143.   // System.err.println(Arrays.deepToString(os));  
  144.  }  
  145.   
  146.  void print(String s){  
  147.   System.out.print(s);  
  148.  }  
  149.   
  150.  void println(String s){  
  151.   System.out.println(s);  
  152.  }  
  153.   
  154.  public static void main(String[] args){  
  155.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  156.   new Main().run();  
  157.  }  
  158. }  
投稿者 時刻: 0 件のコメント:
ラベル:

Aizu Online Judge 1162 Discrete Speed

■1162 Discrete Speed

拡張ダイクストラ．
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. // AC  
  10. public class Main{  
  11.   
  12.  Scanner sc=new Scanner(System.in);  
  13.   
  14.  int INF=1<<28;  
  15.  double EPS=1e-9;  
  16.   
  17.  int n, m;  
  18.  int s, g;  
  19.  LinkedList<E>[] es;  
  20.   
  21.  @SuppressWarnings("unchecked")  
  22.  void run(){  
  23.   for(;;){  
  24.    n=sc.nextInt();  
  25.    m=sc.nextInt();  
  26.    if((n|m)==0){  
  27.     break;  
  28.    }  
  29.    es=new LinkedList[n];  
  30.    for(int i=0; i<n; i++){  
  31.     es[i]=new LinkedList<E>();  
  32.    }  
  33.    s=sc.nextInt()-1;  
  34.    g=sc.nextInt()-1;  
  35.    for(int i=0; i<m; i++){  
  36.     int x=sc.nextInt()-1;  
  37.     int y=sc.nextInt()-1;  
  38.     int d=sc.nextInt();  
  39.     int c=sc.nextInt();  
  40.     es[x].add(new E(y, d, c));  
  41.     es[y].add(new E(x, d, c));  
  42.    }  
  43.    solve();  
  44.   }  
  45.  }  
  46.   
  47.  void solve(){  
  48.   // [前][今][前から今の速度]  
  49.   double[][][] d=new double[n][n][40];  
  50.   PriorityQueue<P> que=new PriorityQueue<P>();  
  51.   for(int j=0; j<n; j++){  
  52.    for(int i=0; i<n; i++){  
  53.     fill(d[j][i], INF);  
  54.    }  
  55.   }  
  56.   d[s][s][1]=0;  
  57.   que.offer(new P(s, s, 0, 0));  
  58.   for(; !que.isEmpty();){  
  59.    P p=que.poll();  
  60.    if(d[p.q][p.p][p.v]+EPS<p.d){  
  61.     continue;  
  62.    }  
  63.    for(E e : es[p.p]){  
  64.     if(p.q==e.to){  
  65.      continue;  
  66.     }  
  67.     for(int i=-1; i<=1; i++){  
  68.      if(p.v+i<=0||p.v+i>e.c){  
  69.       continue;  
  70.      }  
  71.      if(d[p.p][e.to][p.v+i]>p.d+(double)e.d/(p.v+i)+EPS){  
  72.       d[p.p][e.to][p.v+i]=p.d+(double)e.d/(p.v+i);  
  73.       que.offer(new P(p.p, e.to, p.v+i, d[p.p][e.to][p.v+i]));  
  74.      }  
  75.     }  
  76.    }  
  77.   }  
  78.   double min=INF;  
  79.   for(int i=0; i<n; i++){  
  80.    min=min(min, d[i][g][1]);  
  81.   }  
  82.   println(""+(min<INF/2?min:"unreachable"));  
  83.  }  
  84.   
  85.  class E{  
  86.   int to, d, c;  
  87.   
  88.   E(int to, int d, int c){  
  89.    this.to=to;  
  90.    this.d=d;  
  91.    this.c=c;  
  92.   }  
  93.  }  
  94.   
  95.  class P implements Comparable<P>{  
  96.   int q, p, v;  
  97.   double d;  
  98.   
  99.   P(int q, int p, int v, double d){  
  100.    this.q=q;  
  101.    this.p=p;  
  102.    this.v=v;  
  103.    this.d=d;  
  104.   }  
  105.   
  106.   @Override  
  107.   public int compareTo(P p){  
  108.    if(d+EPS<p.d){  
  109.     return -1;  
  110.    }else if(d>p.d+EPS){  
  111.     return 1;  
  112.    }else{  
  113.     return 0;  
  114.    }  
  115.   }  
  116.   
  117.  }  
  118.   
  119.  void debug(Object... os){  
  120.   System.err.println(Arrays.deepToString(os));  
  121.  }  
  122.   
  123.  void print(String s){  
  124.   System.out.print(s);  
  125.  }  
  126.   
  127.  void println(String s){  
  128.   System.out.println(s);  
  129.  }  
  130.   
  131.  public static void main(String[] args){  
  132.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  133.   new Main().run();  
  134.  }  
  135. }  
投稿者 時刻: 0 件のコメント:
ラベル:

Aizu Online Judge 1161 Verbal Arithmetic

■1161 Verbal Arithmetic

非常に汚い探索による解法．
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. // AC  
  10. public class Main{  
  11.   
  12.  Scanner sc=new Scanner(System.in);  
  13.   
  14.  int INF=1<<28;  
  15.  double EPS=1e-9;  
  16.   
  17.  int n;  
  18.  String[] ss;  
  19.   
  20.  void run(){  
  21.   for(;;){  
  22.    n=sc.nextInt();  
  23.    if(n==0){  
  24.     break;  
  25.    }  
  26.    ss=new String[n];  
  27.    for(int i=0; i<n; i++){  
  28.     ss[i]=sc.next();  
  29.    }  
  30.    solve();  
  31.   }  
  32.  }  
  33.   
  34.  int size;  
  35.  int[] cs;  
  36.  int[] map;  
  37.  boolean[] used;  
  38.  int ans;  
  39.   
  40.  void solve(){  
  41.   int[] a=new int[256];  
  42.   fill(a, -1);  
  43.   size=0;  
  44.   for(String s : ss){  
  45.    for(int i=0; i<s.length(); i++){  
  46.     if(a[s.charAt(i)]==-1){  
  47.      size++;  
  48.      a[s.charAt(i)]=INF;  
  49.     }  
  50.     a[s.charAt(i)]=min(a[s.charAt(i)], s.length()-1-i);  
  51.    }  
  52.   }  
  53.   cs=new int[size];  
  54.   for(int k=0, i=0; i<256; i++){  
  55.    if(a[i]>=0){  
  56.     cs[k++]=i+1000*a[i];  
  57.    }  
  58.   }  
  59.   sort(cs);  
  60.   
  61.   used=new boolean[10];  
  62.   map=new int[256];  
  63.   fill(map, -1);  
  64.   ans=0;  
  65.   dfs(0);  
  66.   println(""+ans);  
  67.  }  
  68.   
  69.  void dfs(int k){  
  70.   if(k==size){  
  71.    if(ok(8)){  
  72.     ans++;  
  73.    }  
  74.    return;  
  75.   }  
  76.   for(int i=0; i<10; i++){  
  77.    if(!used[i]){  
  78.     used[i]=true;  
  79.     map[cs[k]%1000]=i;  
  80.     if(ok(cs[k]/1000)){  
  81.      dfs(k+1);  
  82.     }  
  83.     map[cs[k]%1000]=-1;  
  84.     used[i]=false;  
  85.    }  
  86.   }  
  87.  }  
  88.   
  89.  boolean ok(int d){  
  90.   int sum=0;  
  91.   for(int j=0; j<n; j++){  
  92.    if(map[ss[j].charAt(0)]==0&&ss[j].length()>1){  
  93.     return false;  
  94.    }  
  95.    int num=0;  
  96.    for(int i=max(0, d-ss[j].length()); i<d; i++){  
  97.     num=num*10+map[ss[j].charAt(ss[j].length()-d+i)];  
  98.    }  
  99.    if(j==n-1){  
  100.     sum-=num;  
  101.    }else{  
  102.     sum+=num;  
  103.    }  
  104.   }  
  105.   int mod=1;  
  106.   for(int i=0; i<d; i++){  
  107.    mod*=10;  
  108.   }  
  109.   return sum%mod==0;  
  110.  }  
  111.   
  112.  void debug(Object... os){  
  113.   System.err.println(Arrays.deepToString(os));  
  114.  }  
  115.   
  116.  void print(String s){  
  117.   System.out.print(s);  
  118.  }  
  119.   
  120.  void println(String s){  
  121.   System.out.println(s);  
  122.  }  
  123.   
  124.  public static void main(String[] args){  
  125.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  126.   new Main().run();  
  127.  }  
  128. }  
投稿者 時刻: 0 件のコメント:
ラベル:

Aizu Online Judge 1133 Water Tank

■1133 Water Tank

実装ゲー．
view plainprint?
  1. import java.util.*;  
  2. import java.lang.*;  
  3. import java.math.*;  
  4. import java.io.*;  
  5.   
  6. import javax.swing.*;  
  7. import java.awt.*;  
  8.   
  9. import static java.lang.Math.*;  
  10. import static java.util.Arrays.*;  
  11.   
  12. // AC  
  13. public class Main{  
  14.   
  15.  Scanner sc=new Scanner(System.in);  
  16.   
  17.  int INF=1<<28;  
  18.  double EPS=1e-6;  
  19.   
  20.  int d;  
  21.  int n;  
  22.  int[] x, h;  
  23.  int m;  
  24.  int[] f, dv;  
  25.  int l;  
  26.  int[] p, t;  
  27.   
  28.  void run(){  
  29.   d=sc.nextInt();  
  30.   for(int k=0; k<d; k++){  
  31.    n=sc.nextInt()+1;  
  32.    x=new int[n+1];  
  33.    h=new int[n+1];  
  34.    x[0]=0;  
  35.    x[n]=100;  
  36.    h[0]=h[n]=50;  
  37.    for(int i=1; i<n; i++){  
  38.     x[i]=sc.nextInt();  
  39.     h[i]=sc.nextInt();  
  40.    }  
  41.    m=sc.nextInt();  
  42.    f=new int[m];  
  43.    dv=new int[m];  
  44.    for(int i=0; i<m; i++){  
  45.     f[i]=sc.nextInt();  
  46.     dv[i]=sc.nextInt();  
  47.    }  
  48.    l=sc.nextInt();  
  49.    p=new int[l];  
  50.    t=new int[l];  
  51.    for(int i=0; i<l; i++){  
  52.     p[i]=sc.nextInt();  
  53.     t[i]=sc.nextInt();  
  54.    }  
  55.    solve();  
  56.   }  
  57.  }  
  58.   
  59.  double[] y, a;  
  60.  double time;  
  61.   
  62.  void solve(){  
  63.   y=new double[n];  
  64.   a=new double[n];  
  65.   for(int j=0; j<m; j++){  
  66.    for(int i=0; i<n; i++){  
  67.     if(x[i]<f[j]&&f[j]<x[i+1]){  
  68.      a[i]+=dv[j]/30.0;  
  69.     }  
  70.    }  
  71.   }  
  72.   // Visualizer v=new Visualizer();  
  73.   
  74.   double[] ans=new double[l];  
  75.   fill(ans, -1);  
  76.   
  77.   for(time=0;;){  
  78.    double min=INF;  
  79.    for(int i=0; i<n; i++){  
  80.     if(a[i]>EPS){  
  81.      if(y[i]+EPS<h[i]){  
  82.       min=min(min, (h[i]-y[i])*(x[i+1]-x[i])/a[i]);  
  83.      }  
  84.      if(y[i]+EPS<h[i+1]){  
  85.       min=min(min, (h[i+1]-y[i])*(x[i+1]-x[i])/a[i]);  
  86.      }  
  87.     }  
  88.    }  
  89.    if(min==INF){  
  90.     for(;;);  
  91.    }  
  92.    for(int j=0; j<l; j++){  
  93.     if(time<t[j]+EPS&&t[j]+EPS<time+min){  
  94.      for(int i=0; i<n; i++){  
  95.       if(x[i]<p[j]&&p[j]<x[i+1]){  
  96.        ans[j]=min(y[i]+(t[j]-time)*a[i]/(x[i+1]-x[i]), 50);  
  97.       }  
  98.      }  
  99.     }  
  100.    }  
  101.    boolean all50=true;  
  102.    time+=min;  
  103.    for(int i=0; i<n; i++){  
  104.     y[i]+=min*a[i]/(x[i+1]-x[i]);  
  105.     all50&=abs(y[i]-50)<EPS;  
  106.    }  
  107.    // v.repaint();  
  108.    // sleep(1000);  
  109.   
  110.    if(all50){  
  111.     break;  
  112.    }  
  113.    double[] a2=new double[n];  
  114.   
  115.    for(int j=0; j<n; j++){  
  116.     boolean[] bottom=new boolean[n];  
  117.     int left, right;  
  118.     for(left=j; left>=0&&y[left]+EPS>h[left]; left--);  
  119.     for(right=j; right<n&&y[right]+EPS>h[right+1]; right++);  
  120.   
  121.     if(y[left]+EPS<y[j]){  
  122.      for(int i=left; i<n&&abs(y[i]-y[left])<EPS; i++){  
  123.       bottom[i]=true;  
  124.      }  
  125.     }  
  126.     if(y[right]+EPS<y[j]){  
  127.      for(int i=right; i>=0&&abs(y[i]-y[right])<EPS; i--){  
  128.       bottom[i]=true;  
  129.      }  
  130.     }  
  131.     if(abs(y[left]-y[j])<EPS&&abs(y[right]-y[j])<EPS){  
  132.      for(int i=left; i<=right; i++){  
  133.       bottom[i]=true;  
  134.      }  
  135.     }  
  136.     int sum=0;  
  137.     for(int i=0; i<n; i++){  
  138.      if(bottom[i]){  
  139.       sum+=x[i+1]-x[i];  
  140.      }  
  141.     }  
  142.     for(int i=0; i<n; i++){  
  143.      if(bottom[i]){  
  144.       a2[i]+=a[j]/sum*(x[i+1]-x[i]);  
  145.      }  
  146.     }  
  147.    }  
  148.    a=a2.clone();  
  149.   }  
  150.   for(int i=0; i<l; i++){  
  151.    println(ans[i]+EPS<0?"50.0":ans[i]+"");  
  152.   }  
  153.  }  
  154.   
  155.  void sleep(long millis){  
  156.   try{  
  157.    Thread.sleep(millis);  
  158.   }catch(InterruptedException e){  
  159.    e.printStackTrace();  
  160.   }  
  161.  }  
  162.   
  163.  void debug(Object... os){  
  164.   // System.err.println(Arrays.deepToString(os));  
  165.  }  
  166.   
  167.  void print(String s){  
  168.   System.out.print(s);  
  169.  }  
  170.   
  171.  void println(String s){  
  172.   System.out.println(s);  
  173.  }  
  174.   
  175.  public static void main(String[] args){  
  176.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  177.   new Main().run();  
  178.  }  
  179.   
  180.  public class Visualizer extends JFrame{  
  181.   Visualizer(){  
  182.    setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);  
  183.    setVisible(true);  
  184.    getContentPane().add(new MainPanel(), BorderLayout.CENTER);  
  185.    pack();  
  186.   }  
  187.   
  188.   class MainPanel extends JPanel{  
  189.    MainPanel(){  
  190.     setPreferredSize(new Dimension(512, 512));  
  191.    }  
  192.   
  193.    public void paintComponent(Graphics g){  
  194.     int width=getWidth();  
  195.     int height=getHeight();  
  196.     for(int i=0; i<n; i++){  
  197.      g.setColor(Color.BLUE);  
  198.      g.fillRect(x[i]*4, height-(int)(y[i]*4), (x[i+1]-x[i])*4,  
  199.        (int)(y[i]*4));  
  200.      g.drawString(String.format("%.4f", a[i]), x[i]*4, height/2);  
  201.     }  
  202.   
  203.     for(int i=0; i<=n; i++){  
  204.      g.setColor(Color.RED);  
  205.      g.drawLine(x[i]*4, height-h[i]*4, x[i]*4, height);  
  206.     }  
  207.   
  208.     g.setColor(Color.BLACK);  
  209.     g.drawString(""+time, 100, 100);  
  210.    }  
  211.   }  
  212.  }  
  213. }  
投稿者 時刻: 0 件のコメント:
ラベル:

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さんが画像でアップしていましたが，フラクタルな構造をしていました．思い付かなかった．
投稿者 時刻: 0 件のコメント:
ラベル:

UAPC 2011

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

GCJ疲れが影響して，惨敗しました．

■A. It's our delight!!

やるだけ．

■K. Rearranging Seats

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

■Result

2AC 74th
駄目駄目でした．
投稿者 時刻: 0 件のコメント:
ラベル:

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. }  

■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)になり間に合う．
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. }  
■Result 38pts. 756th 念願のTシャツゲットです．もう少し頑張れば，Round3に進めたかもしれないですが，ここ最近で最高レベルに集中出来たので良かったと思います．
投稿者 時刻: 0 件のコメント:
ラベル:

TopCoder SRM 508

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

■DivideAndShift(Easy)

答えをf(n,m)として，再帰的に解きました．
素因数分解をして，素数のべき乗ごとに再帰するので， 制限時間には余裕で間に合います．
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 DivideAndShift {  
  10.  int INF=1<<28;  
  11.  double EPS=1e-9;  
  12.   
  13.  int rec(int n, int m){  
  14.   if(m==0){  
  15.    return 0;  
  16.   }  
  17.   HashMap<Integer,Integer> map=primeFactor(n);  
  18.   int res=min(m,n-m);  
  19.   for(int p:map.keySet()){  
  20.    if(p==1){  
  21.     continue;  
  22.    }  
  23.    res=min(res,rec(n/p,m%(n/p))+1);  
  24.   }  
  25.   return res;  
  26.  }  
  27.   
  28.  public int getLeast(int n, int m) {  
  29.   return rec(n,m-1);  
  30.  }  
  31.    
  32.  HashMap<Integer, Integer> primeFactor(int n){  
  33.   HashMap<Integer, Integer> map=new HashMap<Integer, Integer>();  
  34.   for(int i=2; i*i<=n; i++){  
  35.    int c=0;  
  36.    for(; n%i==0; n/=i)  
  37.     c++;  
  38.    if(c>0)  
  39.     map.put(i, c);  
  40.   }  
  41.   if(n!=1)  
  42.    map.put(n, 1);  
  43.   return map;  
  44.  }  
  45.   
  46.  void debug(Object...os){  
  47.   System.err.println(Arrays.deepToString(os));  
  48.  }  
  49.   
  50.  void print(String s){  
  51.   System.out.print(s);  
  52.  }  
  53.   
  54.  void println(String s){  
  55.   System.out.println(s);  
  56.  }  
  57. }  

■Challenge Phase

撃墜無し．

■Result

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

■Rating

1365 -> 1414
微増．目標の1500にはいつ到達できるのか…．
投稿者 時刻: 0 件のコメント:
ラベル:
登録: 投稿 (Atom)