Aizu Online Judge 1149 Cut the Cakes

■1149 Cut the Cakes

やればできる．

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

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

public class Main{

 Scanner sc=new Scanner(System.in);

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

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

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

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

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

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

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

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

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

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

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

Aizu Online Judge 1131 Unit Fraction Partition

■1131 Unit Fraction Partition

自明な+ちょっと工夫した枝刈りでAC．

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

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

public class Main{

 Scanner sc=new Scanner(System.in);

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

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

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

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

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

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

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

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

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

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

Aizu Online Judge 1156 Twirling Robot

■1156 Twirling Robot

(x座標，y座標，方向ベクトル)を状態としたDijkstra．コストのつけ方が特殊だが，少し注意すれば特に問題無い．

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

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

public class Main{

 Scanner sc=new Scanner(System.in);

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

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

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

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

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

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

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

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

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

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

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

Aizu Online Judge 1136 Polygonal Line Search

■1136 Polygonal Line Search

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

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

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

public class Main{

 Scanner sc=new Scanner(System.in);

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

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

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

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

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

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

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

  return f1||f2;
 }

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

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

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

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

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

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

構文解析ゲー．変数への数の割り当て方は高々27通りなので，全部試せば良い．

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

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

// AC
public class Main{

 Scanner sc=new Scanner(System.in);

 String s;
 int[] map;

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

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

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

 class Result{
  int p, value;

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

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

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

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

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

Aizu Online Judge 1244 Molecular Formula

■1244 Molecular Formula

構文解析ゲー．

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

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

// AC
public class Main{

 Scanner sc=new Scanner(System.in);

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

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

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

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

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

 class Result{
  int p, value;

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

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

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

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

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

Aizu Online Judge 1012 Operations with Finite Sets

■1012 Operations with Finite Sets

構文解析ゲー．

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

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

// AC
public class Main{

 Scanner sc=new Scanner(System.in);

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

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

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

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

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

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

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

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

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

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

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

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

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

Aizu Online Judge 1162 Discrete Speed

■1162 Discrete Speed

拡張ダイクストラ．

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

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

// AC
public class Main{

 Scanner sc=new Scanner(System.in);

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

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

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

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

 class E{
  int to, d, c;

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

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

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

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

 }

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

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

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

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

Aizu Online Judge 1161 Verbal Arithmetic

■1161 Verbal Arithmetic

非常に汚い探索による解法．

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

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

// AC
public class Main{

 Scanner sc=new Scanner(System.in);

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

 int n;
 String[] ss;

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

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

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

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

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

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

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

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

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

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

Aizu Online Judge 1133 Water Tank

■1133 Water Tank

実装ゲー．

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

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

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

// AC
public class Main{

 Scanner sc=new Scanner(System.in);

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

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

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

 double[] y, a;
 double time;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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