ACM/ICPC国内予選 コード

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

A

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.io.*;  
4. import static java.lang.Math.*;  
5. import static java.util.Arrays.*;  
6.   
7. public class A{  
8.  Scanner sc;  
9.  PrintWriter pw, db;  
10.   
11.  int[] dx={-1, 0, 1, 0};  
12.  int[] dy={0, 1, 0, -1};  
13.   
14.  void run(){  
15.   init();  
16.   for(;;){  
17.    int m=sc.nextInt();  
18.    if(m==0)  
19.     break;  
20.    P[] ps=new P[m];  
21.    ps[0]=new P(0, 0);  
22.    for(int i=1; i<m; i++){  
23.     int n=sc.nextInt();  
24.     int d=sc.nextInt();  
25.     ps[i]=new P(ps[n].x+dx[d], ps[n].y+dy[d]);  
26.    }  
27.    int xmin=0, xmax=0;  
28.    int ymin=0, ymax=0;  
29.    for(P p : ps){  
30.     xmin=min(xmin, p.x);  
31.     xmax=max(xmax, p.x);  
32.     ymin=min(ymin, p.y);  
33.     ymax=max(ymax, p.y);  
34.    }  
35.    int w=xmax-xmin+1;  
36.    int h=ymax-ymin+1;  
37.    db.println(w+" "+h);  
38.    pw.println(w+" "+h);  
39.   }  
40.   close();  
41.  }  
42.   
43.  public static void main(String[] args){  
44.   new A().run();  
45.  }  
46.   
47.  void init(){  
48.   try{  
49.    sc=new Scanner(new FileInputStream("A"));  
50.    pw=new PrintWriter("A.out");  
51.    db=new PrintWriter(System.out);  
52.   }catch(IOException e){}  
53.  }  
54.   
55.  void close(){  
56.   sc.close();  
57.   pw.close();  
58.   db.close();  
59.  }  
60.   
61.  static class P{  
62.   int x, y;  
63.   
64.   P(int x, int y){  
65.    this.x=x;  
66.    this.y=y;  
67.   }  
68.  }  
69.   
70. }  

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

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.io.*;  
4. import static java.lang.Math.*;  
5. import static java.util.Arrays.*;  
6.   
7. public class B{  
8.  Scanner sc;  
9.  PrintWriter pw, db;  
10.   
11.  int w, h;  
12.  int[][] right, down;  
13.   
14.  void run(){  
15.   init();  
16.   for(;;){  
17.    w=sc.nextInt();  
18.    h=sc.nextInt();  
19.    if(w==0&&h==0)  
20.     break;  
21.    right=new int[h][w-1];  
22.    down=new int[h-1][w];  
23.    for(int k=0; k<h-1; k++){  
24.     for(int i=0; i<w-1; i++)  
25.      right[k][i]=sc.nextInt();  
26.     for(int i=0; i<w; i++)  
27.      down[k][i]=sc.nextInt();  
28.    }  
29.    for(int i=0; i<w-1; i++)  
30.     right[h-1][i]=sc.nextInt();  
31.    bfs();  
32.   }  
33.   close();  
34.  }  
35.   
36.  void bfs(){  
37.   int[][] map=new int[h][w];  
38.   LinkedList<P> q=new LinkedList<P>();  
39.   P s=new P(0, 0);  
40.   map[0][0]=1;  
41.   q.addLast(s);  
42.   while(!q.isEmpty()){  
43.    P p=q.removeFirst();  
44.    int x=p.x, y=p.y;  
45.    int d=map[p.y][p.x];  
46.   
47.    // up  
48.    int nx=x;  
49.    int ny=y-1;  
50.    if(ny>=0&&down[y-1][x]==0&&map[ny][nx]==0){  
51.     map[ny][nx]=d+1;  
52.     q.addLast(new P(nx, ny));  
53.    }  
54.   
55.    // down  
56.    nx=x;  
57.    ny=y+1;  
58.    if(ny<h&&down[y][x]==0&&map[ny][nx]==0){  
59.     map[ny][nx]=d+1;  
60.     q.addLast(new P(nx, ny));  
61.    }  
62.   
63.    // left  
64.    nx=x-1;  
65.    ny=y;  
66.    if(nx>=0&&right[y][x-1]==0&&map[ny][nx]==0){  
67.     map[ny][nx]=d+1;  
68.     q.addLast(new P(nx, ny));  
69.    }  
70.   
71.    // right  
72.    nx=x+1;  
73.    ny=y;  
74.    if(nx<w&&right[y][x]==0&&map[ny][nx]==0){  
75.     map[ny][nx]=d+1;  
76.     q.addLast(new P(nx, ny));  
77.    }  
78.   }  
79.   db.println(map[h-1][w-1]);  
80.   pw.println(map[h-1][w-1]);  
81.  }  
82.   
83.  public static void main(String[] args){  
84.   new B().run();  
85.  }  
86.   
87.  void init(){  
88.   try{  
89.    sc=new Scanner(new FileInputStream("B"));  
90.    pw=new PrintWriter("B.out");  
91.    db=new PrintWriter(System.out);  
92.   }catch(IOException e){}  
93.  }  
94.   
95.  void close(){  
96.   sc.close();  
97.   pw.close();  
98.   db.close();  
99.  }  
100.   
101.  static class P{  
102.   int x, y;  
103.   
104.   P(int x, int y){  
105.    this.x=x;  
106.    this.y=y;  
107.   }  
108.  }  
109.   
110. }  

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

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.io.*;  
4. import static java.lang.Math.*;  
5. import static java.util.Arrays.*;  
6.   
7. public class C{  
8.  Scanner sc;  
9.  PrintWriter pw, db;  
10.   
11.  LinkedList<Integer> list1, list2;  
12.  int[] dp1;  
13.   
14.  static final int INF=1>>28;  
15.   
16.  void run(){  
17.   init();  
18.   f();  
19.   for(;;){  
20.    int n=sc.nextInt();  
21.    if(n==0)  
22.     break;  
23.    int a1=dp1[n];  
24.    int a2=cal(n);  
25.    db.println(a1+" "+a2);  
26.    pw.println(a1+" "+a2);  
27.   }  
28.   close();  
29.  }  
30.   
31.  void f(){  
32.   int n=1000000;  
33.   
34.   list1=new LinkedList<Integer>();  
35.   list2=new LinkedList<Integer>();  
36.   for(int i=1;; i++){  
37.    int t=i*(i+1)*(i+2)/6;  
38.    if(t>n)  
39.     break;  
40.    list1.add(t);  
41.    if(t%2==1)  
42.     list2.add(t);  
43.   }  
44.   
45.   // 予め計算しておく  
46.   dp1=new int[n+1];  
47.   Arrays.fill(dp1, INF);  
48.   dp1[0]=0;  
49.   for(int j=1; j<=5; j++){  
50.    for(int i=0; i<n; i++){  
51.     if(dp1[i]!=j-1)  
52.      continue;  
53.     for(int k : list1){  
54.      if(i+k<=n)  
55.       dp1[i+k]=min(dp1[i+k], j);  
56.     }  
57.    }  
58.   }  
59.  }  
60.   
61.  int cal(int n){  
62.   int[] dp=new int[n+1];  
63.   Arrays.fill(dp, INF);  
64.   dp[0]=0;  
65.   for(int j=1;; j++){  
66.    for(int i=0; i<n; i++){  
67.     if(dp[i]!=j-1)  
68.      continue;  
69.     for(int k : list2){  
70.      if(i+k==n)  
71.       return j;  
72.      if(i+k<n)  
73.       dp[i+k]=min(dp[i+k], j);  
74.     }  
75.    }  
76.   }  
77.  }  
78.   
79.  public static void main(String[] args){  
80.   new C().run();  
81.  }  
82.   
83.  void init(){  
84.   try{  
85.    sc=new Scanner(new FileInputStream("C"));  
86.    pw=new PrintWriter("C.out");  
87.    db=new PrintWriter(System.out);  
88.   }catch(IOException e){}  
89.  }  
90.   
91.  void close(){  
92.   sc.close();  
93.   pw.close();  
94.   db.close();  
95.  }  
96.   
97. }  

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

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.io.*;  
4. import static java.lang.Math.*;  
5. import static java.util.Arrays.*;  
6.   
7. public class D{  
8.  Scanner sc;  
9.  PrintWriter pw, db;  
10.   
11.  static final int INF=1<<28;  
12.  static final double EPS=1e-6;  
13.   
14.  int w, h;  
15.  int[][] field;  
16.   
17.  int n;  
18.  B[] bs;  
19.  B root;  
20.   
21.  boolean stable;  
22.   
23.  boolean[][] visited;  
24.   
25.  void run(){  
26.   init();  
27.   for(;;){  
28.    w=sc.nextInt();  
29.    h=sc.nextInt();  
30.    sc.nextLine();  
31.    if(w==0&&h==0)  
32.     break;  
33.    field=new int[h][w];  
34.    for(int j=0; j<h; j++){  
35.     String s=sc.nextLine();  
36.     for(int i=0; i<w; i++){  
37.      char c=s.charAt(i);  
38.      if(c=='.')  
39.       field[j][i]=-1;  
40.      else  
41.       field[j][i]=Integer.parseInt(""+c);  
42.     }  
43.    }  
44.    identify();  
45.    bs=new B[n];  
46.    for(int i=0; i<n; i++)  
47.     bs[i]=new B();  
48.    genG();  
49.    genTree();  
50.    stable=true;  
51.    dfs(root);  
52.    db.println(stable?"STABLE":"UNSTABLE");  
53.    pw.println(stable?"STABLE":"UNSTABLE");  
54.   }  
55.   close();  
56.  }  
57.   
58.  // id付け  
59.  void identify(){  
60.   n=0;  
61.   visited=new boolean[h][w];  
62.   for(int j=0; j<h; j++){  
63.    for(int i=0; i<w; i++){  
64.     if(!visited[j][i]&&field[j][i]!=-1){  
65.      search(i, j, field[j][i]);  
66.      n++;  
67.     }  
68.    }  
69.   }  
70.  }  
71.   
72.  void search(int x, int y, int i){  
73.   if(x<0||x>=w||y<0||y>=h)  
74.    return;  
75.   if(visited[y][x])  
76.    return;  
77.   if(field[y][x]!=i)  
78.    return;  
79.   visited[y][x]=true;  
80.   search(x-1, y, i);  
81.   search(x+1, y, i);  
82.   search(x, y-1, i);  
83.   search(x, y+1, i);  
84.   field[y][x]=n;  
85.  }  
86.   
87.  // 重心の生成  
88.  void genG(){  
89.   LinkedList<Double>[] lists=new LinkedList[n];  
90.   for(int i=0; i<n; i++)  
91.    lists[i]=new LinkedList<Double>();  
92.   
93.   for(int j=0; j<h; j++)  
94.    for(int i=0; i<w; i++)  
95.     if(field[j][i]!=-1)  
96.      lists[field[j][i]].add(i+0.5);  
97.   for(int i=0; i<n; i++){  
98.    double sumx=0;  
99.    for(double x : lists[i])  
100.     sumx+=x;  
101.    bs[i].g=sumx/4;  
102.   }  
103.  }  
104.   
105.  // 木の生成，接地面のx座標の計算，根の決定  
106.  void genTree(){  
107.   for(int j=0; j<h-1; j++){  
108.    for(int i=0; i<w; i++){  
109.     int f1=field[j][i];  
110.     int f2=field[j+1][i];  
111.     if(f1==-1||f2==-1||f1==f2)  
112.      continue;  
113.     B b1=bs[f1];  
114.     B b2=bs[f2];  
115.     b1.left=min(b1.left, i);  
116.     b1.right=max(b1.right, i+1);  
117.     if(!b2.children.contains(b1))  
118.      b2.children.add(b1);  
119.    }  
120.   }  
121.   root=null;  
122.   for(int i=0; i<w; i++){  
123.    int id=field[h-1][i];  
124.    if(field[h-1][i]!=-1){  
125.     root=bs[id];  
126.     root.left=min(root.left, i);  
127.     root.right=max(root.right, i+1);  
128.    }  
129.   }  
130.  }  
131.   
132.  void dfs(B rt){  
133.   if(!stable)  
134.    return;  
135.   if(rt==null)  
136.    return;  
137.   double mass=0;  
138.   double mg=0;  
139.   for(B b : rt.children){  
140.    dfs(b);  
141.    mass+=b.mass;  
142.    mg+=b.mass*b.g;  
143.   }  
144.   // マージ  
145.   rt.g=(mg+rt.mass*rt.g)/(mass+rt.mass);  
146.   rt.mass+=mass;  
147.   
148.   if(rt.g>rt.left+EPS&&rt.g+EPS<rt.right)  
149.    ;  
150.   else  
151.    stable=false;  
152.  }  
153.   
154.  class B{  
155.   LinkedList<B> children;  
156.   double left, right;  
157.   double g;  
158.   double mass;  
159.   
160.   B(){  
161.    children=new LinkedList<B>();  
162.    left=INF;  
163.    right=-INF;  
164.    mass=1;  
165.   }  
166.  }  
167.   
168.  public static void main(String[] args){  
169.   new D().run();  
170.  }  
171.   
172.  void init(){  
173.   try{  
174.    sc=new Scanner(new FileInputStream("D"));  
175.    pw=new PrintWriter("D.out");  
176.    db=new PrintWriter(System.out);  
177.   }catch(IOException e){}  
178.  }  
179.   
180.  void close(){  
181.   sc.close();  
182.   pw.close();  
183.   db.close();  
184.  }  
185.   
186. }  

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

}