主にコーディング: 4月 2011

2011年4月30日土曜日

今月の〇〇(2011年4月)

■Aizu Online Judge

Solved:254/46th
Rating:203.75/50th
Ratingは目標通り200に到達しましたが，そのせいでSolvedの順位が下がってしまいました．5月は，Solvedの順位を30位以上，願わくば20位以上にしたいです．

■TopCoder/Codeforces

Codeforcesは，一旦Div.2に落ちたものの，再びDiv.1に復帰しました．
TopCoderは，Rating微増．

Aizu Online Judge 1202 Mobile Phone Coverage

■1202 Mobile Phone Coverage

面倒な問題．下の画像のような感じに分割した．区間をマージする処理が面倒だった．

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;
 R[] rs;
 int caze;

 void run(){
  for(caze=1;; caze++){
   n=sc.nextInt();
   if(n==0){
    break;
   }
   rs=new R[n];
   for(int i=0; i<n; i++){
    double x=sc.nextDouble();
    double y=sc.nextDouble();
    double r=sc.nextDouble();
    rs[i]=new R(x-r, y-r, x+r, y+r);
   }
   solve();
  }
 }

 void solve(){
  TreeSet<Double> setX=new TreeSet<Double>();
  for(int i=0; i<n; i++){
   setX.add(rs[i].x1);
   setX.add(rs[i].x2);
  }
  Double[] xs=setX.toArray(new Double[0]);
  sort(xs);
  int m=xs.length;
  @SuppressWarnings("unchecked")
  TreeSet<R>[] setR=new TreeSet[m];
  for(int i=0; i<m; i++){
   setR[i]=new TreeSet<R>();
  }

  for(int j=0; j<m-1; j++){
   for(int i=0; i<n; i++){
    if(rs[i].x1<xs[j]+EPS&&xs[j]+EPS<rs[i].x2){
     setR[j].add(rs[i]);
    }
   }
  }

  double sum=0;
  for(int k=0; k<m-1; k++){
   LinkedList<Double> seg=new LinkedList<Double>();
   for(R r : setR[k]){
    if(abs(r.y1-r.y2)<EPS){
     continue;
    }
    int i=seg.size(), j=seg.size();
    for(int p=seg.size()-1; p>=0; p--){
     double y=seg.get(p);
     if(y+EPS>r.y2){
      j=p;
     }
     if(y+EPS>r.y1){
      i=p;
     }
    }
    for(int p=i; p<j; p++){
     seg.remove(i);
    }
    if(j%2==0){
     seg.add(i, r.y2);
    }
    if(i%2==0){
     seg.add(i, r.y1);
    }
   }
   double len=0;
   for(int i=0; i<seg.size(); i+=2){
    len+=seg.get(i+1)-seg.get(i);
   }
   sum+=len*(xs[k+1]-xs[k]);
  }
  println(String.format("%d %.2f", caze, sum+EPS));
 }

 class R implements Comparable<R>{
  double x1, y1, x2, y2;

  R(double x1, double y1, double x2, double y2){
   this.x1=x1;
   this.y1=y1;
   this.x2=x2;
   this.y2=y2;
  }

  @Override
  public int compareTo(R arg0){
   if(y1-y2+EPS<0){
    return -1;
   }else if(y1-y2>0+EPS){
    return 1;
   }else if(x1-x2+EPS<0){
    return -1;
   }else if(x1-x2>0+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 1221 Numoeba

■1221 Numoeba

制限時間・メモリ共に余裕があるので，あとは気合で書くだけ．

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 k;
 int m;
 int mod=12345678;
 boolean[] visited=new boolean[10000];

 void run(){
  for(;;){
   k=sc.nextInt();
   if(k==0){
    break;
   }
   solve();
  }
 }

 void solve(){
  Cell leader=new Cell(k);
  m=0;
  int maxNum=1;
  for(int k=1;; k++){
   LinkedList<Cell> que=new LinkedList<Cell>();
   que.offer(leader);
   fill(visited, false);
   visited[leader.v]=true;

   for(; !que.isEmpty();){
    Cell c=que.poll();
    int n=c.n*3+1;
    for(; n%2==0;){
     n/=2;
    }
    n%=mod;
    c.candidate=n>c.n&&(c.size()==0||(c.size()==1&&c!=leader));
    c.n=n;
    if(c.n==1){
     if(c==leader){
      println(k+" "+maxNum);
      return;
     }
     Cell par=null;
     for(Cell d : c){
      if(visited[d.v]){
       par=d;
      }
      d.remove(c);
     }
     c.remove(par);
     if(c.size()==1){
      Cell child=c.getFirst();
      par.add(child);
      child.add(par);
      que.offer(child);
      visited[child.v]=true;
     }
    }else{
     for(Cell d : c){
      if(!visited[d.v]){
       que.offer(d);
       visited[d.v]=true;
      }
     }
    }
   }
   fill(visited, false);
   Cell newLeader=new Cell(0);
   boolean overlap=false;
   int num=0;

   que.offer(leader);
   visited[leader.v]=true;
   for(; !que.isEmpty();){
    Cell c=que.poll();
    num++;
    for(Cell d : c){
     if(!visited[d.v]){
      que.offer(d);
      visited[d.v]=true;
     }
    }
    if(c.n>newLeader.n){
     newLeader=c;
     overlap=false;
    }else if(c.n==newLeader.n){
     overlap=true;
    }
    if(c.candidate&&((c.size()==1&&c!=leader)||c.size()==0)){
     Cell d=new Cell(((c.n+1)/2)|1);
     if(d.n!=1){
      c.add(d);
      d.add(c);
      num++;
     }
    }
   }

   if(!overlap){
    leader=newLeader;
    Cell c=new Cell(((leader.n+1)/2-1)|1);
    if(c.n!=1){
     leader.add(c);
     c.add(leader);
     num++;
    }
   }
   maxNum=max(maxNum, num);
  }
 }

 void dfs(Cell leader){
  fill(visited, false);
  dfs(leader, "");
 }

 void dfs(Cell c, String tab){
  debug(tab, c.n, c.size(), c.v);
  visited[c.v]=true;
  for(Cell d : c){
   if(!visited[d.v]){
    dfs(d, tab+"  ");
   }
  }
 }

 class Cell extends LinkedList<Cell>{
  int n, v;
  boolean candidate;

  Cell(int n){
   this.n=n;
   this.v=m++;
  }

  @Override
  public int hashCode(){
   return v;
  }

  @Override
  public boolean equals(Object o){
   return hashCode()==((Cell)o).hashCode();
  }
 }

 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 1215 Co-occurrence Search

■1215 Co-occurrence Search

しゃくとり法で解くことが出来る．入力がややこしく，無限ループによる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;

 char[] s, key;

 void run(){
  for(;;){
   StringBuffer lines=new StringBuffer();
   for(;;){
    String line=sc.nextLine();
    if(line.equals("")){
     break;
    }
    lines.append(line);
   }
   s=lines.toString().toCharArray();
   key=sc.nextLine().toCharArray();
   solve();
   if(sc.hasNext()){
    sc.nextLine();
   }else{
    break;
   }
  }
  System.out.flush();
 }

 void solve(){
  int i=0, j=0;
  int num=0;
  int n=s.length;

  int min=INF;
  int cMin=0, iMin=0, jMin=0;

  int nKey=0;
  boolean[] isKey=new boolean[256];
  for(char c : key){
   isKey[c]=true;
  }
  for(boolean b : isKey){
   nKey+=b?1:0;
  }
  int[] count=new int[256];

  for(;;){
   for(; j<n&&num<nKey; j++){
    if(isKey[s[j]]&&count[s[j]]++==0){
     num++;
    }
   }

   if(num<nKey){
    break;
   }

   if(j-i<min){
    iMin=i;
    jMin=j;
    min=j-i;
    cMin=1;
   }else if(j-i==min){
    cMin++;
   }

   if(isKey[s[i]]&&--count[s[i]]==0){
    num--;
   }
   i++;
  }

  println(cMin+"\n");
  if(cMin>0){
   String ans=new String(s, iMin, jMin-iMin);
   for(int k=0; k<(ans.length()-1)/72+1; k++){
    println(ans.substring(k*72, min((k+1)*72, ans.length())));
   }
   println("");
  }
 }

 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 1226 Fishnet

■1226 Fishnet

全通り試す．面積はヘロンの公式を使えば簡単．

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;
 P[] a, b, c, d;

 void run(){
  for(;;){
   n=sc.nextInt();
   if(n==0){
    break;
   }
   n+=2;
   a=new P[n];
   b=new P[n];
   c=new P[n];
   d=new P[n];
   a[0]=new P(0, 0);
   b[0]=new P(0, 1);
   c[0]=new P(0, 0);
   d[0]=new P(1, 0);
   for(int i=1; i<n-1; i++)
    a[i]=new P(sc.nextDouble(), 0);
   for(int i=1; i<n-1; i++)
    b[i]=new P(sc.nextDouble(), 1);
   for(int i=1; i<n-1; i++)
    c[i]=new P(0, sc.nextDouble());
   for(int i=1; i<n-1; i++)
    d[i]=new P(1, sc.nextDouble());
   a[n-1]=new P(1, 0);
   b[n-1]=new P(1, 1);
   c[n-1]=new P(0, 1);
   d[n-1]=new P(1, 1);
   solve();
  }
 }

 void solve(){
  double ans=0;
  for(int j=0; j<n-1; j++){
   for(int i=0; i<n-1; i++){
    P p1=isLL(a[i], b[i], c[j], d[j]);
    P p2=isLL(a[i+1], b[i+1], c[j], d[j]);
    P p3=isLL(a[i+1], b[i+1], c[j+1], d[j+1]);
    P p4=isLL(a[i], b[i], c[j+1], d[j+1]);
    ans=max(ans, area(p1, p2, p3)+area(p3, p4, p1));
   }
  }
  println(String.format("%.6f", ans+EPS));
 }

 double area(P p1, P p2, P p3){
  double a=p1.sub(p2).abs();
  double b=p2.sub(p3).abs();
  double c=p3.sub(p1).abs();
  double s=(a+b+c)/2;
  return Math.sqrt(s*(s-a)*(s-b)*(s-c));
 }

 // 直線と直線の交点
 P isLL(P p1, P p2, P q1, P q2){
  double d=q2.sub(q1).det(p2.sub(p1));
  if(abs(d)<EPS)
   return null;
  return p1.add(p2.sub(p1).mul(q2.sub(q1).det(q1.sub(p1))/d));
 }

 class P{
  double x, y;

  P(){
   this(0, 0);
  }

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

  P add(P p){
   return new P(x+p.x, y+p.y);
  }

  P sub(P p){
   return new P(x-p.x, y-p.y);
  }

  P mul(double m){
   return new P(x*m, y*m);
  }

  P div(double d){
   return new P(x/d, y/d);
  }

  double abs(){
   return Math.sqrt(abs2());
  }

  double abs2(){
   return x*x+y*y;
  }

  double arg(){
   return Math.atan2(y, x);
  }

  // inner product
  double dot(P p){
   return x*p.x+y*p.y;
  }

  // outer product
  double det(P p){
   return x*p.y-y*p.x;
  }

  P rot90(){
   return new P(-y, x);
  }

  // conjugation
  P conj(){
   return new P(x, -y);
  }

  @Override
  public String toString(){
   return "("+x+", "+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();
 }
}

2011年4月21日木曜日

Aizu Online Judge 1217 Family Tree

■ 1217 Family Tree

入力の解析が少し面倒．クエリに対する判定は，ある人の親さえ分かれば非常に簡単に出来る．
下記のコードではchildrenも記録していたけど全く必要なかった．

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, String> parent;
 HashMap<String, LinkedList<String>> children;

 void run(){
  for(;;){
   n=sc.nextInt();
   m=sc.nextInt();
   if((n|m)==0){
    break;
   }
   parent=new HashMap<String, String>();
   children=new HashMap<String, LinkedList<String>>();
   sc.nextLine();
   String p="", r=""; // 親, 1つ前
   children.put(p, new LinkedList<String>());
   int x=-1;
   for(int j=0; j<n; j++){
    String s=sc.nextLine();
    int y=s.length()-s.replaceAll(" ", "").length();
    s=s.replaceAll(" ", "");
    // debug(s, r, p);
    if(y>x){
     p=r;
    }else if(y<x){
     for(int i=y; i<x; i++){
      p=parent.get(p);
     }
    }
    parent.put(s, p);
    children.get(p).add(s);
    children.put(s, new LinkedList<String>());
    x=y;
    r=s;
   }
   // dfs("", "");
   for(int i=0; i<m; i++){
    String s=sc.next();
    sc.next();
    sc.next();
    char c=sc.next().charAt(0);
    sc.next();
    String t=sc.next();
    t=t.substring(0, t.length()-1);
    boolean f=false;
    switch(c){
    case 'c':
     f=parent.containsKey(s)&&parent.get(s).equals(t);
     break;
    case 'p':
     f=parent.containsKey(t)&&parent.get(t).equals(s);
     break;
    case 's':
     f=parent.containsKey(s)&&parent.containsKey(t)
       &&parent.get(s).equals(parent.get(t));
     break;
    case 'd':
     for(s=parent.get(s); s!=null; s=parent.get(s)){
      f|=s.equals(t);
     }
     break;
    case 'a':
     for(t=parent.get(t); t!=null; t=parent.get(t)){
      f|=t.equals(s);
     }
     break;
    }
    println(f?"True":"False");
   }
   println("");
  }
 }

 void dfs(String s, String tab){
  for(String t : children.get(s)){
   debug(tab, t, parent.get(t));
   dfs(t, tab+"\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();
 }
}

2011年4月20日水曜日

Codeforces Beta Round #69 (Div. 2 Only)

Div. 1復帰が目標でした．

A. Panoramixs Prediction

値が小さいので愚直に一つずつ試行．

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 m, n;

 void run(){
  m=sc.nextInt();
  n=sc.nextInt();
  boolean f=true;
  for(int i=m+1; i<n; i++){
   f&=!isP(i);
  }
  f&=isP(n);
  println(f?"YES":"NO");
 }

 boolean isP(int n){
  for(int i=2; i*i<=n; i++){
   if(n%i==0){
    return false;
   }
  }
  return n!=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){
  new A().run();
 }
}

B. Depression

%12を忘れないように気をつけるだけ．

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;

 void run(){
  String[] ss=sc.next().split(":");
  double h=Integer.parseInt(ss[0]);
  double m=Integer.parseInt(ss[1]);
  h=(h%12)/12.0*360;
  m=m/60.0*360;
  h=(h+m/12)%360;
  println(h+" "+m);
 }

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

全探索で解くことが出来るが，ちょっとしたミスをしたためSystem Test落ち．下は修正版．

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

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

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

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

 int n, a, b, c;
 int[] p, q;
 HashMap<String, Integer> map;

 void run(){
  int m=7;

  map=new HashMap<String, Integer>();
  map.put("Anka", 0);
  map.put("Chapay", 1);
  map.put("Cleo", 2);
  map.put("Troll", 3);
  map.put("Dracul", 4);
  map.put("Snowy", 5);
  map.put("Hexadecimal", 6);

  n=sc.nextInt();
  p=new int[n];
  q=new int[n];
  for(int i=0; i<n; i++){
   p[i]=map.get(sc.next());
   sc.next();
   q[i]=map.get(sc.next());
  }
  a=sc.nextInt();
  b=sc.nextInt();
  c=sc.nextInt();

  long dmin=1L<<32;
  int lmax=0;
  for(int k=1; k<1<<m; k++){
   for(int j=1; j<1<<m; j++){
    int i=((1<<m)-1)&~(k^j);
    if((k^j)==(k|j)&&i>0){
     int x=a/Integer.bitCount(i);
     int y=b/Integer.bitCount(j);
     int z=c/Integer.bitCount(k);
     int d=max(abs(x-y), max(abs(y-z), abs(z-x)));

     int l=0;
     for(int e=0; e<n; e++){
      if(((k>>p[e])&1)!=0&&((k>>q[e])&1)!=0)
       l++;
      else if(((j>>p[e])&1)!=0&&((j>>q[e])&1)!=0)
       l++;
      else if(((i>>p[e])&1)!=0&&((i>>q[e])&1)!=0)
       l++;
     }
     if(d<dmin){
      dmin=d;
      lmax=l;
     }else if(d==dmin){
      lmax=max(lmax, l);
     }
    }
   }
  }
  println(dmin+" "+lmax);
 }

 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 C().run();
 }
}

D. Falling Anvils

x²+√px+q=0は，p≧4qならば実解が存在する．
つまり，(p,q)∈[0,a]×[-b,b]の長方形内においてp≧4qを満たす領域の面積を計算し，それを長方形の面積で割った値が，実解が存在する確率．a=0やb=0の時は，0除算を避けるために例外処理を追加する必要がある．

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;

 int t;
 double a, b;

 void run(){
  t=sc.nextInt();
  for(int i=0; i<t; i++){
   a=sc.nextInt();
   b=sc.nextInt();
   double area;
   if(4*b<a+EPS){
    area=2*b*(a-b);
   }else{
    area=a*(b+a/8);
   }
   if(abs(b)<EPS){
    println("1");
   }else if(abs(a)<EPS){
    println("0.5");
   }else{
    println(area/(2*a*b)+"");
   }
  }
 }

 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- 2726p 46位
1624 -> 1654
復帰完了…というところです．

Aizu Online Judge 1218 Push!!

■1218 Push!!

人の座標と荷物の座標を状態とし，距離を荷物を押した回数としたダイクストラで解ける．

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 mx0, my0, cx0, cy0, gx, gy;

 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();
     if(a[j][i]==2){
      cx0=i;
      cy0=j;
      a[j][i]=0;
     }else if(a[j][i]==3){
      gx=i;
      gy=j;
      a[j][i]=0;
     }else if(a[j][i]==4){
      mx0=i;
      my0=j;
      a[j][i]=0;
     }
    }
   }
   solve();
  }
 }

 void solve(){
  PriorityQueue<P> que=new PriorityQueue<P>();
  boolean[][][][] visited=new boolean[m][n][m][n];
  int[][][][] d=new int[m][n][m][n];

  for(int k=0; k<m; k++){
   for(int j=0; j<n; j++){
    for(int i=0; i<m; i++){
     fill(d[k][j][i], INF);
    }
   }
  }

  que.add(new P(mx0, my0, cx0, cy0));
  visited[mx0][my0][cx0][cy0]=true;
  d[mx0][my0][cx0][cy0]=0;

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

  for(; !que.isEmpty();){
   P p=que.poll();
   if(d[p.mx][p.my][p.cx][p.cy]<p.d){
    continue;
   }
   for(int i=0; i<4; i++){
    P q=new P(p.mx+dx[i], p.my+dy[i], p.cx, p.cy);
    int push=0;
    // 人が画面外or移動不可
    if(q.mx<0||q.mx>=m||q.my<0||q.my>=n||a[q.my][q.mx]==1){
     continue;
    }
    // 人の移動先がブロック
    if(q.mx==q.cx&&q.my==q.cy){
     q.cx+=dx[i];
     q.cy+=dy[i];
     push=1;
    }
    // ブロックが画面外or配置不可
    if(q.cx<0||q.cx>=m||q.cy<0||q.cy>=n||a[q.cy][q.cx]==1){
     continue;
    }
    // 訪問していない
    if(!visited[q.mx][q.my][q.cx][q.cy]){
     q.d=d[q.mx][q.my][q.cx][q.cy]=d[p.mx][p.my][p.cx][p.cy]
       +push;
     visited[q.mx][q.my][q.cx][q.cy]=true;
     que.offer(q);
    }
   }
  }

  int min=INF;
  for(int j=0; j<n; j++){
   for(int i=0; i<m; i++){
    min=min(min, d[i][j][gx][gy]);
   }
  }

  println(""+(min==INF?-1:min));

 }

 class P implements Comparable<P>{
  int mx, my, cx, cy;
  int d;

  P(int mx, int my, int cx, int cy){
   this.mx=mx;
   this.my=my;
   this.cx=cx;
   this.cy=cy;
  }

  @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 1209 Square Coins

■1209 Square Coins

dp[i]を支払う金額がiの時のコインの組み合わせの数とする．
コインa[0],…,a[j-1]までのdp[i]が求められていれば，a[j]についてのdp[i]を以下の式で求めていけばよい．
dp[i]+=dp[i-a[j]]
初期値は，
dp[0]=1
dp[i]=0 (i≠0)

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(){
  int n=17;
  int[] a=new int[n];
  for(int i=0; i<n; i++){
   a[i]=(i+1)*(i+1);
  }
  int max=300;
  int[] dp=new int[max];
  dp[0]=1;
  for(int j=0; j<n; j++){
   for(int i=a[j]; i<max; i++){
    dp[i]+=dp[i-a[j]];
   }
  }
  for(;;){
   int k=sc.nextInt();
   if(k==0){
    break;
   }
   println(""+dp[k]);
  }
 }

 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年4月19日火曜日

Aizu Online Judge 1209 Square Coins

■1209 Square Coins

dp[i]を支払う金額がiの時のコインの組み合わせの数とする．
コインa[0],…,a[j-1]までのdp[i]が求められていれば，a[j]についてのdp[i]を以下の式で更新すれば良い．
dp[i]+=dp[i-a[j]]

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(){
  int n=17;
  int[] a=new int[n];
  for(int i=0; i<n; i++){
   a[i]=(i+1)*(i+1);
  }
  int max=300;
  int[] dp=new int[max];
  dp[0]=1;
  for(int j=0; j<n; j++){
   for(int i=a[j]; i<max; i++){
    dp[i]+=dp[i-a[j]];
   }
  }
  for(;;){
   int k=sc.nextInt();
   if(k==0){
    break;
   }
   println(""+dp[k]);
  }
 }

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

TopCoder Member SRM 503 Div1 Medium KingdomXCitiesandVillages

■KingdomXCitiesandVillages

問題・解説は，Match Editorial Archiveを参考に．

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;
public class KingdomXCitiesandVillages {
 int INF=1<<28;
 double EPS=1e-9;

 int m, n;

 public double determineLength(int[] cx, int[] cy, int[] vx, int[] vy) {
  m=cx.length;
  n=vx.length;
  double sum=0;
  for(int j=0;j<n;j++){
   LinkedList<R> list=new LinkedList<R>();
   for(int i=0;i<n;i++){
    if(i!=j){
     list.add(new R(Math.hypot(vx[j]-vx[i], vy[j]-vy[i]), false));
    }
   }
   for(int i=0;i<m;i++){
    list.add(new R(Math.hypot(vx[j]-cx[i], vy[j]-cy[i]), true));
   }
   R[] rs=list.toArray(new R[0]);
   Arrays.sort(rs);
   for(int i=0;i<rs.length;i++){
    if(rs[i].isCity){
     sum+=rs[i].d/(i+1);
     break;
    }else{
     sum+=rs[i].d/(i+1)/(i+2);
    }
   }
  }
  return sum;
 }

 class R implements Comparable<R>{
  double d;
  boolean isCity;
  R(double d, boolean isCity){
   this.d=d;
   this.isCity=isCity;
  }
  public int compareTo(R r){
   if(d-r.d+EPS<0){
    return -1;
   }else if(d-r.d>0+EPS){
    return 1;
   }else{
    return 0;
   }
  }
 }
}


// Powered by FileEdit
// Powered by TZTester 1.01 [25-Feb-2003]
// Powered by CodeProcessor

2011年4月18日月曜日

Aizu Online Judge 1216 Lost in Space

■1216 Lost in Space

全探索で間に合う．
元の三角形の辺の長さをd[i]とする．
与えられた座標軍からある3点を選び，それぞれの辺の長さをe[i]とする．
この時，それぞれの辺の比r[i]は，
r[i]=e[i]/d[i]
となる．
それぞれの比の誤差が，0.1%以上になることは無い，というのだから，任意のi，jに対して，
|r[i]-r[j]|/r[i] < 0.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;

 double[] d;
 P[] ps;
 int n;

 void run(){
  d=new double[3];
  for(int t=sc.nextInt(); t>0; t--){
   for(int i=0; i<3; i++){
    d[i]=sc.nextDouble();
   }
   n=sc.nextInt();
   ps=new P[n];
   for(int i=0; i<n; i++){
    double x=sc.nextDouble();
    double y=sc.nextDouble();
    double z=sc.nextDouble();
    ps[i]=new P(x, y, z);
   }
   solve();
  }
 }

 void solve(){
  double[] len={0, 0, 0};
  for(int c=0; c<n; c++){
   for(int b=0; b<n; b++){
    if(b==c){
     continue;
    }
    for(int a=0; a<n; a++){
     if(a==b||a==c){
      continue;
     }
     len[0]=ps[b].sub(ps[c]).abs()/d[0];
     len[1]=ps[c].sub(ps[a]).abs()/d[1];
     len[2]=ps[a].sub(ps[b]).abs()/d[2];
     boolean error=false;
     for(int i=0; i<3; i++){
      int p=i;
      int q=(i+1)%3;
      error|=abs(len[p]-len[q])/len[p]+EPS>=0.001;
     }
     if(!error){
      println((a+1)+" "+(b+1)+" "+(c+1));
     }
    }
   }
  }
 }

 class P{
  double x, y, z;

  P(){
   this(0, 0, 0);
  }

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

  P add(P p){
   return new P(x+p.x, y+p.y, z+p.y);
  }

  P sub(P p){
   return new P(x-p.x, y-p.y, z-p.z);
  }

  P mul(double m){
   return new P(x*m, y*m, z*m);
  }

  P div(double d){
   return new P(x/d, y/d, z/d);
  }

  double abs(){
   return Math.sqrt(abs2());
  }

  double abs2(){
   return x*x+y*y+z*z;
  }

  // inner product
  double dot(P p){
   return x*p.x+y*p.y+z*p.y;
  }

  // outer product
  P det(P p){
   return new P(y*p.z-z*p.y, z*p.x-x*p.z, x*p.y-y*p.x);
  }

  @Override
  public String toString(){
   return x+", "+y+", "+z;
  }
 }

 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 1214 Walking Ant

■1214 Walking Ant

BFSで解ける．但し状態を，(x, y, hp)とする．hpは現在の体力を表す．

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 sx, sy, gx, gy;
 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();
     if(a[j][i]==2){
      sx=i;
      sy=j;
      a[j][i]=1;
     }else if(a[j][i]==3){
      gx=i;
      gy=j;
      a[j][i]=1;
     }
    }
   }
   solve();
  }
 }

 void solve(){
  int max=7;
  int[][][] d=new int[n][m][max];
  boolean[][][] visited=new boolean[n][m][max];
  LinkedList<P> que=new LinkedList<P>();

  for(int j=0; j<n; j++){
   for(int i=0; i<m; i++){
    fill(d[j][i], INF);
   }
  }

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

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

  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], p.hp-1);
    if(q.x>=0&&q.x<m&&q.y>=0&&q.y<n&&a[q.y][q.x]!=0&&q.hp>0){
     if(a[q.y][q.x]==4){
      q.hp=6;
     }
     if(!visited[q.y][q.x][q.hp]){
      que.offer(q);
      d[q.y][q.x][q.hp]=d[p.y][p.x][p.hp]+1;
      visited[q.y][q.x][q.hp]=true;
     }
    }
   }
  }
  int ans=INF;
  for(int k=0; k<max; k++){
   ans=min(ans, d[gy][gx][k]);
  }
  println((ans!=INF?ans:-1)+"");
 }

 class P{
  int x, y, hp;

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

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

TopCoder Member SRM 503

SRM 503(12/19 1:00~3:00)

■FoxMakingDice(Div1 Easy)

Toastmanは，パンを何枚か焼きたい．パンには幾つかの種類があり，ある種類のパンは，X分未満焼くとunder toasted，X分超過焼くとover toastedとなる．
Toastmanは，パンを焼いたが，m_i分焼いてunder toastedだったもの，また，n_i分焼いてover toastedだったものが出来た．Toastmanは何種類のパンを用いたかを覚えていないが，ある種類のパンを焼いたときにunder toasted・over toastedだったものがそれぞれ少なくとも1枚以上はあったという．
パンの種類の最小数を答えよ．

under toastedだったものをU，over toastedだったものをOとし，それらを焼かれた時間の数直線にプロットする．例えば下図．
UOUOOUOUOUOUO

・パンの種類が1つで良い場合．

UUUUU | OOOOOO
上のような場合．Xは，"|"で表される．

・パンが何種類あっても不可能な場合．

O…………
または，
…………U
の場合．

・パンの種類が2つで良い場合．

上記のどれにも当てはまらない場合．
何故なら，必ずパンの順列は，
U[…………]O
となり，
U | […………]O
で分けると，
[…………]内のOは全て排除され．
[U……U]O
となる．その後，
[U……U] | O
で分ければ終了する．

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

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

 public int bake(int[] a, int[] b) {
  Arrays.sort(a); // o
  Arrays.sort(b); // x
  boolean f=true;
  for(int j=0;j<b.length;j++){
   for(int i=0;i<a.length;i++){
    f&=a[i]<b[j];
   }
  }
  if(f){
   return 1;
  }
  else if(a[0]>b[0]||a[a.length-1]>b[b.length-1]){
   return -1;
  }
  else if(a.length>=2&&b.length>=2){
   return 2;
  }
  else{
   return -1;
  }
 }

 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) {
  ToastXToast temp = new ToastXToast();
 }
}

■Result

○×× 0 0
144.26pt.

■Rating

1243 -> 1279
若干上昇．少しずつRatingを上げていきたいものです…．

2011年4月16日土曜日

Aizu Online Judge 1212 Mirror Illusion

■1212 Mirror Illusion

ある座標pから方向vを見ていたとする．ちなみに，初期条件は，p₀=(0.75, 0.25)，v₀=(1, 1)
vのノルムを16以上にとれば，(p+v)が必ず室外に出るので，以下vをそういうベクトルとする．
まず，(p, p+v)が人に当たるかを調べる．当たっていたらそこで終了．
次に，(p, p+v)が鏡に当たるかを調べる．一つでも当たる鏡があれば，その内で交差点が最もpに近い鏡mを選ぶ．pを，(p, p+v)とmとの交差点とする．また，新しい方向ベクトルを， mが横置きだったらv'=(v_x, -v_y)，縦置きだったらv'=(-v_x, v_y)とする．
一つも当たらなかった場合は，外壁のいずれかに当たっていることになるので，4つの壁それぞれについて当たっているかおよび交差点を計算．

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;
 Seg[] segs;

 void run(){
  m=8;
  for(;;){
   n=sc.nextInt();
   if(n<0){
    break;
   }
   segs=new Seg[n];
   for(int i=0; i<n; i++){
    char c=sc.next().charAt(0);
    int x=sc.nextInt();
    int y=sc.nextInt();
    if(c=='x'){
     segs[i]=new Seg(0, x, y, x+1, y);
    }else{
     segs[i]=new Seg(1, x, y, x, y+1);
    }
   }
   solve();
  }
 }

 void solve(){
  P p0=new P(0.75, 0.25);
  P p=new P(0.75, 0.25);
  P v=new P(1, 1);
  Seg[] walls=new Seg[4];
  walls[0]=new Seg(0, 0, 0, m, 0);
  walls[1]=new Seg(0, 0, m, m, m);
  walls[2]=new Seg(0, 0, 0, 0, m);
  walls[3]=new Seg(0, m, 0, m, m);

  for(int i=0; i<10; i++){
   v=v.div(v.abs()).mul(2*m);

   if(p.sub(p0).abs()>EPS&&disSP(p, p.add(v), p0)<EPS){
    int x=(int)(p0.x*100+EPS);
    int y=(int)(p0.y*100+EPS);
    println(x+" "+y);
    break;
   }

   Seg seg=null;
   P p2=null;
   double min=INF;
   for(Seg s : segs){
    if(crsSS(p, p.add(v), s.p1, s.p2)){
     P q=isLL(p, p.add(v), s.p1, s.p2);
     double d=p.sub(q).abs();
     if(d<min+EPS&&d>EPS){
      seg=s;
      p2=q;
      min=p.sub(q).abs();
     }
    }
   }

   if(p2!=null){
    p=p2;
    if(seg.d==0){
     v.y=-v.y;
    }else{
     v.x=-v.x;
    }
   }else{
    for(Seg s : walls){
     if(crsSS(p, p.add(v), s.p1, s.p2)){
      P q=isLL(p, p.add(v), s.p1, s.p2);
      if(p.sub(q).abs()>EPS){
       int x=(int)(q.x*100+EPS);
       int y=(int)(q.y*100+EPS);
       println(x+" "+y);
      }
     }
    }
    break;
   }
  }
 }

 // 線分と点の距離
 double disSP(P p1, P p2, P q){
  if(p2.sub(p1).dot(q.sub(p1))<EPS)
   return q.sub(p1).abs();
  if(p1.sub(p2).dot(q.sub(p2))<EPS)
   return q.sub(p2).abs();
  return disLP(p1, p2, q);
 }

 // 直線と点の距離
 double disLP(P p1, P p2, P q){
  return abs(p2.sub(p1).det(q.sub(p1)))/p2.sub(p1).abs();
 }

 // 線分と線分の交差判定
 boolean crsSS(P p1, P p2, P q1, P q2){
  if(max(p1.x, p2.x)+EPS<min(q1.x, q2.x))
   return false;
  if(max(q1.x, q2.x)+EPS<min(p1.x, p2.x))
   return false;
  if(max(p1.y, p2.y)+EPS<min(q1.y, q2.y))
   return false;
  if(max(q1.y, q2.y)+EPS<min(p1.y, p2.y))
   return false;
  return signum(p2.sub(p1).det(q1.sub(p1)))
    *signum(p2.sub(p1).det(q2.sub(p1)))<EPS
    &&signum(q2.sub(q1).det(p1.sub(q1)))
      *signum(q2.sub(q1).det(p2.sub(q1)))<EPS;
 }

 // 直線と直線の交点
 P isLL(P p1, P p2, P q1, P q2){
  double d=q2.sub(q1).det(p2.sub(p1));
  if(abs(d)<EPS)
   return null;
  return p1.add(p2.sub(p1).mul(q2.sub(q1).det(q1.sub(p1))/d));
 }

 class Seg{
  int d;
  P p1, p2;

  Seg(int d, int x1, int y1, int x2, int y2){
   this.d=d;
   p1=new P(x1, y1);
   p2=new P(x2, y2);
  }
 }

 // 2 dimensions
 class P{
  double x, y;

  P(){
   this(0, 0);
  }

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

  P add(P p){
   return new P(x+p.x, y+p.y);
  }

  P sub(P p){
   return new P(x-p.x, y-p.y);
  }

  P mul(double m){
   return new P(x*m, y*m);
  }

  P div(double d){
   return new P(x/d, y/d);
  }

  double abs(){
   return Math.sqrt(abs2());
  }

  double abs2(){
   return x*x+y*y;
  }

  double arg(){
   return Math.atan2(y, x);
  }

  // inner product
  double dot(P p){
   return x*p.x+y*p.y;
  }

  // outer product
  double det(P p){
   return x*p.y-y*p.x;
  }

  P rot90(){
   return new P(-y, x);
  }

  // conjugation
  P conj(){
   return new P(x, -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 1211 Trapezoids

■1211 Trapezoids

下のような入力が与えられたとする．

*** * * ********** * * * * * * * *** * * * * * * * * * * ***** * * * * * * * ********** * * ************

まず，四角形の内部となりえない所をある値（ここでは'-'）で埋める．

-----------***--------- -----------* *-------- **********-* *------- * *-* *------ * *** *-* *----- * * * *-* *---- * ***** *-* *--- * *-* *-- **********-* *- -----------************

(i, j)が'*'となる(i, j)をラスタスキャン．輪郭をたどり，たどった点を' 'に変更する．

-----------***--------- -----------* *-------- -----------* *------- - --* *------ - *** --* *----- - * * --* *---- - ***** --* *--- - --* *-- -----------* *- -----------************

'-'のみを壁として(i, j)からBFS．この時の探索回数が領域の面積．
(i, j)からBFSで0を'-'に塗りつぶしていく

-----------***--------- -----------* *-------- -----------* *------- -----------* *------ --***------* *----- --* *-----* *---- --*****----* *--- -----------* *-- -----------* *- -----------************

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;
 int[][] a;
 int c;
 boolean[] wall;

 void run(){
  for(int k=0;; k++){
   n=sc.nextInt();
   if(n==0){
    break;
   }
   if(k>0){
    println("----------");
   }
   sc.nextLine();
   m=0;
   String[] ss=new String[n];
   for(int i=0; i<n; i++){
    ss[i]=sc.nextLine();
    m=max(m, ss[i].length());
   }
   a=new int[n][m];
   for(int j=0; j<n; j++){
    for(int i=0; i<ss[j].length(); i++){
     a[j][i]=ss[j].charAt(i)=='*'?1:0;
    }
   }
   solve();
  }
 }

 void solve(){
  c=2;
  wall=new boolean[]{false, true, true};
  for(int j=0; j<n; j++){
   if(a[j][0]==0){
    bfs(0, j);
   }
   if(a[j][m-1]==0){
    bfs(m-1, j);
   }
  }
  for(int i=0; i<m; i++){
   if(a[0][i]==0){
    bfs(i, 0);
   }
   if(a[n-1][i]==0){
    bfs(i, n-1);
   }
  }

  HashMap<Integer, Integer> map=new HashMap<Integer, Integer>();
  int[] dx={1, 1, 0, -1, -1, -1, 0, 1};
  int[] dy={0, 1, 1, 1, 0, -1, -1, -1};
  for(int j=0; j<n; j++){
   for(int i=0; i<m; i++){
    if(a[j][i]==1){
     int outline=0;
     int d=0;
     int x=i, y=j;
     for(;;){
      outline++;
      a[y][x]=0;
      boolean f=false;
      d=(d+5)%8;
      for(int k=0; k<8; k++, d=(d+1)%8){
       int x2=x+dx[d];
       int y2=y+dy[d];
       if(x2>=0&&x2<m&&y2>=0&&y2<n&&a[y2][x2]==1){
        x=x2;
        y=y2;
        f=true;
        break;
       }
      }
      if(!f){
       break;
      }
     }
     c=-1;
     wall=new boolean[]{false, false, true};
     int area=bfs(x, y);
     if(!map.containsKey(area)){
      map.put(area, 0);
     }
     map.put(area, map.get(area)+1);

     c=2;
     wall=new boolean[]{false, true, true};
     bfs(x, y);
    }
   }
  }
  Integer[] is=map.keySet().toArray(new Integer[0]);
  sort(is);
  for(int key : is){
   println(key+" "+map.get(key));
  }
 }

 int bfs(int x, int y){
  int[] dx={0, 0, -1, 1};
  int[] dy={-1, 1, 0, 0};
  LinkedList<P> que=new LinkedList<P>();
  boolean[][] visited=new boolean[n][m];
  que.add(new P(x, y));
  visited[y][x]=true;
  int res=0;
  for(; !que.isEmpty();){
   P p=que.poll();
   if(c>=0){
    a[p.y][p.x]=c;
   }
   res++;
   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<m&&q.y>=0&&q.y<n&&!visited[q.y][q.x]
      &&!wall[a[q.y][q.x]]){
     que.add(q);
     visited[q.y][q.x]=true;
    }
   }
  }
  return res;
 }

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

2011年4月5日火曜日

Aizu Online Judge 1208 Rational Irrationals

■1208 Rational Irrationals

全探索を行うと，O(n²)でかなりキツイ．そこで二部探索を使う．
具体的には，分数をm/dとした時，dを1~nまで回し，√pに近くなるようなmを求める．
探索の幅として[1,n]を設定し，m/d<√pを条件とすれば，
m/d<√p<(m+1)/d
もしくは，
m/d<(m+1)/d<√p (ただし，m+1>n)
となる．
事実上計算量はO(n)．

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

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

public class Main{

 Scanner sc=new Scanner(System.in);

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

 int p, m;

 void run(){
  for(;;){
   p=sc.nextInt();
   m=sc.nextInt();
   if((p|m)==0){
    break;
   }
   solve();
  }
 }

 void solve(){
  long n1=0, d1=1;
  long n2=m, d2=1;
  for(long d=1; d<=m; d++){
   double left=1, right=m;
   for(int i=0; i<100; i++){
    double mid=(left+right)/2;
    if(mid*mid<p*d*d+EPS){
     left=mid;
    }else{
     right=mid;
    }
   }
   int n=(int)(left+EPS);
   if(n1*d<n*d1&&n*n<p*d*d){
    n1=n;
    d1=d;
   }
   if(++n<=m){
    if(p*d*d<n*n&&n*d2<n2*d){
     n2=n;
     d2=d;
    }
   }
  }
  long gcd=gcd(n1, d1);
  n1/=gcd;
  d1/=gcd;
  gcd=gcd(n2, d2);
  n2/=gcd;
  d2/=gcd;
  println(n2+"/"+d2+" "+n1+"/"+d1);
 }

 long gcd(long m, long n){
  for(; n!=0;){
   m=m%n;
   long t=m;
   m=n;
   n=t;
  }
  return 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();
 }
}

2011年4月4日月曜日

Aizu Online Judge

■1204 Pipeline Scheduling

再帰を用いて実際にシミュレートする．左端から詰めていくようにして，簡単な枝刈り（現時点でのサイクル数が，暫定の最短より長い場合は中断）を付け加えれば通る．

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, t, u;
 int[][] a, b;
 int ans;

 void run(){
  t=10;
  u=5;
  for(;;){
   n=sc.nextInt();
   if(n==0){
    break;
   }
   a=new int[u][n];
   for(int j=0; j<u; j++){
    String s=sc.next();
    for(int i=0; i<n; i++){
     a[j][i]=s.charAt(i)=='.'?0:1;
    }
   }
   solve();
  }
 }

 void rec(int k, int p){
  if(p>=ans){
   return;
  }
  if(k==t+1){
   ans=min(ans, p+n-1);
   return;
  }
  for(int q=p; q<p+n; q++){
   boolean f=true;
   for(int j=0; j<u; j++){
    for(int i=0; i<n; i++){
     f&=a[j][i]==0||b[j][q+i]==0;
    }
   }
   if(f){
    for(int j=0; j<u; j++){
     for(int i=0; i<n; i++){
      if(a[j][i]==1){
       b[j][q+i]=k;
      }
     }
    }
    rec(k+1, q+1);
    for(int j=0; j<u; j++){
     for(int i=0; i<n; i++){
      if(a[j][i]==1){
       b[j][q+i]=0;
      }
     }
    }
   }
  }
 }

 void solve(){
  ans=INF;
  b=new int[u][(n+1)*(t+1)];
  rec(1, 0);
  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年4月3日日曜日

Aizu Online Judge 1203 Napoleon's Grumble

■1203 Napoleon's Grumble

回文の中心点jを0~n-1まで動かしながら，
c_j-i,…,c_j+i
c_j-i,…,c_j+i+1
が回文となる最大のiを探す．
片っ端から回文候補をリストに入れた後，冗長のものを省く．

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;

 String s;

 void run(){
  for(; sc.hasNextLine();){
   s=sc.nextLine();
   solve();
  }
 }

 void solve(){
  s=s.toUpperCase().replaceAll("[^A-Z]", "");
  int n=s.length();
  TreeSet<String> set=new TreeSet<String>();
  for(int j=0; j<n; j++){
   int i;
   for(i=0; j-i>=0&&j+i<n&&s.charAt(j-i)==s.charAt(j+i); i++);
   i--;
   if(i>=1){
    set.add(s.substring(j-i, j+i+1));
   }
   for(i=0; j-i>=0&&j+i+1<n&&s.charAt(j-i)==s.charAt(j+i+1); i++);
   i--;
   if(i>=1){
    set.add(s.substring(j-i, j+i+2));
   }
  }
  for(Iterator<String> i=set.iterator(); i.hasNext();){
   String s=i.next();
   for(Iterator<String> j=set.iterator(); j.hasNext();){
    String t=j.next();
    if((s.length()+t.length())%2==0&&t.length()>s.length()){
     int k=(t.length()-s.length())/2;
     if(t.substring(k, t.length()-k).equals(s)){
      i.remove();
      break;
     }
    }
   }
  }
  for(; !set.isEmpty();){
   print(set.pollFirst());
   if(!set.isEmpty()){
    print(" ");
   }
  }
  println("");
 }

 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年4月2日土曜日

Aizu Online Judge 1201 Lattice Practices

■1201 Lattice Practices

まず，10枚の板から5枚を選び，その5枚で構成出来るパターンを全て列挙．列挙の際，反転させても変わらない板がある場合があるので，重複を考慮する必要がある．それぞれのパターンに対応するパターンを残りの5枚で構成できうるかを判定する． 10個から5個選ぶ…₁₀P₅=30240 反転の種類…2⁵=32

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[] a, rev;
 int n, m;

 void run(){
  n=10;
  m=n/2;
  a=new int[n];
  rev=new int[1<<m];
  for(int i=0; i<1<<m; i++){
   int x=i;
   x=(x&0x55555555)<<1|(x>>1)&0x55555555;
   x=(x&0x33333333)<<2|(x>>2)&0x33333333;
   x=(x&0x0f0f0f0f)<<4|(x>>4)&0x0f0f0f0f;
   x=(x<<24)|((x&0xff00)<<8)|((x>>8)&0xff00)|(x>>24);
   rev[i]=(int)(x>>(32-m))&((1<<m)-1);
  }

  for(;;){
   for(int i=0; i<n; i++){
    String s=sc.next();
    if(s.equals("END")){
     return;
    }
    a[i]=Integer.parseInt(s, 2);
   }
   solve();
  }
 }

 void solve(){
  int ans=0;
  int[] b=new int[m];
  int[] c=new int[m];
  int comb=(1<<m)-1;
  boolean[] used=new boolean[m];

  for(; comb<1<<n;){
   // 2^(反転させても同じものの個数)で割る
   int div=1;
   for(int i=0, j=0, k=0; k<10; k++){
    if((comb>>k&1)==1){
     b[i++]=a[k];
     if(rev[a[k]]==a[k]){
      div*=2;
     }
    }else{
     c[j++]=a[k];
    }
   }

   Arrays.sort(b);
   int sum=0;
   for(;;){
    // 2^n通り反転させる
    for(int sup=0; sup<1<<m; sup++){
     for(int i=0; i<m; i++){
      if((sup>>i&1)==1){
       b[i]=rev[b[i]];
      }
     }
     // bの並びをcで構築できるか
     Arrays.fill(used, false);
     sum++;
     for(int i=0; i<m; i++){
      int bits=0;
      for(int j=0; j<m; j++){
       bits=(bits<<1)|(b[j]>>i&1);
      }
      int k=-1;
      for(int j=0; j<m; j++){
       if(!used[j]
         &&((c[j]^bits)==(1<<m)-1||(rev[c[j]]^bits)==(1<<m)-1)){
        k=j;
       }
      }
      if(k>=0){
       used[k]=true;
      }else{
       sum--;
       break;
      }
     }
     for(int i=0; i<m; i++){
      if((sup>>i&1)==1){
       b[i]=rev[b[i]];
      }
     }
    }
    if(!nextPermutation(b)){
     break;
    }
   }
   ans+=sum/div;

   int x=comb&-comb, y=comb+x;
   comb=((comb&~y)/x>>1)|y;
  }
  ans/=8; // 鏡像反転*回転
  println(""+ans);
 }

 boolean nextPermutation(int[] is){
  int n=is.length;
  for(int i=n-1; i>0; i--){
   if(is[i-1]<is[i]){
    int j=n;
    while(is[i-1]>=is[--j]);
    swap(is, i-1, j);
    rev(is, i, n);
    return true;
   }
  }
  rev(is, 0, n);
  return false;
 }

 void swap(int[] is, int i, int j){
  int t=is[i];
  is[i]=is[j];
  is[j]=t;
 }

 void rev(int[] is, int i, int j){
  for(j--; i<j; i++, j--){
   int t=is[i];
   is[i]=is[j];
   is[j]=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();
 }
}

SRM	Easy	Normal	Hard
295	o	-	-
296	o	-	-
297	o	-	-
298	o	-	-
350	o	-	-
386	o	-	-
447	o	-	-
451	o	-	-
462	o	-	-
463	o	-	-
464	o	-	-
465	o	-	-
466	o	-	-
469	o	-	-
471	o	-	-
472	o	-	-
473	o	-	-
474	o	-	-
475	o	-	-
476	o	-	-
477	o	-	-
478	o	-	-
479	o	-	-
480	o	-	-
481	o	-	-
482	o	o	-
483	o	-	-
484	o	-	-
485	o	-	-
486	o	-	-
487	o	-	-
503	-	o	-
511	-	o	-

1	hello world	30B
2	echo	31B
3	99 shinichiroes of hamaji	258B
4	example com	451B
5	Smileys Triangle	63B
8	delete blank lines	37B
14	ultimate problem	19B
16	even lines	40B
19	Fibonacci Numbers	46B
34	FizzBuzz	84B
48	google	67B

2011年4月30日土曜日

2011年4月21日木曜日

2011年4月20日水曜日

2011年4月19日火曜日

2011年4月18日月曜日

2011年4月17日日曜日

2011年4月16日土曜日

2011年4月5日火曜日

2011年4月4日月曜日

2011年4月3日日曜日

2011年4月2日土曜日

Label

Blog Archive

Self Introduction

Link

Project Euler

Single Round Match Div1 Practice

anarchy golf

Books

CD/DVD

2011年の目標

買う

Memo