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)

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

x2+√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は,パンを焼いたが,mi分焼いてunder toastedだったもの,また,ni分焼いて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を見ていたとする.ちなみに,初期条件は,p0=(0.75, 0.25),v0=(1, 1)
vのノルムを16以上にとれば,(p+v)が必ず室外に出るので,以下vをそういうベクトルとする.
まず,(p, p+v)が人に当たるかを調べる.当たっていたらそこで終了.
次に,(p, p+v)が鏡に当たるかを調べる. 一つでも当たる鏡があれば,その内で交差点が最もpに近い鏡mを選ぶ.pを,(p, p+v)とmとの交差点とする.また,新しい方向ベクトルを, mが横置きだったらv'=(vx, -vy), 縦置きだったらv'=(-vx, vy)とする.
一つも当たらなかった場合は,外壁のいずれかに当たっていることになるので,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(n2)でかなりキツイ.そこで二部探索を使う.
具体的には,分数を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まで動かしながら,
cj-i,…,cj+i
cj-i,…,cj+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個選ぶ…10P5=30240 反転の種類…25=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();
 }
}