ACM/ICPC国内予選 コード

汚いけどコード晒しあげ．

A

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

public class A{
 Scanner sc;
 PrintWriter pw, db;

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

 void run(){
  init();
  for(;;){
   int m=sc.nextInt();
   if(m==0)
    break;
   P[] ps=new P[m];
   ps[0]=new P(0, 0);
   for(int i=1; i<m; i++){
    int n=sc.nextInt();
    int d=sc.nextInt();
    ps[i]=new P(ps[n].x+dx[d], ps[n].y+dy[d]);
   }
   int xmin=0, xmax=0;
   int ymin=0, ymax=0;
   for(P p : ps){
    xmin=min(xmin, p.x);
    xmax=max(xmax, p.x);
    ymin=min(ymin, p.y);
    ymax=max(ymax, p.y);
   }
   int w=xmax-xmin+1;
   int h=ymax-ymin+1;
   db.println(w+" "+h);
   pw.println(w+" "+h);
  }
  close();
 }

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

 void init(){
  try{
   sc=new Scanner(new FileInputStream("A"));
   pw=new PrintWriter("A.out");
   db=new PrintWriter(System.out);
  }catch(IOException e){}
 }

 void close(){
  sc.close();
  pw.close();
  db.close();
 }

 static class P{
  int x, y;

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

}

B

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

public class B{
 Scanner sc;
 PrintWriter pw, db;

 int w, h;
 int[][] right, down;

 void run(){
  init();
  for(;;){
   w=sc.nextInt();
   h=sc.nextInt();
   if(w==0&&h==0)
    break;
   right=new int[h][w-1];
   down=new int[h-1][w];
   for(int k=0; k<h-1; k++){
    for(int i=0; i<w-1; i++)
     right[k][i]=sc.nextInt();
    for(int i=0; i<w; i++)
     down[k][i]=sc.nextInt();
   }
   for(int i=0; i<w-1; i++)
    right[h-1][i]=sc.nextInt();
   bfs();
  }
  close();
 }

 void bfs(){
  int[][] map=new int[h][w];
  LinkedList<P> q=new LinkedList<P>();
  P s=new P(0, 0);
  map[0][0]=1;
  q.addLast(s);
  while(!q.isEmpty()){
   P p=q.removeFirst();
   int x=p.x, y=p.y;
   int d=map[p.y][p.x];

   // up
   int nx=x;
   int ny=y-1;
   if(ny>=0&&down[y-1][x]==0&&map[ny][nx]==0){
    map[ny][nx]=d+1;
    q.addLast(new P(nx, ny));
   }

   // down
   nx=x;
   ny=y+1;
   if(ny<h&&down[y][x]==0&&map[ny][nx]==0){
    map[ny][nx]=d+1;
    q.addLast(new P(nx, ny));
   }

   // left
   nx=x-1;
   ny=y;
   if(nx>=0&&right[y][x-1]==0&&map[ny][nx]==0){
    map[ny][nx]=d+1;
    q.addLast(new P(nx, ny));
   }

   // right
   nx=x+1;
   ny=y;
   if(nx<w&&right[y][x]==0&&map[ny][nx]==0){
    map[ny][nx]=d+1;
    q.addLast(new P(nx, ny));
   }
  }
  db.println(map[h-1][w-1]);
  pw.println(map[h-1][w-1]);
 }

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

 void init(){
  try{
   sc=new Scanner(new FileInputStream("B"));
   pw=new PrintWriter("B.out");
   db=new PrintWriter(System.out);
  }catch(IOException e){}
 }

 void close(){
  sc.close();
  pw.close();
  db.close();
 }

 static class P{
  int x, y;

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

}

C

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

public class C{
 Scanner sc;
 PrintWriter pw, db;

 LinkedList<Integer> list1, list2;
 int[] dp1;

 static final int INF=1>>28;

 void run(){
  init();
  f();
  for(;;){
   int n=sc.nextInt();
   if(n==0)
    break;
   int a1=dp1[n];
   int a2=cal(n);
   db.println(a1+" "+a2);
   pw.println(a1+" "+a2);
  }
  close();
 }

 void f(){
  int n=1000000;

  list1=new LinkedList<Integer>();
  list2=new LinkedList<Integer>();
  for(int i=1;; i++){
   int t=i*(i+1)*(i+2)/6;
   if(t>n)
    break;
   list1.add(t);
   if(t%2==1)
    list2.add(t);
  }

  // 予め計算しておく
  dp1=new int[n+1];
  Arrays.fill(dp1, INF);
  dp1[0]=0;
  for(int j=1; j<=5; j++){
   for(int i=0; i<n; i++){
    if(dp1[i]!=j-1)
     continue;
    for(int k : list1){
     if(i+k<=n)
      dp1[i+k]=min(dp1[i+k], j);
    }
   }
  }
 }

 int cal(int n){
  int[] dp=new int[n+1];
  Arrays.fill(dp, INF);
  dp[0]=0;
  for(int j=1;; j++){
   for(int i=0; i<n; i++){
    if(dp[i]!=j-1)
     continue;
    for(int k : list2){
     if(i+k==n)
      return j;
     if(i+k<n)
      dp[i+k]=min(dp[i+k], j);
    }
   }
  }
 }

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

 void init(){
  try{
   sc=new Scanner(new FileInputStream("C"));
   pw=new PrintWriter("C.out");
   db=new PrintWriter(System.out);
  }catch(IOException e){}
 }

 void close(){
  sc.close();
  pw.close();
  db.close();
 }

}

D

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

public class D{
 Scanner sc;
 PrintWriter pw, db;

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

 int w, h;
 int[][] field;

 int n;
 B[] bs;
 B root;

 boolean stable;

 boolean[][] visited;

 void run(){
  init();
  for(;;){
   w=sc.nextInt();
   h=sc.nextInt();
   sc.nextLine();
   if(w==0&&h==0)
    break;
   field=new int[h][w];
   for(int j=0; j<h; j++){
    String s=sc.nextLine();
    for(int i=0; i<w; i++){
     char c=s.charAt(i);
     if(c=='.')
      field[j][i]=-1;
     else
      field[j][i]=Integer.parseInt(""+c);
    }
   }
   identify();
   bs=new B[n];
   for(int i=0; i<n; i++)
    bs[i]=new B();
   genG();
   genTree();
   stable=true;
   dfs(root);
   db.println(stable?"STABLE":"UNSTABLE");
   pw.println(stable?"STABLE":"UNSTABLE");
  }
  close();
 }

 // id付け
 void identify(){
  n=0;
  visited=new boolean[h][w];
  for(int j=0; j<h; j++){
   for(int i=0; i<w; i++){
    if(!visited[j][i]&&field[j][i]!=-1){
     search(i, j, field[j][i]);
     n++;
    }
   }
  }
 }

 void search(int x, int y, int i){
  if(x<0||x>=w||y<0||y>=h)
   return;
  if(visited[y][x])
   return;
  if(field[y][x]!=i)
   return;
  visited[y][x]=true;
  search(x-1, y, i);
  search(x+1, y, i);
  search(x, y-1, i);
  search(x, y+1, i);
  field[y][x]=n;
 }

 // 重心の生成
 void genG(){
  LinkedList<Double>[] lists=new LinkedList[n];
  for(int i=0; i<n; i++)
   lists[i]=new LinkedList<Double>();

  for(int j=0; j<h; j++)
   for(int i=0; i<w; i++)
    if(field[j][i]!=-1)
     lists[field[j][i]].add(i+0.5);
  for(int i=0; i<n; i++){
   double sumx=0;
   for(double x : lists[i])
    sumx+=x;
   bs[i].g=sumx/4;
  }
 }

 // 木の生成，接地面のx座標の計算，根の決定
 void genTree(){
  for(int j=0; j<h-1; j++){
   for(int i=0; i<w; i++){
    int f1=field[j][i];
    int f2=field[j+1][i];
    if(f1==-1||f2==-1||f1==f2)
     continue;
    B b1=bs[f1];
    B b2=bs[f2];
    b1.left=min(b1.left, i);
    b1.right=max(b1.right, i+1);
    if(!b2.children.contains(b1))
     b2.children.add(b1);
   }
  }
  root=null;
  for(int i=0; i<w; i++){
   int id=field[h-1][i];
   if(field[h-1][i]!=-1){
    root=bs[id];
    root.left=min(root.left, i);
    root.right=max(root.right, i+1);
   }
  }
 }

 void dfs(B rt){
  if(!stable)
   return;
  if(rt==null)
   return;
  double mass=0;
  double mg=0;
  for(B b : rt.children){
   dfs(b);
   mass+=b.mass;
   mg+=b.mass*b.g;
  }
  // マージ
  rt.g=(mg+rt.mass*rt.g)/(mass+rt.mass);
  rt.mass+=mass;

  if(rt.g>rt.left+EPS&&rt.g+EPS<rt.right)
   ;
  else
   stable=false;
 }

 class B{
  LinkedList<B> children;
  double left, right;
  double g;
  double mass;

  B(){
   children=new LinkedList<B>();
   left=INF;
   right=-INF;
   mass=1;
  }
 }

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

 void init(){
  try{
   sc=new Scanner(new FileInputStream("D"));
   pw=new PrintWriter("D.out");
   db=new PrintWriter(System.out);
  }catch(IOException e){}
 }

 void close(){
  sc.close();
  pw.close();
  db.close();
 }

}