2011年3月31日木曜日

今月の〇〇(2011年3月)

■Aizu Online Judge

Solved:235/43th
Rating:151.76/67th
簡単な問題ばかり解いていたので,Ratingの順位がやや低めです.ということで来月の目標はRating200にしました.

■TopCoder/Codeforces

ほとんど参加できていません.そのためレーティングも代わり映えしていません.そのため来月は,レーティングの昇降は兎も角として,出来るだけ参加することを重視しようと思います.

■専門書

「計算理論の基礎」を読み進めています.5章辺りを読んでいますが,練習問題に全く手を付けていないため,そちらにも着手する必要がありそうです.また,「コンピュータの数学」は今の自分なら十分読めると判断したため,そろそろ真面目に読もうかと考えている次第です.

2011年3月25日金曜日

Aizu Online Judge 0125 Day Count

■0125 Day Count

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

public class Main{

 Scanner sc=new Scanner(System.in);;

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

 void run(){
  for(;;){
   int y1=sc.nextInt();
   int m1=sc.nextInt();
   int d1=sc.nextInt();
   int y2=sc.nextInt();
   int m2=sc.nextInt();
   int d2=sc.nextInt();
   if(y1<0||m1<0||d1<0||y2<0||m2<0||d2<0){
    break;
   }
   int a=day(y1, m1, d1);
   int b=day(y2, m2, d2);
   println((b-a)+"");
  }
 }

 int day(int y, int m, int d){
  int res=0;
  int[] days={31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
  for(int i=0; i<m-1; i++){
   res+=days[i];
  }
  res+=y*365+d-1;
  if((m==2&&d<=28)||m==1){
   y--;
  }
  if(y>=0){
   res+=y/4+1;
   res-=y/100+1;
   res+=y/400+1;
  }
  return 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);
 }

 public static void main(String[] args){
  new Main().run();
 }
}

Aizu Online Judge 0121 Seven Puzzle

■0121 Seven Puzzle

先に,全てのパターンについて最小ステップ数を計算しておく.BFSで可能.
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;

 HashMap<Integer, Integer> map;
 int[] a;
 int w=4, h=2;

 void run(){
  a=new int[w*h];
  init();
  for(; sc.hasNext();){
   for(int i=0; i<w*h; i++){
    a[i]=sc.nextInt();
   }
   println(""+map.get(id(a)));
  }
 }

 void init(){

  LinkedList<S> que=new LinkedList<S>();
  map=new HashMap<Integer, Integer>();

  que.offer(new S(0, 0, new int[]{0, 1, 2, 3, 4, 5, 6, 7}));
  map.put(id(que.peek().a), 0);
  int[] dx={0, 0, -1, 1};
  int[] dy={-1, 1, 0, 0};

  for(; !que.isEmpty();){
   S s=que.poll();
   int p=s.y*w+s.x;
   for(int i=0; i<4; i++){
    int x2=s.x+dx[i];
    int y2=s.y+dy[i];
    int p2=y2*w+x2;
    if(x2>=0&&x2<w&&y2>=0&&y2<h){
     int[] a2=s.a.clone();
     int t=a2[p];
     a2[p]=a2[p2];
     a2[p2]=t;
     S s2=new S(x2, y2, a2);
     if(!map.containsKey(id(s2.a))){
      que.offer(s2);
      map.put(id(s2.a), map.get(id(s.a))+1);
     }
    }
   }
  }
 }

 int id(int[] a){
  int res=0;
  for(int e : a){
   res=res*10+e;
  }
  return res;
 }

 class S{
  int x, y;
  int[] a;

  S(int x, int y, int[] a){
   this.x=x;
   this.y=y;
   this.a=a;
  }
 }

 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 0120 Patisserie

■0120 Patisserie

r1のロールケーキにr2のロールケーキを並べると,
長さが2√(r1r2)-r1+r2だけ増える.
dp[k][S]=右端がロールケーキk,集合Sのロールケーキを既に並べたとしたときの最小の長さ
としてDP.計算量はO(2nn2).
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 len, n;
 int[] a;

 void run(){
  for(;sc.hasNext();){
   String[] ss=sc.nextLine().split(" ");
   len=Integer.parseInt(ss[0]);
   n=ss.length-1;
   a=new int[n];
   for(int i=0; i<n; i++){
    a[i]=Integer.parseInt(ss[i+1]);
   }
   solve();
  }
 }

 void solve(){
  double[][] dp=new double[1<<n][n];
  for(int j=0; j<1<<n; j++){
   fill(dp[j], INF);
  }
  for(int i=0; i<n; i++){
   dp[1<<i][i]=2*a[i];
  }
  for(int s=1; s<1<<n; s++){
   for(int j=0; j<n; j++){
    if((s>>j&1)==0){
     continue;
    }
    for(int i=0; i<n; i++){
     if((s>>i&1)==0){
      dp[s|1<<i][i]=min(dp[s|1<<i][i],
        dp[s][j]+2*sqrt(a[j]*a[i])-a[j]+a[i]);
     }
    }
   }
  }
  double min=INF;
  for(int i=0; i<n; i++){
   min=min(min, dp[(1<<n)-1][i]);
  }
  println(min<len+EPS?"OK":"NA");
 }

 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 0514 Quality Checking

■0514 Quality Checking

合格
→3つ共正常
失敗
→2つが正常なら残り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;

 void run(){
  for(;;){
   int na, nb, nc;
   na=sc.nextInt();
   nb=sc.nextInt();
   nc=sc.nextInt();
   if((na|nb|nc)==0){
    break;
   }

   int n=sc.nextInt();
   int[] as=new int[na];
   int[] bs=new int[nb];
   int[] cs=new int[nc];
   Arrays.fill(as, 2);
   Arrays.fill(bs, 2);
   Arrays.fill(cs, 2);

   R[] rs=new R[n];
   for(int i=0; i<n; i++){
    int a=sc.nextInt()-1;
    int b=sc.nextInt()-na-1;
    int c=sc.nextInt()-na-nb-1;
    int r=sc.nextInt();
    rs[i]=new R(a, b, c, r);
    if(r==1){
     as[a]=1;
     bs[b]=1;
     cs[c]=1;
    }
   }

   for(int i=0; i<n; i++){
    if(rs[i].r==0){
     int a=as[rs[i].a];
     int b=bs[rs[i].b];
     int c=cs[rs[i].c];
     if(a==1&&b==1){
      c=0;
     }else if(b==1&&c==1){
      a=0;
     }else if(c==1&&a==1){
      b=0;
     }
     as[rs[i].a]=a;
     bs[rs[i].b]=b;
     cs[rs[i].c]=c;
    }
   }
   for(int i=0; i<na; i++){
    println(as[i]+"");
   }
   for(int i=0; i<nb; i++){
    println(bs[i]+"");
   }
   for(int i=0; i<nc; i++){
    println(cs[i]+"");
   }
  }
 }

 class R{
  int a, b, c, r;

  R(int a, int b, int c, int r){
   this.a=a;
   this.b=b;
   this.c=c;
   this.r=r;
  }
 }

 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 0231 Dangerous Bridge

■0231 Dangerous Bridge

時刻aと時刻b-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, a, b;

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

 void solve(){
  for(int j=0; j<n; j++){
   int sum1=0, sum2=0;
   for(int i=0; i<n; i++){
    if(a[i]<=a[j]&&a[j]<b[i]){
     sum1+=m[i];
    }
    if(a[i]<=b[j]-1&&b[j]-1<b[i]){
     sum2+=m[i];
    }
   }
   if(sum1>150||sum2>150){
    println("NG");
    return;
   }
  }
  println("OK");
 }

 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年3月8日火曜日

Codeforces Round #61 (Div. 2)

コンテストが随分ご無沙汰だったので参加してきました.

Codeforces Round #61 (Div. 2)

A. Petya and Java

面倒だったので,BigIntegerを使って読み込み.実は,入力は必ず正の数なので,負の方向へのチェックは必要ありませんでした….
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;

 void run(){
  BigInteger b=sc.nextBigInteger();
  long[] s={-128, -32768, -2147483648, -9223372036854775808L};
  long[] e={127, 32767, 2147483647, 9223372036854775807L};
  String[] ss={"byte", "short", "int", "long"};
  for(int i=0; i<4; i++){
   if(b.compareTo(new BigInteger(s[i]+""))>=0
     &&b.compareTo(new BigInteger(e[i]+""))<=0){
    println(ss[i]);
    return;
   }
  }
  println("BigInteger");
 }

 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){
  new A().run();
 }
}

B. Petya and Countryside

全探索すればOK.
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 n;
 int[] a;

 void run(){
  n=sc.nextInt();
  a=new int[n];
  for(int i=0; i<n; i++){
   a[i]=sc.nextInt();
  }
  int max=0;
  for(int j=0; j<n; j++){
   int s=1;
   for(int i=j-1; i>=0; i--){
    if(a[i]<=a[i+1]){
     s++;
    }else{
     break;
    }
   }
   for(int i=j+1; i<n; i++){
    if(a[i-1]>=a[i]){
     s++;
    }else{
     break;
    }
   }
   max=max(max, s);
  }
  println(max+"");
 }

 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){
  new B().run();
 }
}

C. Petya and File System

書けば通ると思いましたが,落ちてしまいました.

D. Petya and His Friends

私が考えたのは以下のやり方.
a1a2a3a4an
2222
3333
5555
7777

これを縦に掛けたものがそれぞれ答え.

実際には,6, 10, 15, 15*2, 15*3, …で十分だったようです.
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

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

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

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

 void run(){
  int n=sc.nextInt();
  if(n==2){
   println("-1");
   return;
  }
  BigInteger[] bis=new BigInteger[n];
  for(int i=0; i<n; i++){
   bis[i]=BigInteger.ONE;
  }

  int max=1000;
  int p=0;
  int[] prime=new int[max];
  boolean[] isPrime=new boolean[max+1];
  Arrays.fill(isPrime, true);
  isPrime[0]=isPrime[1]=false;
  for(int i=2; i<=max; i++){
   if(isPrime[i]){
    prime[p++]=i;
    for(int j=2*i; j<=max; j+=i){
     isPrime[j]=false;
    }
   }
  }

  for(int j=0; j<n; j++){
   BigInteger bi=new BigInteger(prime[j]+"");
   for(int i=0; i<n-1; i++){
    bis[(j+i)%n]=bis[(j+i)%n].multiply(bi);
   }
  }
  for(int i=0; i<n; i++){
   if(bis[i].toString().length()>100){
    println("-1");
    return;
   }
  }
  for(int i=0; i<n; i++){
   println(bis[i]+"");
  }
 }

 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){
  new D().run();
 }
}
ooxo- 3226p 68位
1506 -> 1694
紫コーダーになりました.

2011年3月7日月曜日

Aizu Online Judge 0212 Highway Express Bus

■0212 Highway Express Bus

拡張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 c, n, m, s, g;
 LinkedList<E>[] es;

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

 void solve(){
  int[][] d=new int[n][c+1];
  PriorityQueue<P> que=new PriorityQueue<P>();

  for(int i=0; i<n; i++){
   Arrays.fill(d[i], INF);
  }
  d[s][c]=0;
  que.offer(new P(s, c, 0));
  for(; !que.isEmpty();){
   P p=que.poll();
   if(d[p.v][p.c]<p.d){
    continue;
   }
   for(E e : es[p.v]){
    if(d[e.to][p.c]>d[p.v][p.c]+e.cost){
     d[e.to][p.c]=d[p.v][p.c]+e.cost;
     que.offer(new P(e.to, p.c, d[e.to][p.c]));
    }
    if(p.c>0&&d[e.to][p.c-1]>d[p.v][p.c]+e.cost/2){
     d[e.to][p.c-1]=d[p.v][p.c]+e.cost/2;
     que.offer(new P(e.to, p.c-1, d[e.to][p.c-1]));
    }
   }
  }
  int min=INF;
  for(int i=0; i<=c; i++){
   min=min(min, d[g][i]);
  }
  min*=10;
  println(""+min);
 }

 class E{
  int to, cost;

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

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

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

  @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 0209 Scene in a Picture

■0209 Scene in a Picture

全探索.

計算量はO(m2n2)だが,1002502=2.5*107なので余裕.

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, b;

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

 void solve(){
  int[][][] c=new int[4][n][n];
  for(int j=0; j<n; j++){
   for(int i=0; i<n; i++){
    c[0][j][i]=b[j][i];
    c[1][i][n-1-j]=b[j][i];
    c[2][n-1-j][n-1-i]=b[j][i];
    c[3][n-1-i][j]=b[j][i];
   }
  }

  int p=m*m;
  for(int i=0; i<4; i++){
   p=min(p, match(c[i]));
  }
  if(p==m*m){
   println("NA");
  }else{
   println((p%m+1)+" "+(p/m+1));
  }
 }

 int match(int[][] c){
  for(int y=0; y+n<=m; y++){
   for(int x=0; x+n<=m; x++){
    boolean f=true;
    for(int j=0; j<n; j++){
     for(int i=0; i<n; i++){
      f&=c[j][i]==-1||c[j][i]==a[y+j][x+i];
     }
    }
    if(f){
     for(int j=0; j<n; j++){
      for(int i=0; i<n; i++){
       if(c[j][i]!=-1){
        return (y+j)*m+(x+i);
       }
      }
     }
    }
   }
  }
  return m*m;
 }

 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 0207 Block

■0207 Block

(xs,ys)から同じ色を持つブロックについてBFS.(xg,yg)が訪問済みであればOK.

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 w, h;
 int sx, sy;
 int gx, gy;
 int[][] a;

 void run(){
  for(;;){
   w=sc.nextInt();
   h=sc.nextInt();
   if((w|h)==0){
    break;
   }
   sx=sc.nextInt()-1;
   sy=sc.nextInt()-1;
   gx=sc.nextInt()-1;
   gy=sc.nextInt()-1;
   int n=sc.nextInt();
   a=new int[h][w];
   for(int k=0; k<n; k++){
    int c=sc.nextInt();
    int d=sc.nextInt();
    int x=sc.nextInt()-1;
    int y=sc.nextInt()-1;
    for(int j=0; j<2; j++){
     for(int i=0; i<4; i++){
      if(d==0){
       a[y+j][x+i]=c;
      }else{
       a[y+i][x+j]=c;
      }
     }
    }
   }
   solve();
  }
 }

 void solve(){
  LinkedList<P> que=new LinkedList<P>();
  boolean[][] visited=new boolean[h][w];

  int[] dx={0, 0, -1, 1};
  int[] dy={-1, 1, 0, 0};

  que.offer(new P(sx, sy));
  visited[sy][sx]=true;

  for(; !que.isEmpty();){
   P p=que.poll();
   for(int i=0; i<4; i++){
    P q=new P(p.x+dx[i], p.y+dy[i]);
    if(q.x>=0&&q.x<w&&q.y>=0&&q.y<h&&a[q.y][q.x]==a[sy][sx]
      &&!visited[q.y][q.x]){
     que.offer(q);
     visited[q.y][q.x]=true;
    }
   }
  }
  println(visited[gy][gx]?"OK":"NG");
 }

 class P{
  int x, y;

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

 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 0203 A New Plan of Aizu Ski Resort

■0203 A New Plan of Aizu Ski Resort

dp[j][i]=(i,j)に到達するまでの滑り方のパターン数
としてDP.
dp[0][i]=
0 - (i,0)に障害物がある
1 - (i,0)に障害物がない
あとは,説明通りに更新していく.dp[n]まで用意しておいて,dp[n-1]とdp[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 Main{

 Scanner sc=new Scanner(System.in);

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

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

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

 void solve(){
  long[][] dp=new long[n+1][m];
  for(int i=0; i<m; i++){
   if(a[0][i]==0){
    dp[0][i]=1;
   }
  }
  for(int j=0; j<n-1; j++){
   for(int i=0; i<m; i++){
    switch(a[j][i]){
    case 0:
     if(i-1>=0&&a[j+1][i-1]==0)
      dp[j+1][i-1]+=dp[j][i];
     if(a[j+1][i]!=1)
      dp[j+1][i]+=dp[j][i];
     if(i+1<m&&a[j+1][i+1]==0)
      dp[j+1][i+1]+=dp[j][i];
     break;
    case 2:
     if(j>=n-2||a[j+2][i]!=1)
      dp[j+2][i]+=dp[j][i];
     break;
    }
   }
  }
  long ans=0;
  for(int j=n-1; j<n+1; j++){
   for(int i=0; i<m; i++){
    ans+=dp[j][i];
   }
  }
  println(ans+"");
 }

 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年3月5日土曜日

Aizu Online Judge 0202 At Boss's Expense

■0202 At Boss's Expense

可能な合計金額と,素数全列挙.

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, x;
 int[] a;

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

 void solve(){
  int max=1000000;
  int p=0;
  int[] prime=new int[max];
  boolean[] isPrime=new boolean[max+1];
  Arrays.fill(isPrime, true);
  isPrime[0]=isPrime[1]=false;
  for(int i=2; i<=max; i++){
   if(isPrime[i]){
    prime[p++]=i;
    for(int j=2*i; j<=max; j+=i){
     isPrime[j]=false;
    }
   }
  }
  boolean[] dp=new boolean[max+1];
  dp[0]=true;
  for(int j=0; j<n; j++){
   for(int i=a[j]; i<=max; i++){
    dp[i]|=dp[i-a[j]];
   }
  }
  int ans=0;
  for(int i=2; i<=x; i++){
   if(dp[i]&&isPrime[i]){
    ans=i;
   }
  }
  if(ans>0){
   println(ans+"");
  }else{
   println("NA");
  }
 }

 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 0201 Wrought Gold Master

■0201 Wrought Gold Master

DFS.あるアイテムについてそれ自身を買う,あるいはレシピを用いて錬金するという両手法を試し,最小を返す.

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, m;
 HashMap<String, Integer> val;
 HashMap<String, LinkedList<String>> recipe;
 String item;

 void run(){
  for(;;){
   val=new HashMap<String, Integer>();
   recipe=new HashMap<String, LinkedList<String>>();
   n=sc.nextInt();
   if(n==0){
    break;
   }
   for(int i=0; i<n; i++){
    String s=sc.next();
    int d=sc.nextInt();
    val.put(s, d);
   }
   m=sc.nextInt();
   for(int j=0; j<m; j++){
    String s=sc.next();
    int k=sc.nextInt();
    LinkedList<String> list=new LinkedList<String>();
    for(int i=0; i<k; i++){
     String t=sc.next();
     list.add(t);
    }
    recipe.put(s, list);
   }
   item=sc.next();
   solve();
  }
 }

 void solve(){
  println(dfs(item)+"");
 }

 int dfs(String s){
  int res=INF;
  if(val.containsKey(s)){
   res=min(res, val.get(s));
  }
  if(recipe.containsKey(s)){
   int sum=0;
   for(String t : recipe.get(s)){
    sum+=dfs(t);
   }
   res=min(res, sum);
  }
  return 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);
 }

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

Aizu Online Judge 0200 Traveling Alone: One-way Ticket of Youth

■0200 Traveling Alone: One-way Ticket of Youth

Warshall-Floyd.O(n3)でn=300なので,多分間に合うだろうという魂胆.

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[][] cost, time;
 int n, m, k;

 void run(){
  for(;;){
   n=sc.nextInt();
   m=sc.nextInt();
   if((n|m)==0){
    break;
   }
   cost=new int[m][m];
   time=new int[m][m];
   for(int j=0; j<m; j++){
    fill(cost[j], INF);
    fill(time[j], INF);
   }
   for(int i=0; i<n; i++){
    int a=sc.nextInt()-1;
    int b=sc.nextInt()-1;
    int c=sc.nextInt();
    int t=sc.nextInt();
    cost[a][b]=cost[b][a]=c;
    time[a][b]=time[b][a]=t;
   }
   for(int k=0; k<m; k++){
    for(int i=0; i<m; i++){
     for(int j=0; j<m; j++){
      cost[i][j]=min(cost[i][j], cost[i][k]+cost[k][j]);
      time[i][j]=min(time[i][j], time[i][k]+time[k][j]);
     }
    }
   }
   k=sc.nextInt();
   for(int i=0; i<k; i++){
    int p=sc.nextInt()-1;
    int q=sc.nextInt()-1;
    int r=sc.nextInt();
    if(r==0){
     println(cost[p][q]+"");
    }else{
     println(time[p][q]+"");
    }
   }
  }
 }

 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年3月4日金曜日

Aizu Online Judge 0197 Greatest Common Divisor: Euclidean Algorithm

■0197 Greatest Common Divisor: Euclidean Algorithm

やるだけ.

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;

 void run(){
  for(;;){
   int x=sc.nextInt();
   int y=sc.nextInt();
   if((x|y)==0){
    break;
   }
   if(x<y){
    int t=x;
    x=y;
    y=t;
   }
   for(int i=0;; i++){
    if(y==0){
     println(x+" "+i);
     break;
    }
    x=x%y;
    int t=x;
    x=y;
    y=t;
   }
  }
 }

 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 0196 Baseball Championship

■0196 Baseball Championship

やるだけ.

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;

 void run(){
  for(;;){
   int n=sc.nextInt();
   if(n==0){
    break;
   }
   R[] rs=new R[n];
   for(int j=0; j<n; j++){
    rs[j]=new R();
    rs[j].name=sc.next();
    for(int i=0; i<n-1; i++){
     switch(sc.nextInt()){
     case 0:
      rs[j].win--;
      break;
     case 1:
      rs[j].lose++;
      break;
     }
    }
   }
   Arrays.sort(rs);
   for(R r : rs){
    println(r.name);
   }
  }
 }

 class R implements Comparable<R>{
  int win, lose;
  String name;

  @Override
  public int compareTo(R r){
   if(win!=r.win){
    return win-r.win;
   }else{
    return lose-r.lose;
   }
  }
 }

 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 0195 What is the Most Popular Shop in Tokaichi?

■0195 What is the Most Popular Shop in Tokaichi?

やるだけ.

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;

 void run(){
  for(;;){
   int n=5;
   int max=0;
   char c='A';
   for(int i=0; i<n; i++){
    int a=sc.nextInt()+sc.nextInt();
    if(a==0){
     return;
    }
    if(a>max){
     c=(char)('A'+i);
     max=a;
    }
   }
   println(c+" "+max);
  }
 }

 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 0189 Convenient Location

■0189 Convenient Location

各々のノードのついて,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 n, m;
 LinkedList<E>[] es;

 @SuppressWarnings("unchecked")
 void run(){
  for(;;){
   es=new LinkedList[10];
   for(int i=0; i<es.length; i++){
    es[i]=new LinkedList<E>();
   }
   n=0;
   m=sc.nextInt();
   if(m==0){
    break;
   }
   for(int i=0; i<m; i++){
    int u=sc.nextInt();
    int v=sc.nextInt();
    int w=sc.nextInt();
    es[u].add(new E(v, w));
    es[v].add(new E(u, w));
    n=max(n, u+1);
    n=max(n, v+1);
   }
   solve();
  }
 }

 void solve(){
  int min=INF;
  int v=0;
  for(int i=0; i<n; i++){
   int d=dijkstra(i);
   if(d<min){
    v=i;
    min=d;
   }
  }
  println(v+" "+min);
 }

 int dijkstra(int s){
  int[] d=new int[n];
  PriorityQueue<P> que=new PriorityQueue<P>();

  Arrays.fill(d, INF);
  d[s]=0;
  que.offer(new P(s, 0));
  for(; !que.isEmpty();){
   P p=que.poll();
   if(d[p.v]<p.d){
    continue;
   }
   for(E e : es[p.v]){
    if(d[e.to]>d[p.v]+e.cost){
     d[e.to]=d[p.v]+e.cost;
     que.offer(new P(e.to, d[e.to]));
    }
   }
  }

  int res=0;
  for(int i=0; i<n; i++){
   res+=d[i];
  }
  return res;
 }

 class E{
  int to, cost;

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

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

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

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