TopCoder SRM 483

SRM 483(9/26 1:00~3:00)

今回は，Easyを出来るだけ正確かつ早く解く事を目標としました．

■BestApproximationDiv1(Div1 Easy)

□問題
"0.dddddd"という形の小数numberが与えられる．分母がmaxDen以下の分数d/nとnumberを比較し，小数点以下何桁目まで一致しているかを数える．一致桁数が最も大きい分数を求めよ．但し，答えが複数存在する場合には，分母が小さいものを，分母が等しい場合は，分子の小さいものを出力せよ．

□解法
全探索するとO(maxDen²)となりますが，1≦maxDen≦1000ですので問題ありませんでした．

□コード

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3.   
4. public class BestApproximationDiv1{  
5.     public String findFraction(int maxDen, String number){  
6.         int bestD=1, bestN=0;  
7.         int maxDigit=0;  
8.         for(int d=maxDen;d>=1;d--){  
9.             for(int n=d-1;n>=0;n--){  
10.                 String s=((double)n/d)+"";  
11.                 if(s.length()==1)  
12.                     s+=".";  
13.                 s+="000000";  
14.                 int digit=1;  
15.                 for(int i=2;i<number.length()&&i<s.length();i++){  
16.                     if(number.charAt(i)!=s.charAt(i))  
17.                         break;  
18.                     digit++;  
19.                 }  
20.                 if(digit>=maxDigit){  
21.                     bestD=d;  
22.                     bestN=n;  
23.                     maxDigit=digit;  
24.                 }  
25.             }  
26.         }  
27.         return bestN+"/"+bestD+" has "+maxDigit+" exact digits";  
28.     }  
29. }  

import java.util.*;
import java.lang.*;

public class BestApproximationDiv1{
    public String findFraction(int maxDen, String number){
        int bestD=1, bestN=0;
        int maxDigit=0;
        for(int d=maxDen;d>=1;d--){
            for(int n=d-1;n>=0;n--){
                String s=((double)n/d)+"";
                if(s.length()==1)
                    s+=".";
                s+="000000";
                int digit=1;
                for(int i=2;i<number.length()&&i<s.length();i++){
                    if(number.charAt(i)!=s.charAt(i))
                        break;
                    digit++;
                }
                if(digit>=maxDigit){
                    bestD=d;
                    bestN=n;
                    maxDigit=digit;
                }
            }
        }
        return bestN+"/"+bestD+" has "+maxDigit+" exact digits";
    }
}

■Challenge
他の人達の回答が結構長くて，読めませんでした．

■Result
○×× 0 -0
190.00p

今回は，HardがMediumよりも簡単という噂が聞こえてきて，Hardを解かなかった事を後悔していましたが，意外や意外，実は難しい問題だったようで，多くの人がSystem Testで落とされていました．

■Rating
1372 -> 1463

結構上がりました．4回連続Rating上昇です．目標のYellowCoderまであと少し…．

Codeforces Beta Round #30

Codeforces Beta Round #30 9/25(0:00~2:00)

1週間振り．

■A. Accounting
□問題
3つの整数A,B,n(|A|,|B|≦1000, 1≦n≦10)が与えられる．
AXⁿ=Bとなる整数Xが存在するか判定し，存在する場合はその内の1つの解を求めよ．

□解法
場合分けをきっちりやればOK．

□コード

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5. import static java.lang.Math.*;  
6. import static java.util.Arrays.*;  
7.   
8. public class A{  
9.     Scanner sc=new Scanner(System.in);  
10.   
11.     void run(){  
12.         int a=sc.nextInt();  
13.         int b=sc.nextInt();  
14.         int n=sc.nextInt();  
15.         if(a*b>0){  
16.             a=Math.abs(a);  
17.             b=Math.abs(b);  
18.             for(int x=1;; x++){  
19.                 int c=a*(int)Math.pow(x, n);  
20.                 if(c==b){  
21.                     println(""+x);  
22.                     break;  
23.                 }else if(c>b){  
24.                     println("No solution");  
25.                     break;  
26.                 }  
27.             }  
28.         }else if(a*b<0){  
29.             if(n%2==0){  
30.                 println("No solution");  
31.                 return;  
32.             }  
33.             a=Math.abs(a);  
34.             b=Math.abs(b);  
35.             for(int x=1;; x++){  
36.                 int c=a*(int)Math.pow(x, n);  
37.                 if(c==b){  
38.                     println("-"+x);  
39.                     break;  
40.                 }else if(c>b){  
41.                     println("No solution");  
42.                     break;  
43.                 }  
44.             }  
45.         }else{  
46.             if(a==0&&b==0){  
47.                 println("1");  
48.             }else if(a==0){  
49.                 println("No solution");  
50.             }else{  
51.                 println("0");  
52.             }  
53.         }  
54.     }  
55.   
56.     void println(String s){  
57.         System.out.println(s);  
58.     }  
59.   
60.     void print(String s){  
61.         System.out.print(s);  
62.     }  
63.   
64.     public static void main(String[] args){  
65.         new A().run();  
66.     }  
67. }  

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

    void run(){
        int a=sc.nextInt();
        int b=sc.nextInt();
        int n=sc.nextInt();
        if(a*b>0){
            a=Math.abs(a);
            b=Math.abs(b);
            for(int x=1;; x++){
                int c=a*(int)Math.pow(x, n);
                if(c==b){
                    println(""+x);
                    break;
                }else if(c>b){
                    println("No solution");
                    break;
                }
            }
        }else if(a*b<0){
            if(n%2==0){
                println("No solution");
                return;
            }
            a=Math.abs(a);
            b=Math.abs(b);
            for(int x=1;; x++){
                int c=a*(int)Math.pow(x, n);
                if(c==b){
                    println("-"+x);
                    break;
                }else if(c>b){
                    println("No solution");
                    break;
                }
            }
        }else{
            if(a==0&&b==0){
                println("1");
            }else if(a==0){
                println("No solution");
            }else{
                println("0");
            }
        }
    }

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

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

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

■B. Codeforces World Finals
□問題
Bobの生年月日(BD.BM.BY)とコンテストの開催年月日(DD.MM.YY)が与えられる．コンテストの開催年月日にはBobが18才以上となっているようにBobの生年月日を並び替える(BD，BM，BYをそれぞれ並び替える)ことは出来るか．

□解法
6通り全ての並び替えに対し，それが生年月日であるか+18才以上になるかという条件チェックをちゃんとやったつもりでしたが，堕ちました．

□コード
自主規制

■C. Shooting Gallery
□問題
n個のターゲットがある．ターゲットiはそれぞれ座標(x_i, y_i)，出現時刻t_i，命中率p_iを持つ．プレイヤーは，任意の位置からスタートできるが，座標c_iからc_jへ移動するのには，|c_j-c_i|だけの時間がかかる．最適な行動をとった時，ターゲットの破壊個数の期待値は最大いくらになるか．

□解法
まず，t_iでソートします．ターゲットiを破壊し最適な行動をとった時の最大期待値E_iは，
E_i=p_i+MAX_{j(tj-ti≧|cj-ci|)}E_j
となります．
ですので，t_iが大きいものからE_iを求めていき，全て求め終わった後，最も大きいE_iが答えとなります．

□コード

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5. import static java.lang.Math.*;  
6. import static java.util.Arrays.*;  
7.   
8. public class C{  
9.     Scanner sc=new Scanner(System.in);  
10.   
11.     int n;  
12.     R[] rs;  
13.   
14.     double EPS=1e-6;  
15.   
16.     void run(){  
17.         n=sc.nextInt();  
18.         rs=new R[n];  
19.         for(int i=0; i<n; i++){  
20.             R r=new R();  
21.             r.x=sc.nextInt();  
22.             r.y=sc.nextInt();  
23.             r.t=sc.nextInt();  
24.             r.p=sc.nextDouble();  
25.             rs[i]=r;  
26.         }  
27.         Arrays.sort(rs, new Comparator<R>(){  
28.             @Override  
29.             public int compare(R r1, R r2){  
30.                 return r2.t-r1.t;  
31.             }  
32.         });  
33.         for(int j=0; j<n; j++){  
34.             R r=rs[j];  
35.             r.E+=r.p;  
36.             for(int i=j+1; i<n; i++){  
37.                 R s=rs[i];  
38.                 double d=Math.sqrt((r.x-s.x)*(r.x-s.x)+(r.y-s.y)*(r.y-s.y));  
39.                 if(d<r.t-s.t+EPS){  
40.                     s.E=Math.max(s.E, r.E);  
41.                 }  
42.             }  
43.         }  
44.         double ans=0;  
45.         for(R r : rs){  
46.             ans=Math.max(ans, r.E);  
47.         }  
48.         println(""+ans);  
49.     }  
50.   
51.     class R{  
52.         int x, y, t;  
53.         double p;  
54.         double E;  
55.     }  
56.   
57.     void println(String s){  
58.         System.out.println(s);  
59.     }  
60.   
61.     void print(String s){  
62.         System.out.print(s);  
63.     }  
64.   
65.     public static void main(String[] args){  
66.         new C().run();  
67.     }  
68. }  

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

    double EPS=1e-6;

    void run(){
        n=sc.nextInt();
        rs=new R[n];
        for(int i=0; i<n; i++){
            R r=new R();
            r.x=sc.nextInt();
            r.y=sc.nextInt();
            r.t=sc.nextInt();
            r.p=sc.nextDouble();
            rs[i]=r;
        }
        Arrays.sort(rs, new Comparator<R>(){
            @Override
            public int compare(R r1, R r2){
                return r2.t-r1.t;
            }
        });
        for(int j=0; j<n; j++){
            R r=rs[j];
            r.E+=r.p;
            for(int i=j+1; i<n; i++){
                R s=rs[i];
                double d=Math.sqrt((r.x-s.x)*(r.x-s.x)+(r.y-s.y)*(r.y-s.y));
                if(d<r.t-s.t+EPS){
                    s.E=Math.max(s.E, r.E);
                }
            }
        }
        double ans=0;
        for(R r : rs){
            ans=Math.max(ans, r.E);
        }
        println(""+ans);
    }

    class R{
        int x, y, t;
        double p;
        double E;
    }

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

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

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

■Result
○×○××
1636p
151位

■Rating
1759 -> 1709

さらにRatingダウン．Bを落としたのが痛かった…．

Codeforces Beta Round #28

Codeforces Beta Round #28 9/18(0:00~2:00)

久し振りのCodeforces．今回もCodeforces format．

■A. Bender Problem
□問題
複数の釘，長さが異なる複数の(金属)棒がある．釘を頂点，棒を辺として多角形を作れるかどうかを判定せよ．但し，個々の棒は任意の位置で1度折り曲げる必要がある．

□解法
例えば釘が4本，棒が2本とし，釘の座標をp₁,p₂,p₃,p₄とする．棒を折り曲げる座標は，p₁,p₃かp₂,p₄の2通りとなるため，それぞれが可能かを調べれば良い．

□コード

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5. import static java.lang.Math.*;  
6. import static java.util.Arrays.*;  
7.   
8. public class A{  
9.     Scanner sc=new Scanner(System.in);  
10.   
11.     int n, m;  
12.   
13.     int[] x, y;  
14.     int[] rod;  
15.   
16.     void run(){  
17.         n=sc.nextInt();  
18.         m=sc.nextInt();  
19.         x=new int[n];  
20.         y=new int[n];  
21.         rod=new int[m];  
22.         for(int i=0; i<n; i++){  
23.             x[i]=sc.nextInt();  
24.             y[i]=sc.nextInt();  
25.         }  
26.         for(int i=0; i<m; i++)  
27.             rod[i]=sc.nextInt();  
28.   
29.         boolean f1=true;  
30.         boolean f2=true;  
31.   
32.         int[] ans1=new int[n];  
33.         boolean[] selected=new boolean[m];  
34.   
35.         Arrays.fill(ans1, -1);  
36.         Arrays.fill(selected, false);  
37.         for(int k=0; k<n; k+=2){  
38.             // k-1,k,k+1  
39.             int x1=x[(k-1+n)%n];  
40.             int y1=y[(k-1+n)%n];  
41.             int x2=x[k];  
42.             int y2=y[k];  
43.             int x3=x[k+1];  
44.             int y3=y[k+1];  
45.             int len1=(int)Math.sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));  
46.             int len2=(int)Math.sqrt((x3-x2)*(x3-x2)+(y3-y2)*(y3-y2));  
47.             boolean f=false;  
48.             for(int i=0; i<m; i++){  
49.                 if(!selected[i]&&len1+len2==rod[i]){  
50.                     selected[i]=true;  
51.                     ans1[k]=i+1;  
52.                     f=true;  
53.                     break;  
54.                 }  
55.             }  
56.             if(!f){  
57.                 f1=false;  
58.                 break;  
59.             }  
60.         }  
61.   
62.         int[] ans2=new int[n];  
63.         Arrays.fill(ans2, -1);  
64.         Arrays.fill(selected, false);  
65.         for(int k=1; k<n; k+=2){  
66.             // k-1,k,k+1  
67.             int x1=x[k-1];  
68.             int y1=y[k-1];  
69.             int x2=x[k];  
70.             int y2=y[k];  
71.             int x3=x[(k+1)%n];  
72.             int y3=y[(k+1)%n];  
73.             int len1=(int)Math.sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));  
74.             int len2=(int)Math.sqrt((x3-x2)*(x3-x2)+(y3-y2)*(y3-y2));  
75.             boolean f=false;  
76.             for(int i=0; i<m; i++){  
77.                 if(!selected[i]&&len1+len2==rod[i]){  
78.                     selected[i]=true;  
79.                     ans2[k]=i+1;  
80.                     f=true;  
81.                     break;  
82.                 }  
83.             }  
84.             if(!f){  
85.                 f2=false;  
86.                 break;  
87.             }  
88.         }  
89.           
90.         if(f1||f2){  
91.             println("YES");  
92.             if(f1){  
93.                 for(int i=0; i<n; i++)  
94.                     print(ans1[i]+" ");  
95.                 println("");  
96.             }  
97.             else if(f2){  
98.                 for(int i=0; i<n; i++)  
99.                     print(ans2[i]+" ");  
100.                 println("");  
101.             }  
102.         }else{  
103.             println("NO");  
104.         }  
105.   
106.     }  
107.   
108.     void println(String s){  
109.         System.out.println(s);  
110.     }  
111.   
112.     void print(String s){  
113.         System.out.print(s);  
114.     }  
115.   
116.     public static void main(String[] args){  
117.         new A().run();  
118.     }  
119. }  

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

    int[] x, y;
    int[] rod;

    void run(){
        n=sc.nextInt();
        m=sc.nextInt();
        x=new int[n];
        y=new int[n];
        rod=new int[m];
        for(int i=0; i<n; i++){
            x[i]=sc.nextInt();
            y[i]=sc.nextInt();
        }
        for(int i=0; i<m; i++)
            rod[i]=sc.nextInt();

        boolean f1=true;
        boolean f2=true;

        int[] ans1=new int[n];
        boolean[] selected=new boolean[m];

        Arrays.fill(ans1, -1);
        Arrays.fill(selected, false);
        for(int k=0; k<n; k+=2){
            // k-1,k,k+1
            int x1=x[(k-1+n)%n];
            int y1=y[(k-1+n)%n];
            int x2=x[k];
            int y2=y[k];
            int x3=x[k+1];
            int y3=y[k+1];
            int len1=(int)Math.sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
            int len2=(int)Math.sqrt((x3-x2)*(x3-x2)+(y3-y2)*(y3-y2));
            boolean f=false;
            for(int i=0; i<m; i++){
                if(!selected[i]&&len1+len2==rod[i]){
                    selected[i]=true;
                    ans1[k]=i+1;
                    f=true;
                    break;
                }
            }
            if(!f){
                f1=false;
                break;
            }
        }

        int[] ans2=new int[n];
        Arrays.fill(ans2, -1);
        Arrays.fill(selected, false);
        for(int k=1; k<n; k+=2){
            // k-1,k,k+1
            int x1=x[k-1];
            int y1=y[k-1];
            int x2=x[k];
            int y2=y[k];
            int x3=x[(k+1)%n];
            int y3=y[(k+1)%n];
            int len1=(int)Math.sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
            int len2=(int)Math.sqrt((x3-x2)*(x3-x2)+(y3-y2)*(y3-y2));
            boolean f=false;
            for(int i=0; i<m; i++){
                if(!selected[i]&&len1+len2==rod[i]){
                    selected[i]=true;
                    ans2[k]=i+1;
                    f=true;
                    break;
                }
            }
            if(!f){
                f2=false;
                break;
            }
        }
        
        if(f1||f2){
            println("YES");
            if(f1){
                for(int i=0; i<n; i++)
                    print(ans1[i]+" ");
                println("");
            }
            else if(f2){
                for(int i=0; i<n; i++)
                    print(ans2[i]+" ");
                println("");
            }
        }else{
            println("NO");
        }

    }

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

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

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

■B. pSort
□問題
n個のセルがある．セルiとセルjはある条件にて各々が持つ値を交換する事が出来る．
初期状態では，n個のセルは，それぞれ1,2,…,n-1,nという値を持っている．
n個のセルの最終状態とどのセル同士が値を交換できるかの情報が与えられた時，初期状態から最終状態への遷移が可能かどうかを判定せよ．

□解法
交換できるセルは互いに素な集合．
例えば，0,…,7まであるとして，
集合1 : 0,3,5,6
集合2 : 1,2,4
集合3 : 7
がそれぞれ互いの値を交換出来る等．
だから，どのセルとどのセルが交換できるかを無向グラフで表現し，強連結成分分解した後，union-find木を作り，最終状態と比較すれば良い(と思う)．最終状態は，順番はともかく集合としては，初期状態と同一のもので無ければならない．

□コード

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5. import static java.lang.Math.*;  
6. import static java.util.Arrays.*;  
7.   
8. public class B{  
9.     Scanner sc=new Scanner(System.in);  
10.   
11.     int n;  
12.     int[] a;  
13.     int[] fav;  
14.   
15.     void run(){  
16.         n=sc.nextInt();  
17.         a=new int[n];  
18.         fav=new int[n];  
19.         for(int i=0; i<n; i++)  
20.             a[i]=sc.nextInt()-1;  
21.         for(int i=0; i<n; i++)  
22.             fav[i]=sc.nextInt();  
23.   
24.         V[] vs=new V[n];  
25.         for(int i=0; i<n; i++)  
26.             vs[i]=new V(i);  
27.         boolean[][] added=new boolean[n][n];  
28.         for(int j=0; j<n; j++){  
29.             for(int i=0; i<n; i++){  
30.                 if((Math.abs(j-i)==fav[i]||Math.abs(j-i)==fav[j])&&!added[j][i]){  
31.                     added[j][i]=true;  
32.                     vs[i].add(vs[j]);  
33.                 }  
34.             }  
35.         }  
36.         scc(vs);  
37.   
38.         parent=new int[n];  
39.         rank=new int[n];  
40.   
41.         for(int i=0; i<n; i++)  
42.             makeSet(i);  
43.   
44.         for(int j=0; j<n; j++)  
45.             for(int i=0; i<n; i++)  
46.                 if(vs[i].comp==vs[j].comp)  
47.                     union(i, j);  
48.   
49.         for(int i=0; i<n; i++){  
50.             if(!sameComponents(i, a[i])){  
51.                 println("NO");  
52.                 return;  
53.             }  
54.         }  
55.         println("YES");  
56.     }  
57.   
58.     void println(String s){  
59.         System.out.println(s);  
60.     }  
61.   
62.     void print(String s){  
63.         System.out.print(s);  
64.     }  
65.   
66.     public static void main(String[] args){  
67.         new B().run();  
68.     }  
69.   
70.     // Union-Find  
71.   
72.     int[] parent;  
73.     int[] rank;  
74.   
75.     void makeSet(int x){  
76.         parent[x]=x;  
77.         rank[x]=0;  
78.     }  
79.   
80.     void union(int x, int y){  
81.         link(findSet(x), findSet(y));  
82.     }  
83.   
84.     boolean sameComponents(int x, int y){  
85.         return findSet(x)==findSet(y);  
86.     }  
87.   
88.     void link(int x, int y){  
89.         if(rank[x]>rank[y]){  
90.             parent[y]=x;  
91.         }else{  
92.             parent[x]=y;  
93.             if(rank[x]==rank[y])  
94.                 rank[y]++;  
95.         }  
96.     }  
97.   
98.     int findSet(int x){  
99.         if(parent[x]!=x)  
100.             parent[x]=findSet(parent[x]);  
101.         return parent[x];  
102.     }  
103.   
104.     // Strongly Connected Components  
105.   
106.     int m;  
107.     V[] us;  
108.   
109.     int scc(V[] vs){  
110.         m=vs.length;  
111.         us=new V[m];  
112.         for(V v : vs)  
113.             if(!v.visit)  
114.                 dfs(v);  
115.         for(V v : vs)  
116.             v.visit=false;  
117.         for(V u : us)  
118.             if(!u.visit)  
119.                 dfsrev(u, m++);  
120.         return m;  
121.     }  
122.   
123.     void dfs(V v){  
124.         v.visit=true;  
125.         for(V u : v.fs)  
126.             if(!u.visit)  
127.                 dfs(u);  
128.         us[--m]=v;  
129.     }  
130.   
131.     void dfsrev(V v, int k){  
132.         v.visit=true;  
133.         for(V u : v.rs)  
134.             if(!u.visit)  
135.                 dfsrev(u, k);  
136.         v.comp=k;  
137.     }  
138.   
139.     // 頂点  
140.     static class V{  
141.         // 接続している頂点  
142.         LinkedList<V> fs=new LinkedList<V>();  
143.         // 接続されている頂点  
144.         LinkedList<V> rs=new LinkedList<V>();  
145.         boolean visit;  
146.         int comp;  
147.   
148.         int id;  
149.         V(int id){  
150.             this.id=id;  
151.         }  
152.   
153.         void add(V to){  
154.             fs.add(to);  
155.             to.rs.add(this);  
156.         }  
157.     }  
158. }  

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 n;
    int[] a;
    int[] fav;

    void run(){
        n=sc.nextInt();
        a=new int[n];
        fav=new int[n];
        for(int i=0; i<n; i++)
            a[i]=sc.nextInt()-1;
        for(int i=0; i<n; i++)
            fav[i]=sc.nextInt();

        V[] vs=new V[n];
        for(int i=0; i<n; i++)
            vs[i]=new V(i);
        boolean[][] added=new boolean[n][n];
        for(int j=0; j<n; j++){
            for(int i=0; i<n; i++){
                if((Math.abs(j-i)==fav[i]||Math.abs(j-i)==fav[j])&&!added[j][i]){
                    added[j][i]=true;
                    vs[i].add(vs[j]);
                }
            }
        }
        scc(vs);

        parent=new int[n];
        rank=new int[n];

        for(int i=0; i<n; i++)
            makeSet(i);

        for(int j=0; j<n; j++)
            for(int i=0; i<n; i++)
                if(vs[i].comp==vs[j].comp)
                    union(i, j);

        for(int i=0; i<n; i++){
            if(!sameComponents(i, a[i])){
                println("NO");
                return;
            }
        }
        println("YES");
    }

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

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

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

    // Union-Find

    int[] parent;
    int[] rank;

    void makeSet(int x){
        parent[x]=x;
        rank[x]=0;
    }

    void union(int x, int y){
        link(findSet(x), findSet(y));
    }

    boolean sameComponents(int x, int y){
        return findSet(x)==findSet(y);
    }

    void link(int x, int y){
        if(rank[x]>rank[y]){
            parent[y]=x;
        }else{
            parent[x]=y;
            if(rank[x]==rank[y])
                rank[y]++;
        }
    }

    int findSet(int x){
        if(parent[x]!=x)
            parent[x]=findSet(parent[x]);
        return parent[x];
    }

    // Strongly Connected Components

    int m;
    V[] us;

    int scc(V[] vs){
        m=vs.length;
        us=new V[m];
        for(V v : vs)
            if(!v.visit)
                dfs(v);
        for(V v : vs)
            v.visit=false;
        for(V u : us)
            if(!u.visit)
                dfsrev(u, m++);
        return m;
    }

    void dfs(V v){
        v.visit=true;
        for(V u : v.fs)
            if(!u.visit)
                dfs(u);
        us[--m]=v;
    }

    void dfsrev(V v, int k){
        v.visit=true;
        for(V u : v.rs)
            if(!u.visit)
                dfsrev(u, k);
        v.comp=k;
    }

    // 頂点
    static class V{
        // 接続している頂点
        LinkedList<V> fs=new LinkedList<V>();
        // 接続されている頂点
        LinkedList<V> rs=new LinkedList<V>();
        boolean visit;
        int comp;

        int id;
        V(int id){
            this.id=id;
        }

        void add(V to){
            fs.add(to);
            to.rs.add(this);
        }
    }
}

C以降はどうにも解けませんでした．

■Result
○○×××
998p
158位

■Rating
1851 -> 1759

不覚にもRatingダウン．3問以上解かないとRating上昇は見込めません．

M-Judge 10158 Dungeon Wall

ACM-ICPC JAG Summer Camp 2010, Day 4
Problem D: Dungeon Wall
より

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4.   
5. public class Main{  
6.   
7.     Scanner sc=new Scanner(System.in);  
8.   
9.     int INF=1>>28;  
10.   
11.     int w, h, n;  
12.     int ix, iy, ox, oy;  
13.   
14.     boolean[][][] can;  
15.     int[] dx={0, 1, 0, -1};  
16.     int[] dy={-1, 0, 1, 0};  
17.   
18.     boolean[][] visited;  
19.     int[][] dist;  
20.     P[][] ps;  
21.   
22.     void run(){  
23.         w=sc.nextInt();  
24.         h=sc.nextInt();  
25.         n=sc.nextInt();  
26.         can=new boolean[h][w][4];  
27.         for(int j=0; j<h; j++)  
28.             for(int i=0; i<w; i++)  
29.                 for(int k=0; k<4; k++)  
30.                     can[j][i][k]=true;  
31.   
32.         for(int j=0; j<h; j++){  
33.             can[j][0][3]=false;  
34.             can[j][w-1][1]=false;  
35.         }  
36.         for(int i=0; i<w; i++){  
37.             can[0][i][0]=false;  
38.             can[h-1][i][2]=false;  
39.         }  
40.   
41.         for(int i=0; i<n; i++){  
42.             int sx=sc.nextInt();  
43.             int sy=sc.nextInt();  
44.             int tx=sc.nextInt();  
45.             int ty=sc.nextInt();  
46.             int x1=Math.min(sx, tx);  
47.             int x2=Math.max(sx, tx);  
48.             int y1=Math.min(sy, ty);  
49.             int y2=Math.max(sy, ty);  
50.   
51.             if(x1==x2){  
52.                 for(int y=y1; y<y2; y++){  
53.                     if(x1>0)  
54.                         can[y][x1-1][1]=false;  
55.                     if(x1<w)  
56.                         can[y][x1][3]=false;  
57.                 }  
58.             }else{  
59.                 // y1==y2  
60.                 for(int x=x1; x<x2; x++){  
61.                     if(y1>0)  
62.                         can[y1-1][x][2]=false;  
63.                     if(y1<h)  
64.                         can[y1][x][0]=false;  
65.                 }  
66.             }  
67.         }  
68.   
69.         ix=sc.nextInt();  
70.         iy=sc.nextInt();  
71.         ox=sc.nextInt();  
72.         oy=sc.nextInt();  
73.   
74.         visited=new boolean[h][w];  
75.         dist=new int[h][w];  
76.         ps=new P[h][w];  
77.         for(int j=0; j<h; j++)  
78.             for(int i=0; i<w; i++)  
79.                 ps[j][i]=new P(i, j);  
80.   
81.         int minDist=bfs();  
82.         int maxdist=minDist;  
83.         for(int j=0; j<h; j++){  
84.             for(int i=0; i<w; i++){  
85.                 if(can[j][i][0]){  
86.                     can[j][i][0]=false;  
87.                     can[j-1][i][2]=false;  
88.                     int d=bfs();  
89.                     if(d!=INF)  
90.                         maxdist=Math.max(maxdist, bfs());  
91.                     can[j][i][0]=true;  
92.                     can[j-1][i][2]=true;  
93.                 }  
94.                 if(can[j][i][1]){  
95.                     can[j][i][1]=false;  
96.                     can[j][i+1][3]=false;  
97.                     int d=bfs();  
98.                     if(d!=INF)  
99.                         maxdist=Math.max(maxdist, bfs());  
100.                     can[j][i][1]=true;  
101.                     can[j][i+1][3]=true;  
102.                 }  
103.             }  
104.         }  
105.         // println(minDist+"");  
106.         // println(maxdist+"");  
107.         println((maxdist-minDist)+"");  
108.     }  
109.   
110.     int bfs(){  
111.         for(int j=0; j<h; j++){  
112.             for(int i=0; i<w; i++){  
113.                 visited[j][i]=false;  
114.                 dist[j][i]=0;  
115.             }  
116.         }  
117.         LinkedList<P> q=new LinkedList<P>();  
118.         q.addLast(ps[iy][ix]);  
119.         visited[iy][ix]=true;  
120.         for(; !q.isEmpty();){  
121.             P p=q.removeFirst();  
122.             if(p.x==ox&&p.y==oy)  
123.                 return dist[p.y][p.x];  
124.             for(int d=0; d<4; d++){  
125.                 int x=p.x+dx[d];  
126.                 int y=p.y+dy[d];  
127.                 if(can[p.y][p.x][d]&&!visited[y][x]){  
128.                     q.addLast(ps[y][x]);  
129.                     visited[y][x]=true;  
130.                     dist[y][x]=dist[p.y][p.x]+1;  
131.                 }  
132.             }  
133.         }  
134.         return INF;  
135.     }  
136.   
137.     class P{  
138.         int x, y;  
139.   
140.         P(int x, int y){  
141.             this.x=x;  
142.             this.y=y;  
143.         }  
144.     }  
145.   
146.     public static void main(String[] args){  
147.         new Main().run();  
148.     }  
149.   
150.     void println(String s){  
151.         System.out.println(s);  
152.     }  
153.   
154.     void print(String s){  
155.         System.out.print(s);  
156.     }  
157. }  

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

public class Main{

    Scanner sc=new Scanner(System.in);

    int INF=1>>28;

    int w, h, n;
    int ix, iy, ox, oy;

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

    boolean[][] visited;
    int[][] dist;
    P[][] ps;

    void run(){
        w=sc.nextInt();
        h=sc.nextInt();
        n=sc.nextInt();
        can=new boolean[h][w][4];
        for(int j=0; j<h; j++)
            for(int i=0; i<w; i++)
                for(int k=0; k<4; k++)
                    can[j][i][k]=true;

        for(int j=0; j<h; j++){
            can[j][0][3]=false;
            can[j][w-1][1]=false;
        }
        for(int i=0; i<w; i++){
            can[0][i][0]=false;
            can[h-1][i][2]=false;
        }

        for(int i=0; i<n; i++){
            int sx=sc.nextInt();
            int sy=sc.nextInt();
            int tx=sc.nextInt();
            int ty=sc.nextInt();
            int x1=Math.min(sx, tx);
            int x2=Math.max(sx, tx);
            int y1=Math.min(sy, ty);
            int y2=Math.max(sy, ty);

            if(x1==x2){
                for(int y=y1; y<y2; y++){
                    if(x1>0)
                        can[y][x1-1][1]=false;
                    if(x1<w)
                        can[y][x1][3]=false;
                }
            }else{
                // y1==y2
                for(int x=x1; x<x2; x++){
                    if(y1>0)
                        can[y1-1][x][2]=false;
                    if(y1<h)
                        can[y1][x][0]=false;
                }
            }
        }

        ix=sc.nextInt();
        iy=sc.nextInt();
        ox=sc.nextInt();
        oy=sc.nextInt();

        visited=new boolean[h][w];
        dist=new int[h][w];
        ps=new P[h][w];
        for(int j=0; j<h; j++)
            for(int i=0; i<w; i++)
                ps[j][i]=new P(i, j);

        int minDist=bfs();
        int maxdist=minDist;
        for(int j=0; j<h; j++){
            for(int i=0; i<w; i++){
                if(can[j][i][0]){
                    can[j][i][0]=false;
                    can[j-1][i][2]=false;
                    int d=bfs();
                    if(d!=INF)
                        maxdist=Math.max(maxdist, bfs());
                    can[j][i][0]=true;
                    can[j-1][i][2]=true;
                }
                if(can[j][i][1]){
                    can[j][i][1]=false;
                    can[j][i+1][3]=false;
                    int d=bfs();
                    if(d!=INF)
                        maxdist=Math.max(maxdist, bfs());
                    can[j][i][1]=true;
                    can[j][i+1][3]=true;
                }
            }
        }
        // println(minDist+"");
        // println(maxdist+"");
        println((maxdist-minDist)+"");
    }

    int bfs(){
        for(int j=0; j<h; j++){
            for(int i=0; i<w; i++){
                visited[j][i]=false;
                dist[j][i]=0;
            }
        }
        LinkedList<P> q=new LinkedList<P>();
        q.addLast(ps[iy][ix]);
        visited[iy][ix]=true;
        for(; !q.isEmpty();){
            P p=q.removeFirst();
            if(p.x==ox&&p.y==oy)
                return dist[p.y][p.x];
            for(int d=0; d<4; d++){
                int x=p.x+dx[d];
                int y=p.y+dy[d];
                if(can[p.y][p.x][d]&&!visited[y][x]){
                    q.addLast(ps[y][x]);
                    visited[y][x]=true;
                    dist[y][x]=dist[p.y][p.x]+1;
                }
            }
        }
        return INF;
    }

    class P{
        int x, y;

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

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

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

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

M-Judge 10157 Save your cats

ACM-ICPC JAG Summer Camp 2010, Day 4
Problem C: Save your cats
より

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4.   
5. public class Main{  
6.   
7.     Scanner sc=new Scanner(System.in);  
8.   
9.     int n, m;  
10.     int[] x, y;  
11.   
12.     int INF=1>>28;  
13.   
14.     int[] p;  
15.     int[] rank;  
16.   
17.     void run(){  
18.         n=sc.nextInt();  
19.         m=sc.nextInt();  
20.         x=new int[n];  
21.         y=new int[n];  
22.   
23.         for(int i=0; i<n; i++){  
24.             x[i]=sc.nextInt();  
25.             y[i]=sc.nextInt();  
26.         }  
27.   
28.         double sumW=0.0;  
29.         E[] es=new E[m];  
30.         for(int i=0; i<m; i++){  
31.             int p=sc.nextInt()-1;  
32.             int q=sc.nextInt()-1;  
33.             double w=Math.sqrt((x[q]-x[p])*(x[q]-x[p])+(y[q]-y[p])*(y[q]-y[p]));  
34.             sumW+=w;  
35.             es[i]=new E(p, q, w);  
36.         }  
37.   
38.         Arrays.sort(es, new Comparator<E>(){  
39.             public int compare(E e1, E e2){  
40.                 return e1.w<e2.w?1:-1;  
41.             }  
42.         });  
43.   
44.         p=new int[n];  
45.         rank=new int[n];  
46.         for(int i=0; i<n; i++)  
47.             p[i]=i;  
48.   
49.         double extW=0.0;  
50.         for(E e : es){  
51.             if(findSet(e.v)!=findSet(e.u)){  
52.                 extW+=e.w;  
53.                 union(e.v, e.u);  
54.             }  
55.         }  
56.         println((sumW-extW)+"");  
57.     }  
58.   
59.     void union(int x, int y){  
60.         x=findSet(x);  
61.         y=findSet(y);  
62.         if(rank[x]>rank[y]){  
63.             p[y]=x;  
64.         }else{  
65.             p[x]=y;  
66.             if(rank[x]==rank[y]){  
67.                 rank[y]++;  
68.             }  
69.         }  
70.     }  
71.   
72.     int findSet(int x){  
73.         if(p[x]!=x)  
74.             p[x]=findSet(p[x]);  
75.         return p[x];  
76.     }  
77.   
78.     public static void main(String[] args){  
79.         new Main().run();  
80.     }  
81.   
82.     void println(String s){  
83.         System.out.println(s);  
84.     }  
85.   
86.     void print(String s){  
87.         System.out.print(s);  
88.     }  
89.   
90.     class E{  
91.         int v, u;  
92.         double w;  
93.   
94.         E(int v, int u, double w){  
95.             this.v=v;  
96.             this.u=u;  
97.             this.w=w;  
98.         }  
99.     }  
100. }  

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

public class Main{

    Scanner sc=new Scanner(System.in);

    int n, m;
    int[] x, y;

    int INF=1>>28;

    int[] p;
    int[] rank;

    void run(){
        n=sc.nextInt();
        m=sc.nextInt();
        x=new int[n];
        y=new int[n];

        for(int i=0; i<n; i++){
            x[i]=sc.nextInt();
            y[i]=sc.nextInt();
        }

        double sumW=0.0;
        E[] es=new E[m];
        for(int i=0; i<m; i++){
            int p=sc.nextInt()-1;
            int q=sc.nextInt()-1;
            double w=Math.sqrt((x[q]-x[p])*(x[q]-x[p])+(y[q]-y[p])*(y[q]-y[p]));
            sumW+=w;
            es[i]=new E(p, q, w);
        }

        Arrays.sort(es, new Comparator<E>(){
            public int compare(E e1, E e2){
                return e1.w<e2.w?1:-1;
            }
        });

        p=new int[n];
        rank=new int[n];
        for(int i=0; i<n; i++)
            p[i]=i;

        double extW=0.0;
        for(E e : es){
            if(findSet(e.v)!=findSet(e.u)){
                extW+=e.w;
                union(e.v, e.u);
            }
        }
        println((sumW-extW)+"");
    }

    void union(int x, int y){
        x=findSet(x);
        y=findSet(y);
        if(rank[x]>rank[y]){
            p[y]=x;
        }else{
            p[x]=y;
            if(rank[x]==rank[y]){
                rank[y]++;
            }
        }
    }

    int findSet(int x){
        if(p[x]!=x)
            p[x]=findSet(p[x]);
        return p[x];
    }

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

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

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

    class E{
        int v, u;
        double w;

        E(int v, int u, double w){
            this.v=v;
            this.u=u;
            this.w=w;
        }
    }
}

ただし，実行時間3:00[s]超．

M-Judge 10156 Kaeru Jump

ACM-ICPC JAG Summer Camp 2010, Day 4
Problem B: Kaeru Jump
より

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4.   
5. public class Main{  
6.   
7.     Scanner sc=new Scanner(System.in);  
8.   
9.     int h, w;  
10.     int[][] a;  
11.     int x0, y0;  
12.     int dir;  
13.   
14.     int[] dx={0, 1, 0, -1};  
15.     int[] dy={-1, 0, 1, 0};  
16.     char[] dc={'U', 'R', 'D', 'L'};  
17.   
18.     int nLeaf;  
19.   
20.     LinkedList<Character> solution;  
21.   
22.     void run(){  
23.         solution=new LinkedList<Character>();  
24.         h=sc.nextInt();  
25.         w=sc.nextInt();  
26.         a=new int[h][w];  
27.   
28.         for(int j=0; j<h; j++){  
29.             String s=sc.next();  
30.             for(int i=0; i<w; i++){  
31.                 char c=s.charAt(i);  
32.                 if(c=='.'){  
33.                     a[j][i]=-1;  
34.                 }else if(c=='o'){  
35.                     a[j][i]=nLeaf++;  
36.                 }else{  
37.                     a[j][i]=nLeaf++;  
38.                     x0=i;  
39.                     y0=j;  
40.                     switch(c){  
41.                     case 'U':  
42.                         dir=0;  
43.                         break;  
44.                     case 'R':  
45.                         dir=1;  
46.                         break;  
47.                     case 'D':  
48.                         dir=2;  
49.                         break;  
50.                     case 'L':  
51.                         dir=3;  
52.                         break;  
53.                     }  
54.                 }  
55.             }  
56.         }  
57.         sol();  
58.     }  
59.   
60.     void sol(){  
61.         // show();  
62.         rec(x0, y0, dir, nLeaf);  
63.         for(char c : solution)  
64.             print(c+"");  
65.         println("");  
66.     }  
67.   
68.     boolean solved=false;  
69.   
70.     void show(){  
71.         for(int j=0; j<h; j++){  
72.             for(int i=0; i<w; i++){  
73.                 print(a[j][i]+", ");  
74.             }  
75.             println("");  
76.         }  
77.         println("");  
78.     }  
79.   
80.     void rec(int x, int y, int dir0, int leaf){  
81.         if(leaf==1){  
82.             // println(Arrays.toString(solution.toArray()));  
83.             solved=true;  
84.             return;  
85.         }  
86.         // show();  
87.         int l=a[y][x];  
88.         a[y][x]=-1;  
89.         for(int d=-1; d<=1; d++){  
90.             int dir=(dir0+d+4)%4;  
91.             int i=x;  
92.             int j=y;  
93.             for(; i>=0&&i<w&&j>=0&&j<h; i+=dx[dir], j+=dy[dir]){  
94.                 if(a[j][i]>=0){  
95.                     solution.addLast(dc[dir]);  
96.                     rec(i, j, dir, leaf-1);  
97.                     if(solved)  
98.                         return;  
99.                     solution.removeLast();  
100.                     break;  
101.                 }  
102.             }  
103.         }  
104.         a[y][x]=l;  
105.     }  
106.   
107.     public static void main(String[] args){  
108.         new Main().run();  
109.     }  
110.   
111.     void println(String s){  
112.         System.out.println(s);  
113.     }  
114.   
115.     void print(String s){  
116.         System.out.print(s);  
117.     }  
118. }  

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

public class Main{

    Scanner sc=new Scanner(System.in);

    int h, w;
    int[][] a;
    int x0, y0;
    int dir;

    int[] dx={0, 1, 0, -1};
    int[] dy={-1, 0, 1, 0};
    char[] dc={'U', 'R', 'D', 'L'};

    int nLeaf;

    LinkedList<Character> solution;

    void run(){
        solution=new LinkedList<Character>();
        h=sc.nextInt();
        w=sc.nextInt();
        a=new int[h][w];

        for(int j=0; j<h; j++){
            String s=sc.next();
            for(int i=0; i<w; i++){
                char c=s.charAt(i);
                if(c=='.'){
                    a[j][i]=-1;
                }else if(c=='o'){
                    a[j][i]=nLeaf++;
                }else{
                    a[j][i]=nLeaf++;
                    x0=i;
                    y0=j;
                    switch(c){
                    case 'U':
                        dir=0;
                        break;
                    case 'R':
                        dir=1;
                        break;
                    case 'D':
                        dir=2;
                        break;
                    case 'L':
                        dir=3;
                        break;
                    }
                }
            }
        }
        sol();
    }

    void sol(){
        // show();
        rec(x0, y0, dir, nLeaf);
        for(char c : solution)
            print(c+"");
        println("");
    }

    boolean solved=false;

    void show(){
        for(int j=0; j<h; j++){
            for(int i=0; i<w; i++){
                print(a[j][i]+", ");
            }
            println("");
        }
        println("");
    }

    void rec(int x, int y, int dir0, int leaf){
        if(leaf==1){
            // println(Arrays.toString(solution.toArray()));
            solved=true;
            return;
        }
        // show();
        int l=a[y][x];
        a[y][x]=-1;
        for(int d=-1; d<=1; d++){
            int dir=(dir0+d+4)%4;
            int i=x;
            int j=y;
            for(; i>=0&&i<w&&j>=0&&j<h; i+=dx[dir], j+=dy[dir]){
                if(a[j][i]>=0){
                    solution.addLast(dc[dir]);
                    rec(i, j, dir, leaf-1);
                    if(solved)
                        return;
                    solution.removeLast();
                    break;
                }
            }
        }
        a[y][x]=l;
    }

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

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

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

M-Judge 10146 Carrot Tour

ACM-ICPC JAG Summer Camp 2010, Day 3
Problem B: Carrot Tour
より

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 Main{  
8.     Scanner sc=new Scanner(System.in);  
9.   
10.     final int INF=1>>28;  
11.     final double EPS=1e-9;  
12.   
13.     int n;  
14.     double r;  
15.     double theta;  
16.     int[] xs, ys;  
17.     double[][] cost;  
18.     boolean[][][] can;  
19.   
20.     void run(){  
21.         n=sc.nextInt();  
22.         r=sc.nextDouble();  
23.         theta=sc.nextDouble();  
24.         xs=new int[n];  
25.         ys=new int[n];  
26.         cost=new double[n][n];  
27.         can=new boolean[n][n][n];  
28.         for(int i=0; i<n; i++){  
29.             xs[i]=sc.nextInt();  
30.             ys[i]=sc.nextInt();  
31.         }  
32.           
33.         for(int j=0; j<n; j++){  
34.             for(int i=0; i<n; i++){  
35.                 double dx=xs[j]-xs[i];  
36.                 double dy=ys[j]-ys[i];  
37.                 if(i==j)  
38.                     cost[j][i]=INF;  
39.                 else  
40.                     cost[j][i]=Math.sqrt(dx*dx+dy*dy);  
41.             }  
42.         }  
43.   
44.         // i->j->k  
45.         for(int k=0; k<n; k++){  
46.             for(int j=0; j<n; j++){  
47.                 if(j==k)  
48.                     continue;  
49.                 for(int i=0; i<n; i++){  
50.                     if(i==k||i==j)  
51.                         continue;  
52.                     double x1=xs[j]-xs[i];  
53.                     double y1=ys[j]-ys[i];  
54.                     double x2=xs[k]-xs[j];  
55.                     double y2=ys[k]-ys[j];  
56.                     double cost=(x1*x2+y1*y2)  
57.                             /Math.sqrt((x1*x1+y1*y1)*(x2*x2+y2*y2));  
58.                     if(Math.cos(Math.toRadians(theta))<cost+EPS)  
59.                         can[i][j][k]=true;  
60.                 }  
61.             }  
62.         }  
63.   
64.         double dp[][]=new double[n][n];  
65.         double t[][]=new double[n][n];  
66.   
67.         for(int j=0; j<n; j++)  
68.             for(int i=0; i<n; i++)  
69.                 t[i][j]=INF;  
70.         for(int j=0; j<n; j++)  
71.             t[0][j]=cost[0][j];  
72.   
73.         for(int c=0;; c++){  
74.             boolean f=false;  
75.             for(int j=0; j<n; j++)  
76.                 for(int i=0; i<n; i++)  
77.                     if(t[j][i]<r+EPS)  
78.                         f=true;  
79.             if(!f){  
80.                 println(c+"");  
81.                 return;  
82.             }  
83.   
84.             for(int k=0; k<n; k++){  
85.                 for(int j=0; j<n; j++){  
86.                     dp[j][k]=INF;  
87.                     for(int i=0; i<n; i++){  
88.                         if(can[i][j][k]){  
89.                             dp[j][k]=Math.min(dp[j][k], t[i][j]+cost[j][k]);  
90.                         }  
91.                     }  
92.                 }  
93.             }  
94.             for(int j=0; j<n; j++)  
95.                 for(int i=0; i<n; i++)  
96.                     t[j][i]=dp[j][i];  
97.         }  
98.     }  
99.   
100.     public static void main(String[] args){  
101.         new Main().run();  
102.     }  
103.   
104.     void print(String s){  
105.         System.out.print(s);  
106.     }  
107.   
108.     void println(String s){  
109.         System.out.println(s);  
110.     }  
111.   
112.     void println(){  
113.         System.out.println();  
114.     }  
115.   
116. }  

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

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

    final int INF=1>>28;
    final double EPS=1e-9;

    int n;
    double r;
    double theta;
    int[] xs, ys;
    double[][] cost;
    boolean[][][] can;

    void run(){
        n=sc.nextInt();
        r=sc.nextDouble();
        theta=sc.nextDouble();
        xs=new int[n];
        ys=new int[n];
        cost=new double[n][n];
        can=new boolean[n][n][n];
        for(int i=0; i<n; i++){
            xs[i]=sc.nextInt();
            ys[i]=sc.nextInt();
        }
        
        for(int j=0; j<n; j++){
            for(int i=0; i<n; i++){
                double dx=xs[j]-xs[i];
                double dy=ys[j]-ys[i];
                if(i==j)
                    cost[j][i]=INF;
                else
                    cost[j][i]=Math.sqrt(dx*dx+dy*dy);
            }
        }

        // i->j->k
        for(int k=0; k<n; k++){
            for(int j=0; j<n; j++){
                if(j==k)
                    continue;
                for(int i=0; i<n; i++){
                    if(i==k||i==j)
                        continue;
                    double x1=xs[j]-xs[i];
                    double y1=ys[j]-ys[i];
                    double x2=xs[k]-xs[j];
                    double y2=ys[k]-ys[j];
                    double cost=(x1*x2+y1*y2)
                            /Math.sqrt((x1*x1+y1*y1)*(x2*x2+y2*y2));
                    if(Math.cos(Math.toRadians(theta))<cost+EPS)
                        can[i][j][k]=true;
                }
            }
        }

        double dp[][]=new double[n][n];
        double t[][]=new double[n][n];

        for(int j=0; j<n; j++)
            for(int i=0; i<n; i++)
                t[i][j]=INF;
        for(int j=0; j<n; j++)
            t[0][j]=cost[0][j];

        for(int c=0;; c++){
            boolean f=false;
            for(int j=0; j<n; j++)
                for(int i=0; i<n; i++)
                    if(t[j][i]<r+EPS)
                        f=true;
            if(!f){
                println(c+"");
                return;
            }

            for(int k=0; k<n; k++){
                for(int j=0; j<n; j++){
                    dp[j][k]=INF;
                    for(int i=0; i<n; i++){
                        if(can[i][j][k]){
                            dp[j][k]=Math.min(dp[j][k], t[i][j]+cost[j][k]);
                        }
                    }
                }
            }
            for(int j=0; j<n; j++)
                for(int i=0; i<n; i++)
                    t[j][i]=dp[j][i];
        }
    }

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

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

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

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

}

M-Judge 10145 Ennichi

ACM-ICPC JAG Summer Camp 2010, Day 3
Problem A: Ennichi
より

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 Main{  
8.     Scanner sc=new Scanner(System.in);  
9.   
10.     final int INF=1>>30;  
11.     final double EPS=1e-9;  
12.   
13.     int h, w, n;  
14.     char[][] a;  
15.   
16.     void run(){  
17.         h=sc.nextInt();  
18.         w=sc.nextInt();  
19.         n=sc.nextInt();  
20.         a=new char[h][w];  
21.         for(int j=0; j<h; j++){  
22.             String s=sc.next();  
23.             for(int i=0; i<w; i++){  
24.                 a[j][i]=s.charAt(i);  
25.             }  
26.         }  
27.   
28.         for(int j=0; j<h; j++){  
29.             for(int i=0; i<w-1; i++){  
30.                 if(a[j][i]==a[j][i+1])  
31.                     continue;  
32.   
33.                 // swap(i,j)<->(i+1,j)  
34.                 char c=a[j][i];  
35.                 a[j][i]=a[j][i+1];  
36.                 a[j][i+1]=c;  
37.   
38.                 if(check()){  
39.                     println("YES");  
40.                     return;  
41.                 }  
42.   
43.                 c=a[j][i];  
44.                 a[j][i]=a[j][i+1];  
45.                 a[j][i+1]=c;  
46.             }  
47.         }  
48.         println("NO");  
49.     }  
50.   
51.     void show(char[][] a){  
52.         for(int j=0; j<h; j++){  
53.             for(int i=0; i<w; i++){  
54.                 print(a[j][i]+"");  
55.             }  
56.             println("");  
57.         }  
58.     }  
59.   
60.     boolean check(){  
61.         boolean[][] clear;  
62.         char[][] a=new char[h][w];  
63.         for(int j=0; j<h; j++)  
64.             for(int i=0; i<w; i++)  
65.                 a[j][i]=this.a[j][i];  
66.   
67.         for(;;){  
68.             // 落下  
69.             for(int i=0; i<w; i++){  
70.                 for(int j=1; j<h; j++){  
71.                     if(a[j][i]!='.')  
72.                         continue;  
73.                     for(int k=j; k>0; k--)  
74.                         a[k][i]=a[k-1][i];  
75.                     a[0][i]='.';  
76.                 }  
77.             }  
78.   
79.             boolean cl=false;  
80.             clear=new boolean[h][w];  
81.   
82.             for(int y=0; y<h; y++){  
83.                 for(int x=0; x<w; x++){  
84.                     // (x, y)から縦/横を調べる  
85.                     if(a[y][x]=='.')  
86.                         continue;  
87.   
88.                     boolean f=true;  
89.                     for(int y2=y; y2<y+n; y2++){  
90.                         if(y2>=h||a[y2][x]!=a[y][x]){  
91.                             f=false;  
92.                             break;  
93.                         }  
94.                     }  
95.                     if(f){  
96.                         for(int y2=y; y2<h&&a[y2][x]==a[y][x]; y2++)  
97.                             clear[y2][x]=true;  
98.                         cl=true;  
99.                     }  
100.   
101.                     f=true;  
102.                     for(int x2=x; x2<x+n; x2++){  
103.                         if(x2>=w||a[y][x2]!=a[y][x]){  
104.                             f=false;  
105.                             break;  
106.                         }  
107.                     }  
108.                     if(f){  
109.                         for(int x2=x; x2<w&&a[y][x2]==a[y][x]; x2++)  
110.                             clear[y][x2]=true;  
111.                         cl=true;  
112.                     }  
113.                 }  
114.             }  
115.   
116.             for(int j=0; j<h; j++)  
117.                 for(int i=0; i<w; i++)  
118.                     if(clear[j][i])  
119.                         a[j][i]='.';  
120.   
121.             if(!cl)  
122.                 break;  
123.         }  
124.         for(int j=0; j<h; j++)  
125.             for(int i=0; i<w; i++)  
126.                 if(a[j][i]!='.')  
127.                     return false;  
128.         return true;  
129.     }  
130.   
131.     public static void main(String[] args){  
132.         new Main().run();  
133.     }  
134.   
135.     void print(String s){  
136.         System.out.print(s);  
137.     }  
138.   
139.     void println(String s){  
140.         System.out.println(s);  
141.     }  
142.   
143.     void println(){  
144.         System.out.println();  
145.     }  
146. }  

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

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

    final int INF=1>>30;
    final double EPS=1e-9;

    int h, w, n;
    char[][] a;

    void run(){
        h=sc.nextInt();
        w=sc.nextInt();
        n=sc.nextInt();
        a=new char[h][w];
        for(int j=0; j<h; j++){
            String s=sc.next();
            for(int i=0; i<w; i++){
                a[j][i]=s.charAt(i);
            }
        }

        for(int j=0; j<h; j++){
            for(int i=0; i<w-1; i++){
                if(a[j][i]==a[j][i+1])
                    continue;

                // swap(i,j)<->(i+1,j)
                char c=a[j][i];
                a[j][i]=a[j][i+1];
                a[j][i+1]=c;

                if(check()){
                    println("YES");
                    return;
                }

                c=a[j][i];
                a[j][i]=a[j][i+1];
                a[j][i+1]=c;
            }
        }
        println("NO");
    }

    void show(char[][] a){
        for(int j=0; j<h; j++){
            for(int i=0; i<w; i++){
                print(a[j][i]+"");
            }
            println("");
        }
    }

    boolean check(){
        boolean[][] clear;
        char[][] a=new char[h][w];
        for(int j=0; j<h; j++)
            for(int i=0; i<w; i++)
                a[j][i]=this.a[j][i];

        for(;;){
            // 落下
            for(int i=0; i<w; i++){
                for(int j=1; j<h; j++){
                    if(a[j][i]!='.')
                        continue;
                    for(int k=j; k>0; k--)
                        a[k][i]=a[k-1][i];
                    a[0][i]='.';
                }
            }

            boolean cl=false;
            clear=new boolean[h][w];

            for(int y=0; y<h; y++){
                for(int x=0; x<w; x++){
                    // (x, y)から縦/横を調べる
                    if(a[y][x]=='.')
                        continue;

                    boolean f=true;
                    for(int y2=y; y2<y+n; y2++){
                        if(y2>=h||a[y2][x]!=a[y][x]){
                            f=false;
                            break;
                        }
                    }
                    if(f){
                        for(int y2=y; y2<h&&a[y2][x]==a[y][x]; y2++)
                            clear[y2][x]=true;
                        cl=true;
                    }

                    f=true;
                    for(int x2=x; x2<x+n; x2++){
                        if(x2>=w||a[y][x2]!=a[y][x]){
                            f=false;
                            break;
                        }
                    }
                    if(f){
                        for(int x2=x; x2<w&&a[y][x2]==a[y][x]; x2++)
                            clear[y][x2]=true;
                        cl=true;
                    }
                }
            }

            for(int j=0; j<h; j++)
                for(int i=0; i<w; i++)
                    if(clear[j][i])
                        a[j][i]='.';

            if(!cl)
                break;
        }
        for(int j=0; j<h; j++)
            for(int i=0; i<w; i++)
                if(a[j][i]!='.')
                    return false;
        return true;
    }

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

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

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

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

M-Judge 10136 友だちの誘い方

ACM-ICPC JAG Summer Camp 2010, Day 2
Problem 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 Main{  
8.     Scanner sc=new Scanner(System.in);  
9.   
10.     final int INF=1>>30;  
11.     final double EPS=1e-9;  
12.   
13.     int n;  
14.     int[] a, b, c;  
15.   
16.     int max=131072;  
17.     int[] tree;  
18.   
19.     void run(){  
20.         tree=new int[max*2-1];  
21.         n=sc.nextInt();  
22.         a=new int[n];  
23.         b=new int[n];  
24.         int r=0;  
25.         for(int i=0; i<n; i++){  
26.             a[i]=sc.nextInt();  
27.             b[i]=sc.nextInt();  
28.             update(a[i], b[i]+1, 0, 0, max);  
29.             r=Math.max(r, b[i]);  
30.         }  
31.   
32.         for(int i=r; i>=2; i--){  
33.             int c=query(i);  
34.             if(i<=c+1){  
35.                 println((i-1)+"");  
36.                 return;  
37.             }  
38.         }  
39.         println("0");  
40.     }  
41.   
42.     void update(int a, int b, int k, int left, int right){  
43.         // println(""+a+","+b+","+k+","+left+","+right);  
44.         if(right<=a||b<=left)  
45.             return;  
46.         if(a<=left&&right<=b){  
47.             tree[k]++;  
48.             return;  
49.         }  
50.         update(a, b, k*2+1, left, (left+right)/2);  
51.         update(a, b, k*2+2, (left+right)/2, right);  
52.     }  
53.   
54.     int query(int k){  
55.         int ret=0;  
56.         for(int i=k+max-1;;){  
57.             ret+=tree[i];  
58.             if(i==0)  
59.                 break;  
60.             i=(i-1)/2;  
61.         }  
62.         return ret;  
63.     }  
64.   
65.     public static void main(String[] args){  
66.         new Main().run();  
67.     }  
68.   
69.     void print(String s){  
70.         System.out.print(s);  
71.     }  
72.   
73.     void println(String s){  
74.         System.out.println(s);  
75.     }  
76.   
77.     void println(){  
78.         System.out.println();  
79.     }  
80. }  

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

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

    final int INF=1>>30;
    final double EPS=1e-9;

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

    int max=131072;
    int[] tree;

    void run(){
        tree=new int[max*2-1];
        n=sc.nextInt();
        a=new int[n];
        b=new int[n];
        int r=0;
        for(int i=0; i<n; i++){
            a[i]=sc.nextInt();
            b[i]=sc.nextInt();
            update(a[i], b[i]+1, 0, 0, max);
            r=Math.max(r, b[i]);
        }

        for(int i=r; i>=2; i--){
            int c=query(i);
            if(i<=c+1){
                println((i-1)+"");
                return;
            }
        }
        println("0");
    }

    void update(int a, int b, int k, int left, int right){
        // println(""+a+","+b+","+k+","+left+","+right);
        if(right<=a||b<=left)
            return;
        if(a<=left&&right<=b){
            tree[k]++;
            return;
        }
        update(a, b, k*2+1, left, (left+right)/2);
        update(a, b, k*2+2, (left+right)/2, right);
    }

    int query(int k){
        int ret=0;
        for(int i=k+max-1;;){
            ret+=tree[i];
            if(i==0)
                break;
            i=(i-1)/2;
        }
        return ret;
    }

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

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

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

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

ただし，実行時間3:00[s]超．

M-Judge 10135 雅先生の地球侵略日誌

ACM-ICPC JAG Summer Camp 2010, Day 2
Problem 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 Main{  
8.     Scanner sc=new Scanner(System.in);  
9.   
10.     final int INF=1>>30;  
11.     final double EPS=1e-9;  
12.   
13.     void run(){  
14.         long n=sc.nextLong()-1;  
15.         long r=1;  
16.         int ans=0;  
17.         for(; n/r!=0; r*=3, ans++);  
18.         println(""+ans);  
19.     }  
20.   
21.     public static void main(String[] args){  
22.         new Main().run();  
23.     }  
24.   
25.     void print(String s){  
26.         System.out.print(s);  
27.     }  
28.   
29.     void println(String s){  
30.         System.out.println(s);  
31.     }  
32.   
33.     void println(){  
34.         System.out.println();  
35.     }  
36. }  

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

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

    final int INF=1>>30;
    final double EPS=1e-9;

    void run(){
        long n=sc.nextLong()-1;
        long r=1;
        int ans=0;
        for(; n/r!=0; r*=3, ans++);
        println(""+ans);
    }

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

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

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

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

ACM-ICPC JAG Summer Camp 2010

国内予選から早2ヶ月半．
この時期は毎年，OB/OG の会による夏合宿が開かれるようです．
チームnyamaは14位だった為参加できませんでした(10位以内でないとダメ)が，合宿中のコンテストには参加出来るようなので参加してきました．

問題はhttp://m-judge.maximum.vc/より閲覧出来ます．

■Day2
寝坊．13:00頃から参戦しました．

A 雅先生の地球侵略日誌
適当に小さい値で試してみると，log₃Nみたいな感じ．ちゃっちゃと書いて提出．

B 友だちの誘い方
どうやって解くんだろう
->[i人なら問題無い人]の人数c_iを数える
->c_i+1<=iなら，c_i人誘える
->これを全てのiに対してループしてmaxを取れば…
->提出
->TLE
->O(n²)で，n<=10⁵だからTLEになるのは当たり前じゃないか
->Segment Tree使えばいいんじゃね?
->初めてのSegment Tree
->何か速くなった
->提出
->通ったー…?
->制限時間03:00[s]，実行時間04:37[s]
->ACはしたけど，Standsには影響しませんでした…

正式にACしたのは1問だけという残念振り．

■Day3
11:00項からの参戦．

A Ennichi
落ちゲーのシミュレーションすればいいのかな
->提出
->WA
->あれ…
その後，ACしたのは随分後になってからでした．まさか落下処理を間違えていたとは…．

B Carrot Tour
グラフ問題
->とりあえず，(i,j)間コストと，i->jと来た後kに進めるかを求めよう
->とりあえず，DFS
->とりあえず，サンプル合う
->とりあえず，提出
->とりあえず，TLE

全くやり方が思い浮かびませんでした．
終了後，red.cliff.jpの診断人さんのニコ生にて
[前のノード][今のノード][ニンジンの本数]=最短距離
のDPが出ていたので，サクサクッと組んだら，ACしました．

結局，この日も1問しか解けませんでした．

■Day4
ほぼ開始時刻直後から参戦．

A Alien's Counting
うーむ，とりあえずグラフにしてみよう
->連結でない所は，全く関わり合いがないので，強連結成分分解して，それぞれ求めて掛け合わせればいいのかな?(と意味不明な供述をしており)
->それぞれの値を求められない…

結局解けませんでした…

B Kaeru Jump
単純にDFSするだけでは?
->通った

D Dungeon Wall
壁が作れそうな所に作ってBFSするだけかな?
->TLE，BFS間違ってた
->修正，AC

H Ropeway
何か問題を読み間違えまくって，最終的には難しい問題だと分かりました…

この日は2問．もう一問位解きたいものです．

TopCoder 練習

HanoiGoodAndBad(Member SRM 482 Div1 Medium)

LayCurseさんのブログ
ゲームにっき(仮) | SRM482 DIV1 参加記録:
を参考に解く．

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3.   
4. public class HanoiGoodAndBad{  
5.     LinkedList<Integer> a,b,c;  
6.     int dave;  
7.     int step;  
8.   
9.     public int moves(int n, int dave){  
10.         this.dave=dave;  
11.         a=new LinkedList<Integer>();  
12.         b=new LinkedList<Integer>();  
13.         c=new LinkedList<Integer>();  
14.         for(int i=0;i<n;i++)  
15.             a.addLast(i);  
16.         step=0;  
17.         solve(a,b,c,n);  
18.           
19.         //System.out.println(Arrays.toString(a.toArray()));  
20.         //System.out.println(Arrays.toString(b.toArray()));  
21.         //System.out.println(Arrays.toString(c.toArray()));  
22.   
23.         return rec(a,b,c,n-1);  
24.     }  
25.   
26.     int rec(LinkedList<Integer> a,LinkedList<Integer> b, LinkedList<Integer> c,int k){  
27.         if(a.contains(k))  
28.             return rec(a,b,c,k-1);  
29.         else if(b.contains(k))  
30.             return (int)Math.pow(3,k)+rec(c,b,a,k-1);  
31.         else if(c.contains(k))  
32.             return 2*(int)Math.pow(3,k)+rec(a,b,c,k-1);  
33.         else  
34.             return 0;  
35.     }  
36.   
37.     void solve(LinkedList<Integer> a,LinkedList<Integer> b, LinkedList<Integer> c, int k){  
38.         if(k==0)  
39.             return;  
40.         solve(a,c,b,k-1);  
41.         if(step==dave)  return;  
42.         c.addFirst(a.removeFirst());  
43.         step++;  
44.         if(step==dave)  return;  
45.         solve(b,a,c,k-1);  
46.     }  
47. }  

import java.util.*;
import java.lang.*;

public class HanoiGoodAndBad{
    LinkedList<Integer> a,b,c;
    int dave;
    int step;

    public int moves(int n, int dave){
        this.dave=dave;
        a=new LinkedList<Integer>();
        b=new LinkedList<Integer>();
        c=new LinkedList<Integer>();
        for(int i=0;i<n;i++)
            a.addLast(i);
        step=0;
        solve(a,b,c,n);
        
        //System.out.println(Arrays.toString(a.toArray()));
        //System.out.println(Arrays.toString(b.toArray()));
        //System.out.println(Arrays.toString(c.toArray()));

        return rec(a,b,c,n-1);
    }

    int rec(LinkedList<Integer> a,LinkedList<Integer> b, LinkedList<Integer> c,int k){
        if(a.contains(k))
            return rec(a,b,c,k-1);
        else if(b.contains(k))
            return (int)Math.pow(3,k)+rec(c,b,a,k-1);
        else if(c.contains(k))
            return 2*(int)Math.pow(3,k)+rec(a,b,c,k-1);
        else
            return 0;
    }

    void solve(LinkedList<Integer> a,LinkedList<Integer> b, LinkedList<Integer> c, int k){
        if(k==0)
            return;
        solve(a,c,b,k-1);
        if(step==dave)  return;
        c.addFirst(a.removeFirst());
        step++;
        if(step==dave)  return;
        solve(b,a,c,k-1);
    }
}

TopCoder 練習

LockersDivOne(Member SRM 482 Div1 Easy)

愚直なシミュレーションでも動くことを確認．

view plainprint?

1. public class LockersDivOne{  
2.     public int lastOpened(int n){  
3.         int[] a=new int[n];  
4.         int[] b=new int[n];  
5.         int last=n;  
6.         for(int i=0;i<n;i++)  
7.             a[i]=i;  
8.         for(int s=2;;s++){  
9.             int k=0;  
10.             for(int i=0;i<last;i++){  
11.                 if(i%s!=0)  
12.                     b[k++]=a[i];  
13.             }  
14.             last=k;  
15.             if(last<=1)  
16.                 return b[0]+1;  
17.             for(int i=0;i<last;i++)  
18.                 a[i]=b[i];  
19.         }  
20.     }  
21. }  

public class LockersDivOne{
    public int lastOpened(int n){
        int[] a=new int[n];
        int[] b=new int[n];
        int last=n;
        for(int i=0;i<n;i++)
            a[i]=i;
        for(int s=2;;s++){
            int k=0;
            for(int i=0;i<last;i++){
                if(i%s!=0)
                    b[k++]=a[i];
            }
            last=k;
            if(last<=1)
                return b[0]+1;
            for(int i=0;i<last;i++)
                a[i]=b[i];
        }
    }
}

TopCoder Member SRM 482

Member SRM 482(9/16 0:00~2:00)

先週に引き続き．

■LockersDivOne(DIV1 Easy)

□Problem
1~N(1≦N≦2000000)まで番号付けされたロッカーがある．全てのロッカーは，閉じられている．
DaveとEarlは，番号の昇順にロッカーを見ていき，最初に見つけた閉じられているロッカーを開ける．その後，閉じられているロッカーを2個見つける度にそのロッカーを開けていく．番号Nまで戻ったら，はじめに戻り，2個飛ばしを3個飛ばしにし，同様のことをする．以降，4,5,6,…とロッカーを飛ばす個数を増やしていく．最後に残ったロッカーの番号は何か．

最初はLinkedListで実装しましたが，最大ケースを試したところ，メモリが足りないと言われかなり焦りました．しょうが無いので配列による実装に落ち着きましたが，最初から配列による実装にしていれば，もっと早く提出出来たと思います．ただ，今回は，Resubmitを一度もしないで済んだので，104.04pでした．

□Code

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4.   
5. public class LockersDivOne{  
6.  public int lastOpened(int N){  
7.   int[] a=new int[10000];  
8.   int[] b=new int[N];  
9.   for(int i=0;i<N;i++){  
10.    for(int k=2;k<a.length;k++){  
11.     if(a[k]==0){  
12.      a[k]++;  
13.      b[i]=k;  
14.      // System.out.println("i="+i+", k="+k);  
15.      break;  
16.     }else{  
17.      a[k]++;  
18.     }  
19.     if(a[k]==k)  
20.      a[k]=0;  
21.    }  
22.   }  
23.   int ret=0;  
24.   for(int i=0;i<N;i++){  
25.    if(b[i]>b[ret])  
26.     ret=i;  
27.    //if(b[i]<2)  
28.    // System.out.println("Error!");  
29.   }  
30.   //System.out.println(Arrays.toString(b));  
31.   //System.out.println(Arrays.toString(a));  
32.   return ret+1;  
33.  }  
34. }  

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

public class LockersDivOne{
 public int lastOpened(int N){
  int[] a=new int[10000];
  int[] b=new int[N];
  for(int i=0;i<N;i++){
   for(int k=2;k<a.length;k++){
    if(a[k]==0){
     a[k]++;
     b[i]=k;
     // System.out.println("i="+i+", k="+k);
     break;
    }else{
     a[k]++;
    }
    if(a[k]==k)
     a[k]=0;
   }
  }
  int ret=0;
  for(int i=0;i<N;i++){
   if(b[i]>b[ret])
    ret=i;
   //if(b[i]<2)
   // System.out.println("Error!");
  }
  //System.out.println(Arrays.toString(b));
  //System.out.println(Arrays.toString(a));
  return ret+1;
 }
}

■Challenge
は，今回やりませんでした．

■Result
○×× 0 -0
104.04p

■Rating
1339 -> 1372
やっとhighestを更新しました．今年中には1500まで上げたいと思います．

PKU Judge Online 1664 放苹果

■1664 放苹果

□Problem
m個のリンゴをn皿に分配する．分配の仕方は何通りあるかを求めよ．
m=7，n=3の時は，
7 0 0
6 1 0
5 2 0
5 1 1
4 3 0
4 2 1
3 3 1
3 2 2
の8種類．

□Solution
f(m,n,e)
m個のリンゴをn皿に分配する組．ただしそれぞれの皿のリンゴはe個以下とする．
f(0,0,e)=1
…0個のリンゴを0皿に分配する方法は1通り
f(m,0,e)=0 (m>0)
…1個以上のリンゴを0皿には分配できない
f(m,n,e)=Σ_{i=[i,min(m,e)]}f(m-i,n-1,min(i,e))
…まず1つの皿にリンゴを置く，その際，置けるリンゴの個数iは，[1,min(m,e)]まで．
そしてリンゴをi個置いたら，残りn-1皿にはm-i個のリンゴを置くことになるが，それぞれの皿のリンゴの個数の上限は，min(i,e)となる．
上の式より，再帰的に求める(mとnが与えられたらf(m,n,m)を呼び出せばよい)．

□Code

view plainprint?

1. package p1664;  
2.   
3. import java.util.*;  
4. import java.lang.*;  
5. import java.math.*;  
6. import java.io.*;  
7.   
8. import static java.lang.Math.*;  
9. import static java.util.Arrays.*;  
10.   
11. public class Main{  
12.   
13.     Scanner sc=new Scanner(System.in);  
14.   
15.     final int INF=Integer.MAX_VALUE;  
16.     final double EPS=1e-9;  
17.   
18.     void run(){  
19.         for(int t=sc.nextInt(); t>0; t--){  
20.             int m=sc.nextInt();  
21.             int n=sc.nextInt();  
22.             println(""+f(m, n, m));  
23.         }  
24.     }  
25.   
26.     // m個のリンゴをn皿に分配する  
27.     // ただしそれぞれの皿のリンゴはe個以下  
28.     int f(int m, int n, int e){  
29.         if(n==0)  
30.             return m==0?1:0;  
31.         int ret=0;  
32.         // ある皿に置けるリンゴの個数iは，0<=1<=min(m(上限), e(制約))  
33.         // ある皿にリンゴをi個置くと，m-i個のリンゴを残りn-1皿に分配することになる  
34.         // ただしそれぞれの皿のリンゴはmin(i(上限), e(制約))個以下  
35.         for(int i=0; i<=Math.min(m, e); i++)  
36.             ret+=f(m-i, n-1, Math.min(i, e));  
37.         return ret;  
38.     }  
39.   
40.     void print(String s){  
41.         System.out.print(s);  
42.     }  
43.   
44.     void println(String s){  
45.         System.out.println(s);  
46.     }  
47.   
48.     public static void main(String[] args){  
49.         // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
50.         new Main().run();  
51.     }  
52. }  

package p1664;

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

    final int INF=Integer.MAX_VALUE;
    final double EPS=1e-9;

    void run(){
        for(int t=sc.nextInt(); t>0; t--){
            int m=sc.nextInt();
            int n=sc.nextInt();
            println(""+f(m, n, m));
        }
    }

    // m個のリンゴをn皿に分配する
    // ただしそれぞれの皿のリンゴはe個以下
    int f(int m, int n, int e){
        if(n==0)
            return m==0?1:0;
        int ret=0;
        // ある皿に置けるリンゴの個数iは，0<=1<=min(m(上限), e(制約))
        // ある皿にリンゴをi個置くと，m-i個のリンゴを残りn-1皿に分配することになる
        // ただしそれぞれの皿のリンゴはmin(i(上限), e(制約))個以下
        for(int i=0; i<=Math.min(m, e); i++)
            ret+=f(m-i, n-1, Math.min(i, e));
        return ret;
    }

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

PKU Judge Online 1455 Crazy tea party

■1455 Crazy tea party

□Problem
n人のcrazy tea party参加者が円テーブルに座っている．各ステップで，1組の隣り合う2人が位置を交代することが出来る．n人の位置を逆順にするための最小ステップ数を求めよ．

□Solution
f(n)=最小ステップ数
g(n)=n人が一直線上に座っているとした時の反転にかかる最小ステップ数とする．

g(n)を求める．
n=5の時，
12345
↓
23451
ここまでで，n-1ステップかかる．
残り2345を反転させるためにはg(4)ステップかかる．
よって，
g(n)=g(n-1)+n-1
g(1)=1
となるため，
g(n)=n(n-1)/2

f(n)を求める．
n人を2分割してそれぞれを反転させる(3分割してそれぞれを反転させても逆順にはならないので意味が無い)．
123|456
↓
321|654
n=2mの時は，
g(n)+g(n)<g(n-k)+g(n+k) (k>0)
より，丁度真ん中で分割した時が最小ステップとなる．
f(n)=g(m)+g(m)
n=2m+1の時も，(多分)同様にして示せるため
f(n)=g(m)+g(m+1)

□Code

view plainprint?

1. package p1455;  
2.   
3. import java.util.*;  
4. import java.lang.*;  
5. import java.math.*;  
6.   
7. public class Main{  
8.     Scanner sc=new Scanner(System.in);  
9.   
10.     void run(){  
11.         for(int t=sc.nextInt(); t>0; t--){  
12.             int n=sc.nextInt();  
13.             int r=n/2;  
14.             int s=n-r;  
15.             int ans=r*(r-1)/2+s*(s-1)/2;  
16.             println(""+ans);  
17.         }  
18.     }  
19.   
20.     void println(String s){  
21.         System.out.println(s);  
22.     }  
23.   
24.     void print(String s){  
25.         System.out.print(s);  
26.     }  
27.   
28.     public static void main(String[] args){  
29.         new Main().run();  
30.     }  
31. }  

package p1455;

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

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

    void run(){
        for(int t=sc.nextInt(); t>0; t--){
            int n=sc.nextInt();
            int r=n/2;
            int s=n-r;
            int ans=r*(r-1)/2+s*(s-1)/2;
            println(""+ans);
        }
    }

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

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

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

PKU Judge Online 1517 u Calculate e

■1517 u Calculate e

□Problem
マクローリン展開によるeの計算過程を表示せよ．

□Solution
やっつけ．BigDecimalで求めた結果をベタ貼りです．

□Code

view plainprint?

1. package p1517;  
2.   
3. import java.util.*;  
4. import java.lang.*;  
5. import java.math.*;  
6.   
7. public class Main{  
8.     Scanner sc=new Scanner(System.in);  
9.   
10.     void run(){  
11.         println("n e");  
12.         println("- -----------");  
13.         println("0 1");  
14.         println("1 2");  
15.         println("2 2.5");  
16.         println("3 2.666666667");  
17.         println("4 2.708333333");  
18.         println("5 2.716666667");  
19.         println("6 2.718055556");  
20.         println("7 2.718253968");  
21.         println("8 2.718278770");  
22.         println("9 2.718281526");  
23.     }  
24.   
25.     void println(String s){  
26.         System.out.println(s);  
27.     }  
28.   
29.     void print(String s){  
30.         System.out.print(s);  
31.     }  
32.   
33.     public static void main(String[] args){  
34.         new Main().run();  
35.     }  
36. }  

package p1517;

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

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

    void run(){
        println("n e");
        println("- -----------");
        println("0 1");
        println("1 2");
        println("2 2.5");
        println("3 2.666666667");
        println("4 2.708333333");
        println("5 2.716666667");
        println("6 2.718055556");
        println("7 2.718253968");
        println("8 2.718278770");
        println("9 2.718281526");
    }

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

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

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

PKU Judge Online 1565 Skew Binary

■1565 Skew Binary

□Problem
10120(skew)=1*(2⁵-1)+0*(2⁴-1)+1*(2³-1)+2*(2²-1)+0*(2¹-1)
という方法で値を計算せよ．

□Solution
やるだけ．

□Code

view plainprint?

1. package p1565;  
2.   
3. import java.util.*;  
4. import java.lang.*;  
5. import java.math.*;  
6.   
7. public class Main{  
8.     Scanner sc=new Scanner(System.in);  
9.   
10.     void run(){  
11.         for(;;){  
12.             String s=sc.next();  
13.             if(s.equals("0"))  
14.                 break;  
15.             long ans=0;  
16.             long sum=0;  
17.             for(char c : s.toCharArray()){  
18.                 int d=c-'0';  
19.                 ans=ans*2+d;  
20.                 sum+=d;  
21.             }  
22.             ans*=2;  
23.             ans-=sum;  
24.             println(""+ans);  
25.         }  
26.     }  
27.   
28.     void println(String s){  
29.         System.out.println(s);  
30.     }  
31.   
32.     void print(String s){  
33.         System.out.print(s);  
34.     }  
35.   
36.     public static void main(String[] args){  
37.         new Main().run();  
38.     }  
39. }  

package p1565;

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

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

    void run(){
        for(;;){
            String s=sc.next();
            if(s.equals("0"))
                break;
            long ans=0;
            long sum=0;
            for(char c : s.toCharArray()){
                int d=c-'0';
                ans=ans*2+d;
                sum+=d;
            }
            ans*=2;
            ans-=sum;
            println(""+ans);
        }
    }

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

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

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

PKU Judge Online 1477 Box of Bricks

■1477 Box of Bricks

□Problem
いくつかのブロックを縦に並べた列がいくつかある．全ての列の高さを平坦化するのに必要なブロックの移動回数の最小値を求めよ．
(便宜上90°回転してます)
■■■■■
■■
■■■■
■
■■■■■■■
■■■■■
↓
■■■■
■■■■
■■■■
■■■■
■■■■
■■■■

□Solution
やるだけ．

□Code

view plainprint?

1. package p1477;  
2.   
3. import java.util.*;  
4. import java.lang.*;  
5. import java.math.*;  
6.   
7. public class Main{  
8.     Scanner sc=new Scanner(System.in);  
9.   
10.     void run(){  
11.         for(int s=1;; s++){  
12.             int n=sc.nextInt();  
13.             if(n==0)  
14.                 break;  
15.             int[] a=new int[n];  
16.             int ave=0;  
17.             for(int i=0; i<n; i++)  
18.                 ave+=a[i]=sc.nextInt();  
19.             ave/=n;  
20.             int ans=0;  
21.             for(int i=0; i<n; i++)  
22.                 if(a[i]>ave)  
23.                     ans+=a[i]-ave;  
24.             println("Set #"+s);  
25.             println("The minimum number of moves is "+ans+".");  
26.             println("");  
27.         }  
28.     }  
29.   
30.     void println(String s){  
31.         System.out.println(s);  
32.     }  
33.   
34.     void print(String s){  
35.         System.out.print(s);  
36.     }  
37.   
38.     public static void main(String[] args){  
39.         new Main().run();  
40.     }  
41. }  

package p1477;

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

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

    void run(){
        for(int s=1;; s++){
            int n=sc.nextInt();
            if(n==0)
                break;
            int[] a=new int[n];
            int ave=0;
            for(int i=0; i<n; i++)
                ave+=a[i]=sc.nextInt();
            ave/=n;
            int ans=0;
            for(int i=0; i<n; i++)
                if(a[i]>ave)
                    ans+=a[i]-ave;
            println("Set #"+s);
            println("The minimum number of moves is "+ans+".");
            println("");
        }
    }

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

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

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

PKU Judge Online 1458 Common Subsequence

■1458 Common Subsequence

□Problem
文字列sとtのLCS(Longest Common Subsequence:最長共通部分文字列)を求めよ．

□Solution
lcs(i,j)をsのi文字目までの部分文字列とtのj文字目までの部分文字列のLCSとすると，
lcs(i,0)=0
lcs(0,j)=0
lcs(i,j)=lcs(i-1,j-1)+1 (sのi文字目とtのj文字目が等しい場合)
lcs(i,j)=max(lcs(i,j-1),lcs(i-1,j)) (sのi文字目とtのj文字目が等しくない場合)
これらを使ってDP．

□Code

view plainprint?

1. package p1458;  
2.   
3. import java.util.*;  
4. import java.lang.*;  
5. import java.math.*;  
6.   
7. public class Main{  
8.     Scanner sc=new Scanner(System.in);  
9.   
10.     void run(){  
11.         for(; sc.hasNext();){  
12.             String s=sc.next();  
13.             String t=sc.next();  
14.             int m=s.length();  
15.             int n=t.length();  
16.             int[][] dp=new int[n+1][m+1];  
17.             for(int j=1; j<=n; j++){  
18.                 for(int i=1; i<=m; i++){  
19.                     if(s.charAt(i-1)==t.charAt(j-1))  
20.                         dp[j][i]=dp[j-1][i-1]+1;  
21.                     else  
22.                         dp[j][i]=Math.max(dp[j-1][i], dp[j][i-1]);  
23.                 }  
24.             }  
25.             println(""+dp[n][m]);  
26.         }  
27.     }  
28.   
29.     void println(String s){  
30.         System.out.println(s);  
31.     }  
32.   
33.     void print(String s){  
34.         System.out.print(s);  
35.     }  
36.   
37.     public static void main(String[] args){  
38.         new Main().run();  
39.     }  
40. }  

package p1458;

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

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

    void run(){
        for(; sc.hasNext();){
            String s=sc.next();
            String t=sc.next();
            int m=s.length();
            int n=t.length();
            int[][] dp=new int[n+1][m+1];
            for(int j=1; j<=n; j++){
                for(int i=1; i<=m; i++){
                    if(s.charAt(i-1)==t.charAt(j-1))
                        dp[j][i]=dp[j-1][i-1]+1;
                    else
                        dp[j][i]=Math.max(dp[j-1][i], dp[j][i-1]);
                }
            }
            println(""+dp[n][m]);
        }
    }

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

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

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

PKU Judge Online 1423 Big Number

■1423 Big Number

□Problem
n!は10進数表記で何桁になるか求めよ．

□Solution
ある自然数mが10進数表記でd(m)桁になるとき，
d(m)=[log₁₀(m)]+1
が成り立つ．
よって，
d(n!)
=[log₁₀(n!)]+1
=[Σ_k=[1,n]log₁₀(k)]+1

d(n!)を1≦n≦10⁷について予め求めておく．

□Code

view plainprint?

1. package p1423;  
2.   
3. import java.util.*;  
4. import java.lang.*;  
5. import java.math.*;  
6.   
7. public class Main{  
8.     Scanner sc=new Scanner(System.in);  
9.   
10.     void run(){  
11.         int n=(int)1e7;  
12.         int[] d=new int[n+1];  
13.         double a=0.0;  
14.         for(int i=1; i<=n; i++){  
15.             a+=Math.log10(i);  
16.             d[i]=(int)a+1;  
17.         }  
18.         for(int t=sc.nextInt(); t>0; t--){  
19.             int k=sc.nextInt();  
20.             println(d[k]+"");  
21.         }  
22.     }  
23.   
24.     void println(String s){  
25.         System.out.println(s);  
26.     }  
27.   
28.     void print(String s){  
29.         System.out.print(s);  
30.     }  
31.   
32.     public static void main(String[] args){  
33.         new Main().run();  
34.     }  
35. }  

package p1423;

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

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

    void run(){
        int n=(int)1e7;
        int[] d=new int[n+1];
        double a=0.0;
        for(int i=1; i<=n; i++){
            a+=Math.log10(i);
            d[i]=(int)a+1;
        }
        for(int t=sc.nextInt(); t>0; t--){
            int k=sc.nextInt();
            println(d[k]+"");
        }
    }

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

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

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

PKU Judge Online 1401 Factorial

■1401 Factorial

□Problem
n!を10進数で表した時，最下桁から続く0の個数を求めよ．

□Solution
やるだけ．

□Code

view plainprint?

1. package p1401;  
2.   
3. import java.util.*;  
4. import java.lang.*;  
5. import java.math.*;  
6.   
7. public class Main{  
8.     Scanner sc=new Scanner(System.in);  
9.   
10.     void run(){  
11.         for(int t=sc.nextInt(); t>0; t--){  
12.             long n=sc.nextLong();  
13.             long ans=0;  
14.             for(long r=5; r<=n; r*=5)  
15.                 ans+=n/r;  
16.             println(ans+"");  
17.         }  
18.     }  
19.   
20.     void println(String s){  
21.         System.out.println(s);  
22.     }  
23.   
24.     void print(String s){  
25.         System.out.print(s);  
26.     }  
27.   
28.     public static void main(String[] args){  
29.         new Main().run();  
30.     }  
31. }  

package p1401;

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

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

    void run(){
        for(int t=sc.nextInt(); t>0; t--){
            long n=sc.nextLong();
            long ans=0;
            for(long r=5; r<=n; r*=5)
                ans+=n/r;
            println(ans+"");
        }
    }

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

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

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

PKU Judge Online 1218 THE DRUNK JAILER

■1218 THE DRUNK JAILER

□Problem
ある刑務所には部屋がn個(1,2,3,…,n)ある．
ある夜，退屈していた看守は，ゲームを始めた．
1.各部屋(1,2,3,…)の鍵を開けていく．
2.1つ飛ばしに各部屋(2,4,6,…)の鍵を閉めていく．
3.2つ飛ばしに各部屋(3,6,9,…)の鍵を開けていく．
…
n.n-1つ飛ばしに各部屋(nのみ)の鍵を開けていく．
最終的に，鍵が空いている部屋はいくつあるか．

□Solution
やるだけ．

□Code

view plainprint?

1. package p1218;  
2.   
3. import java.util.*;  
4. import java.lang.*;  
5. import java.math.*;  
6.   
7. public class Main{  
8.     Scanner sc=new Scanner(System.in);  
9.       
10.     void run(){  
11.         for(int t=sc.nextInt();t>0;t--){  
12.             int n=sc.nextInt();  
13.             int[] a=new int[n];  
14.             // 0-lock  
15.             // 1-unlock  
16.             for(int k=1;k<=n;k++)  
17.                 for(int i=k-1;i<n;i+=k)  
18.                     a[i]=1-a[i];  
19.             int ans=0;  
20.             for(int e:a)  
21.                 ans+=e;  
22.             println(""+ans);  
23.         }  
24.     }  
25.       
26.     void println(String s){  
27.         System.out.println(s);  
28.     }  
29.   
30.     void print(String s){  
31.         System.out.print(s);  
32.     }  
33.   
34.     public static void main(String[] args){  
35.         new Main().run();  
36.     }  
37. }  

package p1218;

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

public class Main{
    Scanner sc=new Scanner(System.in);
    
    void run(){
        for(int t=sc.nextInt();t>0;t--){
            int n=sc.nextInt();
            int[] a=new int[n];
            // 0-lock
            // 1-unlock
            for(int k=1;k<=n;k++)
                for(int i=k-1;i<n;i+=k)
                    a[i]=1-a[i];
            int ans=0;
            for(int e:a)
                ans+=e;
            println(""+ans);
        }
    }
    
    void println(String s){
        System.out.println(s);
    }

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

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

PKU Judge Online 1012 Joseph

■1012 Joseph

□Problem
Josephの問題がある．これは，1~nまで数字付けされたn人が円状に並び，1の人からm人毎に省いていき，最後に残った人が生き残る，というものである．今回は，0<k<14となるkが与えられ，2k人が並ぶ．前半k人よりも先に後半k人が先に省かれるような最小のmを求めよ．

□Solution
kの範囲が狭いので，先に答えを求めておく．mの計算方法はコードのm(int k)を見て下さい．

□Code

view plainprint?

1. package p1012;  
2.   
3. import java.util.*;  
4. import java.lang.*;  
5. import java.math.*;  
6. import java.io.*;  
7.   
8. import static java.lang.Math.*;  
9. import static java.util.Arrays.*;  
10.   
11. public class Main{  
12.   
13.  Scanner sc;  
14.   
15.  final int INF=Integer.MAX_VALUE;  
16.  final double EPS=1e-9;  
17.   
18.  void run(){  
19.   sc=new Scanner(System.in);  
20.   int[] ans={0, 2, 7, 5, 30, 169, 441, 1872, 7632, 1740, 93313, 459901,  
21.     1358657, 2504881};  
22.   for(;;){  
23.    int k=sc.nextInt();  
24.    if(k==0)  
25.     break;  
26.    println(""+ans[k]);  
27.   }  
28.  }  
29.   
30.  void debug(){  
31.   for(int k=1; k<14; k++)  
32.    println("k="+k+", m="+m(k));  
33.  }  
34.   
35.  int m(int k){  
36.   int n=k*2;  
37.   LinkedList<Integer> a=new LinkedList<Integer>();  
38.   for(int m=1;; m++){  
39.    a.clear();  
40.    for(int i=0; i<n; i++)  
41.     a.add(i);  
42.    int p=0;  
43.    boolean f=true;  
44.    for(int j=0; j<k; j++){  
45.     p=(p-1+m)%a.size();  
46.     if(a.remove(p)<k){  
47.      f=false;  
48.      break;  
49.     }  
50.    }  
51.    if(f)  
52.     return m;  
53.   }  
54.  }  
55.   
56.  void print(String s){  
57.   System.out.print(s);  
58.  }  
59.   
60.  void println(String s){  
61.   System.out.println(s);  
62.  }  
63.   
64.  public static void main(String[] args){  
65.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
66.   new Main().run();  
67.  }  
68. }  

package p1012;

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;

 final int INF=Integer.MAX_VALUE;
 final double EPS=1e-9;

 void run(){
  sc=new Scanner(System.in);
  int[] ans={0, 2, 7, 5, 30, 169, 441, 1872, 7632, 1740, 93313, 459901,
    1358657, 2504881};
  for(;;){
   int k=sc.nextInt();
   if(k==0)
    break;
   println(""+ans[k]);
  }
 }

 void debug(){
  for(int k=1; k<14; k++)
   println("k="+k+", m="+m(k));
 }

 int m(int k){
  int n=k*2;
  LinkedList<Integer> a=new LinkedList<Integer>();
  for(int m=1;; m++){
   a.clear();
   for(int i=0; i<n; i++)
    a.add(i);
   int p=0;
   boolean f=true;
   for(int j=0; j<k; j++){
    p=(p-1+m)%a.size();
    if(a.remove(p)<k){
     f=false;
     break;
    }
   }
   if(f)
    return m;
  }
 }

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

PKU Judge Online 1338 Ugly Numbers

■1338 Ugly Numbers

□Problem
素因数が2,3,5のみである自然数をugly numberと呼ぶ．n個目のugly numberを表示せよ．

□Solution
n≦1500であるので，先に生成しておけばよい．

□Code(かなり適当です)

view plainprint?

1. package p1338;  
2.   
3. import java.util.*;  
4. import java.lang.*;  
5. import java.math.*;  
6. import java.io.*;  
7.   
8. import static java.lang.Math.*;  
9. import static java.util.Arrays.*;  
10.   
11. public class Main{  
12.   
13.  Scanner sc=new Scanner(System.in);  
14.   
15.  final int INF=Integer.MAX_VALUE;  
16.  final double EPS=1e-9;  
17.   
18.  void run(){  
19.   LinkedList<Long> list=new LinkedList<Long>();  
20.   long r5=1;  
21.   for(int k=0; k<14; k++){  
22.    if(r5>1000000000)  
23.     break;  
24.    long r3=1;  
25.    for(int j=0; j<19+1; j++){  
26.     if(r5*r3>1000000000)  
27.      break;  
28.     long r2=1;  
29.     for(int i=0; i<31; i++){  
30.      if(r2*r3*r5>1000000000)  
31.       break;  
32.      list.add(r2*r3*r5);  
33.      r2*=2;  
34.     }  
35.     r3*=3;  
36.    }  
37.    r5*=5;  
38.   }  
39.   Long[] a=list.toArray(new Long[0]);  
40.   sort(a);  
41.   for(;;){  
42.    int m=sc.nextInt();  
43.    if(m==0)  
44.     break;  
45.    println(a[m-1]+"");  
46.   }  
47.  }  
48.   
49.  boolean ugly(int n){  
50.   while(n%2==0)  
51.    n/=2;  
52.   while(n%3==0)  
53.    n/=3;  
54.   while(n%5==0)  
55.    n/=5;  
56.   return n==1;  
57.  }  
58.   
59.  void print(String s){  
60.   System.out.print(s);  
61.  }  
62.   
63.  void println(String s){  
64.   System.out.println(s);  
65.  }  
66.   
67.  public static void main(String[] args){  
68.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
69.   new Main().run();  
70.  }  
71. }  

package p1338;

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

 final int INF=Integer.MAX_VALUE;
 final double EPS=1e-9;

 void run(){
  LinkedList<Long> list=new LinkedList<Long>();
  long r5=1;
  for(int k=0; k<14; k++){
   if(r5>1000000000)
    break;
   long r3=1;
   for(int j=0; j<19+1; j++){
    if(r5*r3>1000000000)
     break;
    long r2=1;
    for(int i=0; i<31; i++){
     if(r2*r3*r5>1000000000)
      break;
     list.add(r2*r3*r5);
     r2*=2;
    }
    r3*=3;
   }
   r5*=5;
  }
  Long[] a=list.toArray(new Long[0]);
  sort(a);
  for(;;){
   int m=sc.nextInt();
   if(m==0)
    break;
   println(a[m-1]+"");
  }
 }

 boolean ugly(int n){
  while(n%2==0)
   n/=2;
  while(n%3==0)
   n/=3;
  while(n%5==0)
   n/=5;
  return n==1;
 }

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

PKU Judge Online 1316 Self Numbers

■1316 Self Numbers

□Problem
自然数nに対し，d(n)をn+(各桁の総和)と定義する．例えば，d(75)=75+7+5=87．n=d(m)となるmが存在しないnをself-numberと呼ぶ．10000以下のself-numberを全て表示せよ．

□Solution
やるだけ．

□Code

view plainprint?

1. package p1316;  
2.   
3. import java.util.*;  
4. import java.lang.*;  
5. import java.math.*;  
6. import java.io.*;  
7.   
8. import static java.lang.Math.*;  
9. import static java.util.Arrays.*;  
10.   
11. public class Main{  
12.   
13.     Scanner sc=new Scanner(System.in);  
14.   
15.     final int INF=Integer.MAX_VALUE;  
16.     final double EPS=1e-9;  
17.   
18.     void run(){  
19.         int n=10000;  
20.         int[] a=new int[n];  
21.         for(int i=1; i<n; i++){  
22.             int m=i;  
23.             int s=i;  
24.             while(m!=0){  
25.                 s+=m%10;  
26.                 m/=10;  
27.             }  
28.             if(s<n)  
29.                 a[s]=1;  
30.         }  
31.         for(int i=1; i<n; i++)  
32.             if(a[i]==0)  
33.                 println(i+"");  
34.     }  
35.   
36.     void print(String s){  
37.         System.out.print(s);  
38.     }  
39.   
40.     void println(String s){  
41.         System.out.println(s);  
42.     }  
43.   
44.     public static void main(String[] args){  
45.         // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
46.         new Main().run();  
47.     }  
48. }  

package p1316;

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

    final int INF=Integer.MAX_VALUE;
    final double EPS=1e-9;

    void run(){
        int n=10000;
        int[] a=new int[n];
        for(int i=1; i<n; i++){
            int m=i;
            int s=i;
            while(m!=0){
                s+=m%10;
                m/=10;
            }
            if(s<n)
                a[s]=1;
        }
        for(int i=1; i<n; i++)
            if(a[i]==0)
                println(i+"");
    }

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

PKU Judge Online 1163 The Triangle

■1163 The Triangle

□Problem
ピラミッド状になっている数字がある．

    7
   3 8
  8 1 0
 2 7 4 4
4 5 2 6 5

このピラミッドを一番上(ここでは7)から左下/右下へたどって行き，総和を取る．この総和の最大値を出力せよ．この例では，30(7->3->8->7->5)が最大値．

□Solution
下からDPしていくだけ．

□Code

view plainprint?

1. package p1163;  
2.   
3. import java.util.*;  
4. import java.lang.*;  
5. import java.math.*;  
6. import java.io.*;  
7.   
8. import static java.lang.Math.*;  
9. import static java.util.Arrays.*;  
10.   
11. public class Main{  
12.   
13.     Scanner sc=new Scanner(System.in);  
14.   
15.     final int INF=Integer.MAX_VALUE;  
16.     final double EPS=1e-9;  
17.   
18.     void run(){  
19.         int n=sc.nextInt();  
20.         int[][] a=new int[n][n];  
21.         for(int j=0; j<n; j++)  
22.             for(int i=0; i<j+1; i++)  
23.                 a[j][i]=sc.nextInt();  
24.   
25.         for(int j=n-2; j>=0; j--)  
26.             for(int i=0; i<j+1; i++)  
27.                 a[j][i]+=max(a[j+1][i], a[j+1][i+1]);  
28.         println(a[0][0]+"");  
29.     }  
30.   
31.     void print(String s){  
32.         System.out.print(s);  
33.     }  
34.   
35.     void println(String s){  
36.         System.out.println(s);  
37.     }  
38.   
39.     public static void main(String[] args){  
40.         // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
41.         new Main().run();  
42.     }  
43. }  

package p1163;

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

    final int INF=Integer.MAX_VALUE;
    final double EPS=1e-9;

    void run(){
        int n=sc.nextInt();
        int[][] a=new int[n][n];
        for(int j=0; j<n; j++)
            for(int i=0; i<j+1; i++)
                a[j][i]=sc.nextInt();

        for(int j=n-2; j>=0; j--)
            for(int i=0; i<j+1; i++)
                a[j][i]+=max(a[j+1][i], a[j+1][i+1]);
        println(a[0][0]+"");
    }

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

PKU Judge Online 1013 Counterfeit Dollar

■1013 Counterfeit Dollar

□Problem
12枚の銀貨があり，その内の1つは偽物である．偽物と本物とは重さが違うが，軽いか重いかはわからない．あなたは，天秤を3回用いて幾つかの銀貨の重さを比較し，左の皿に乗せたn枚，右の皿に乗せたn枚，右の皿が上がるor下がるor変わらない，という情報を得た．これより，偽物の銀貨を探し出し，かつ，それが本物より軽いか重いかを判定せよ．

□Solution
解は1つのみある，という制約があるため，12枚の銀貨それぞれが軽いor重い偽物だと想定し，与えられた情報にマッチするか判定するだけ．

□Code

view plainprint?

1. package p1013;  
2.   
3. import java.util.*;  
4. import java.lang.*;  
5. import java.math.*;  
6. import java.io.*;  
7.   
8. import static java.lang.Math.*;  
9. import static java.util.Arrays.*;  
10.   
11. public class Main{  
12.   
13.     Scanner sc;  
14.   
15.     final int INF=Integer.MAX_VALUE;  
16.     final double EPS=1e-9;  
17.   
18.     void run(){  
19.         sc=new Scanner(System.in);  
20.         int n=sc.nextInt();  
21.         int[] a=new int[12];  
22.         for(int t=0; t<n; t++){  
23.             Case[] cases=new Case[3];  
24.             for(int j=0; j<3; j++){  
25.                 cases[j]=new Case();  
26.                 String s=sc.next();  
27.                 for(char c : s.toCharArray())  
28.                     cases[j].left.add(c-'A');  
29.                 s=sc.next();  
30.                 for(char c : s.toCharArray())  
31.                     cases[j].right.add(c-'A');  
32.                 s=sc.next();  
33.                 if(s.equals("up"))  
34.                     cases[j].res=-1;  
35.                 else if(s.equals("down"))  
36.                     cases[j].res=1;  
37.                 else  
38.                     cases[j].res=0;  
39.             }  
40.             fill(a, 2);  
41.             for(int j=0; j<24; j++){  
42.                 int coin=j/2;  
43.                 // heavy  
44.                 if(j%2==0)  
45.                     a[coin]=3;  
46.                 // light  
47.                 else  
48.                     a[coin]=1;  
49.                 boolean f=true;  
50.                 for(Case c : cases){  
51.                     int leftSum=0, rightSum=0;  
52.                     for(int i : c.left)  
53.                         leftSum+=a[i];  
54.                     for(int i : c.right)  
55.                         rightSum+=a[i];  
56.                     if(leftSum>rightSum){  
57.                         if(c.res!=-1){  
58.                             f=false;  
59.                             break;  
60.                         }  
61.                     }else if(leftSum<rightSum){  
62.                         if(c.res!=1){  
63.                             f=false;  
64.                             break;  
65.                         }  
66.                     }else{  
67.                         if(c.res!=0){  
68.                             f=false;  
69.                             break;  
70.                         }  
71.                     }  
72.                 }  
73.                 if(f){  
74.                     println((char)(coin+'A')  
75.                             +" is the counterfeit coin and it is "  
76.                             +new String[]{"heavy", "light"}[j%2]+".");  
77.                     break;  
78.                 }  
79.                 a[coin]=2;  
80.             }  
81.         }  
82.     }  
83.   
84.     class Case{  
85.         LinkedList<Integer> left=new LinkedList<Integer>();  
86.         LinkedList<Integer> right=new LinkedList<Integer>();  
87.         // right  
88.         // up=-1, down=1, even=0  
89.         int res;  
90.     }  
91.   
92.     void print(String s){  
93.         System.out.print(s);  
94.     }  
95.   
96.     void println(String s){  
97.         System.out.println(s);  
98.     }  
99.   
100.     public static void main(String[] args){  
101.         // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
102.         new Main().run();  
103.     }  
104. }  

package p1013;

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;

    final int INF=Integer.MAX_VALUE;
    final double EPS=1e-9;

    void run(){
        sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] a=new int[12];
        for(int t=0; t<n; t++){
            Case[] cases=new Case[3];
            for(int j=0; j<3; j++){
                cases[j]=new Case();
                String s=sc.next();
                for(char c : s.toCharArray())
                    cases[j].left.add(c-'A');
                s=sc.next();
                for(char c : s.toCharArray())
                    cases[j].right.add(c-'A');
                s=sc.next();
                if(s.equals("up"))
                    cases[j].res=-1;
                else if(s.equals("down"))
                    cases[j].res=1;
                else
                    cases[j].res=0;
            }
            fill(a, 2);
            for(int j=0; j<24; j++){
                int coin=j/2;
                // heavy
                if(j%2==0)
                    a[coin]=3;
                // light
                else
                    a[coin]=1;
                boolean f=true;
                for(Case c : cases){
                    int leftSum=0, rightSum=0;
                    for(int i : c.left)
                        leftSum+=a[i];
                    for(int i : c.right)
                        rightSum+=a[i];
                    if(leftSum>rightSum){
                        if(c.res!=-1){
                            f=false;
                            break;
                        }
                    }else if(leftSum<rightSum){
                        if(c.res!=1){
                            f=false;
                            break;
                        }
                    }else{
                        if(c.res!=0){
                            f=false;
                            break;
                        }
                    }
                }
                if(f){
                    println((char)(coin+'A')
                            +" is the counterfeit coin and it is "
                            +new String[]{"heavy", "light"}[j%2]+".");
                    break;
                }
                a[coin]=2;
            }
        }
    }

    class Case{
        LinkedList<Integer> left=new LinkedList<Integer>();
        LinkedList<Integer> right=new LinkedList<Integer>();
        // right
        // up=-1, down=1, even=0
        int res;
    }

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

PKU Judge Online 1001 Exponentiation

■1001 Exponentiation

□Problem
Rⁿを計算せよ．
0.0<R<99.999
0<n<=25

□Solution
BigDecimal無限精度モード+正規表現 -> ^q^

□Code

view plainprint?

1. package p1001;  
2.   
3. import java.util.*;  
4. import java.lang.*;  
5. import java.math.*;  
6. import java.io.*;  
7.   
8. import static java.lang.Math.*;  
9. import static java.util.Arrays.*;  
10.   
11. public class Main{  
12.   
13.     Scanner sc;  
14.   
15.     static final int INF=Integer.MAX_VALUE;  
16.     static final double EPS=1e-9;  
17.   
18.     void run(){  
19.         sc=new Scanner(System.in);  
20.         for(; sc.hasNext();){  
21.             BigDecimal r=sc.nextBigDecimal();  
22.             int n=sc.nextInt();  
23.             String ans=r.pow(n, MathContext.UNLIMITED).toPlainString()  
24.                     .replaceAll("^0*|[.]?0*$", "");  
25.             println(ans);  
26.         }  
27.         sc.close();  
28.     }  
29.   
30.     void print(String s){  
31.         System.out.print(s);  
32.     }  
33.   
34.     void println(String s){  
35.         System.out.println(s);  
36.     }  
37.   
38.     public static void main(String[] args){  
39.         new Main().run();  
40.     }  
41. }  

package p1001;

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;

    static final int INF=Integer.MAX_VALUE;
    static final double EPS=1e-9;

    void run(){
        sc=new Scanner(System.in);
        for(; sc.hasNext();){
            BigDecimal r=sc.nextBigDecimal();
            int n=sc.nextInt();
            String ans=r.pow(n, MathContext.UNLIMITED).toPlainString()
                    .replaceAll("^0*|[.]?0*$", "");
            println(ans);
        }
        sc.close();
    }

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

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

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

Project Euler

problem 107
最小全域木．終了．

problem 205
[1,4]の四面体サイコロ9つと，[1,6]の立方体サイコロ6つでゲームを行う．それぞれの合計値を比較し，大きい方が勝ちとする．前者が勝つ確率は幾らか．
それぞれについて，0~36がそれぞれ何回出現するか数えて比較するだけ．

100問解いたので，やっとこさLevel 3になりました．

TopCoder Member SRM 481

SRM 481(9/9 20:00~22:00)

久しぶりのSRM．今回は，とりあえずEasy正答を目標に．

■ChickenOracle(Div1 Easy)

□Problem
あなたは，"卵が先か鶏が先か"問題の答えを知りたい．そんな時oracleは現れた．
しかし，あなたがどんなに尋ねても，oracleは答えを教えてくれない．その代わり，n人には既に答えを教えた"という．そこであなたは，そのn人に答えを尋ねてみたところ，eggCount人は"卵が先だ"と言い，残りのn-eggCount人は"鶏が先だ"と言う．困ったあなたはもう一度oracleに尋ねたところ，"lieCount人には嘘の答えを教えた．更にliarCount人は，あなたに(oracleが教えた)答えと反対の答えを言った"とのこと．これらの情報から，oracleの本当の答えを推測せよ．
返り値
"卵が先" -> "The egg"
"鶏が先" -> "The chicken"
どちらもあり得る -> "Ambiguous"
どちらもありえない -> "The oracle is a lie"

場合分けを沢山すれば解けるとは思うのですが，難しかったので，愚直にループを回しました．しかし，↓の回答に辿りつくまでに2回もResubmitしてしまった為，Scoreが75.0pになってしまいました．

□Code

view plainprint?

1. import java.util.*;  
2. import java.math.*;  
3. import java.lang.*;  
4.   
5. public class ChickenOracle{  
6.     public String theTruth(int n, int eggCount, int lie, int liar){  
7.         int e=eggCount;  
8.         int c=n-eggCount;  
9.   
10.         boolean ef=false;  
11.         boolean cf=false;  
12.           
13.         for(int i=0;i<=lie;i++){  
14.             int l1=i;  
15.             int l2=lie-l1;  
16.             int e1=e-l1;  
17.             int c1=c-l2;  
18.             if(e1<0||c1<0)  
19.                 continue;  
20.             e1+=l2;  
21.             c1+=l1;  
22.             if(e1==liar) cf=true;  
23.             if(c1==liar) ef=true;  
24.         }  
25.           
26.         if(cf&&ef) return "Ambiguous";  
27.         else if(cf)return "The chicken";  
28.         else if(ef)return "The egg";  
29.         else       return "The oracle is a lie";  
30.     }  
31. }  

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

public class ChickenOracle{
    public String theTruth(int n, int eggCount, int lie, int liar){
        int e=eggCount;
        int c=n-eggCount;

        boolean ef=false;
        boolean cf=false;
        
        for(int i=0;i<=lie;i++){
            int l1=i;
            int l2=lie-l1;
            int e1=e-l1;
            int c1=c-l2;
            if(e1<0||c1<0)
                continue;
            e1+=l2;
            c1+=l1;
            if(e1==liar) cf=true;
            if(c1==liar) ef=true;
        }
        
        if(cf&&ef) return "Ambiguous";
        else if(cf)return "The chicken";
        else if(ef)return "The egg";
        else       return "The oracle is a lie";
    }
}

■Challenge
一人，自分が陥っていたミスと同様のことをしていた人がいたので撃墜(+50)．
もう一人，間違ってそうだからとチャレンジしたが撃墜失敗(-25)．

■Result
○×× 50 -25
100.0p

■Rating
1282 -> 1339

とりあえず1300まで上昇．どうにか次回もRatingを上げたいものです．

Project Euler

problem 59
XORにより暗号化された文から平文を推測する問題．かなり適当に解いた．

problem 89
与えられたローマ数字を最小文字数で表す問題．文字の先読みをして適当に解く．

専門書を買う

Prologへの入門(PrologとAI)
プログラミングコンテストチャレンジブック

Prologの技芸 4.2節の練習問題

(1)

挿入ソート
sort([3,1,2],Ys)
    sort([1,2],Zs1)
        sort([2],Zs2)
            sort([],Zs3)        {Zs3=[]}
                true
            insert(2,[],Zs2)    {Zs2=[2]}
                true
        insert(1,[2],Zs1)       {Zs1=[2|Zs4]}
            1>2
                fail
        insert(1,[2],Zs1)       {Zs1=[1,2|[]]}
            1=<2
                true
    insert(3,[1,2],Ys)          {Ys=[1|Ys1]}
        3>1
            true
        insert(3,[2],Ys1)       {Ys1=[2|Ys2]}
            3>2
                true
            insert(3,[],Ys2)    {Ys2=[3]}
                true

クイックソート
sort([3,1,2],Ys)
    partition([1,2],3,Ls,Bs)        {Ls=[1|Ls1]}
        1 =< 3
            true
        partition([2],3,Ls1,Bs)     {Ls1=[2|Ls2]}
            2 =< 3
                true
            partition([],3,Ls2,Bs)  {Ls2=[], Bs=[]}
                true
    sort([1,2],Ls3)
        partition([2],1,Ls4,Bs1)    {Ls4=[2|Ls5]}
            2 =< 1
                fail
        partition([2],1,Ls4,Bs1)    {Bs1=[2|Bs2]}
            2 > 1
                true
            partition([],1,Ls4,Bs2) {Ls4=[], Bs2=[]}
                true
        sort([],Ls5)                {Ls5=[]}
            true
        sort([2],Bs3)
            partition([],2,Ls6,Bs4) {Ls6=[], Bs4=[]}
                true
            sort([],Ls7)            {Ls7=[]}
                true
            sort([],Bs5)            {Bs5=[]}
                true
            append([],[2],Bs3)      {Bs3=[2]}
                true
        append([],[1,2],Ls3)        {Ls3=[1,2]}
            true
    sort([],Bs6)                    {Bs6=[]}
        true
    append([1,2],[3],Ys)            {Ys=[1,2,3]}
        true

(2)

derivative(3*sin(x)-4*cos(x),x,D)   {D=0}
    constant(3*sin(x)-4*cos(x))
        integer(3*sin(x)-4*cos(x))
            fail
derivative(3*sin(x)-4*cos(x),x,D)   {D=DF-DG}
    derivative(3*sin(x),x,DF)       {DF=0}
        constant(3*sin(x))
            integer(3*sin(x))
                fail
    derivative(3*sin(x),x,DF)       {DF=3*DG1+DF1*sin(x)}
        derivative(3,x,DF1)         {DF1=0}
            constant(3)
                integer(3)
                    true
        derivative(sin(x),x,DG1)    {DG1=0}
            constant(sin(x))
                integer(sin(x))
                    fail
        derivative(sin(x),x,DG1)    {DG1=cos(x)}
            true
    derivative(4*cos(x),x,DG)       {DG=0}
        constant(4*cos(x))
            integer(4*cos(x))
                fail
    derivative(4*cos(x),x,DG)       {DG=4*DG1+DF1*cos(x)}
        derivative(4,x,DF1)         {DF1=0}
            constant(4)
                integer(4)
                    true
        derivative(cos(x),x,DG1)    {DG1=0}
            constant(cos(x))
                integer(cos(x))
                    fail
        derivative(cos(x),x,DG1)    {DG1=-sin(x)}
            true

Prologの技芸 4.1節の練習問題

(1)

X=b
Xs=[]
Ys=[c,d]
L=[b|Zs]

(2)

N=s(0)
A=a
B=b
C=c
Ms=Xs

Prologの技芸 3.5節の練習問題

(1)

% arithmetic_sum(A + B) :-
%  算術和A+Bは，正規化されている．すなわちAが定数で，
%  Bが算術和の正規表現となっている形式A+B．
:- op(600, xfy, +).
arithmetic_sum(A + B) :- atomic(A), arithmetic_sum(B).
arithmetic_sum(A) :- atomic(A).

演算子定義

:- op(500, fy,~).
:- op(550,xfy,&).
:- op(600,xfy,'|').

(2)

bool(true).
bool(false).
bool(X & Y) :- bool(X), bool(Y).
bool(X | Y) :- bool(X), bool(Y).
bool(~X) :- bool(X).

(3)

% 和積標準形(選言の連言)
cnf(F1 & F2) :- disjunctive(F1), cnf(F2).
cnf(F) :- disjunctive(F).
% 選言
disjunctive(F1 | F2) :- atomic_formula(F1), disjunctive(F2).
disjunctive(F) :- atomic_formula(F).
% 連言
conjunctive(F1 & F2) :- atomic_formula(F1), conjunctive(F2).
conjunctive(F) :- atomic_formula(F).
% リテラル
atomic_formula(X) :- atomic(X).
atomic_formula(~X) :- atomic(X).

(4)

% negation_inwards(F1,F2) :-
%  F2は，論理式F1に現れる否定を
%  全て連言や選言の内側に移し変えて得られる論理式である．
negation_inwards(F1 & F2,G1 & G2) :-
 negation_inwards(F1,G1), negation_inwards(F2,G2).
negation_inwards(F1 | F2,G1 | G2) :-
 negation_inwards(F1,G1), negation_inwards(F2,G2).
negation_inwards(~(F1 & F2),G1 | G2) :-
 negation_inwards(~F1,G1), negation_inwards(~F2,G2).
negation_inwards(~(F1 | F2),G1 & G2) :-
 negation_inwards(~F1,G1), negation_inwards(~F2,G2).
negation_inwards(~ ~F,G) :- negation_inwards(F,G).
negation_inwards(F,F) :- atomic_formula(F).

Project Euler

problem 70
1<n<10において，10進数で表したφ(n)がnの並び替えになっているものの内，n/φ(n)が最大となるnを求めよ，という問題．
φ(n)の計算が予想以上に遅く，苦戦．最後はマシンパワーに頼った．

problem 80
1≦n≦100において，√n(ただし√nは無理数)の上位100桁をそれぞれ足しあわせた合計を求めよ，という問題．
BigDecimalの精度をMathContext.UNLIMITED(無制限)に設定し，愚直なループで√nを求めた．

Prologの技芸 3.4節の練習問題

(1)

% subtree(S,T) :-
%  SはTの部分木である．
subtree(tree(X,L,R),tree(_,Left,_)) :-
 subtree(tree(X,L,R),Left).
subtree(tree(X,L,R),tree(_,_,Right)) :-
 subtree(tree(X,L,R),Right).
subtree(tree(X,Left,Right),tree(X,Left,Right)).

(2)

% sum_tree(TreeOfIntegers,Sum) :-
%  Sumは整数の木TreeOfIntegersの整数要素の和である．
sum_tree(tree(X,Left,Right),Sum) :-
 sum_tree(Left,SumLeft),
 sum_tree(Right,SumRight),
 Sum is SumLeft+SumRight+X.
sum_tree(void,0).

(3)

% ordered(TreeOfIntegers) :-
%  TreeOfIntegersは整数の順序木である．
% ordered_left(X,Tree) :-
%  XがTreeの根節点よりも小さく，かつTreeが順序木．
% ordered_right(X,Tree) :-
%  XがTreeの根節点よりも小さく，かつTreeが順序木．
ordered(tree(X,Left,Right)) :-
 ordered_left(X,Left),
 ordered(Left),
 ordered_right(X,Right),
 ordered(Right).
ordered(void).
ordered_left(X,tree(Y,Left,Right)) :-
 X > Y, ordered_left(Y,Left), ordered_right(Y,Right).
ordered_right(X,tree(Y,Left,Right)) :-
 X < Y, ordered_left(Y,Left), ordered_right(Y,Right).
ordered_left(_,void).
ordered_right(_,void).

(4)

% tree_insert(X,Tree,Tree1) :-
%  Tree1は順序木Tree中にXを挿入してできる順序木である．
tree_insert(X,tree(X,Left,Right),tree(X,Left,Right)).
tree_insert(X,tree(Y,Left,Right),tree(Y,Left1,Right)) :-
 X < Y, tree_insert(X,Left,Left1).
tree_insert(X,tree(Y,Left,Right),tree(Y,Left,Right1)) :-
 X > Y, tree_insert(X,Right,Right1).
tree_insert(X,void,tree(X,void,void)).

Project Euler

problem 72
problem 73

Prologの技芸 3.3節の練習問題

(1)

% substitute(X,Y,L1,L2) :-
%  L2はL1中に現れるすべてのXをYで置き換えた結果である．
substitute(X,Y,[],[]).
substitute(X,Y,[X|Xs],[Y|Ys]) :- substitute(X,Y,Xs,Ys).
substitute(X,Y,[Z|Xs],[Z|Ys]) :- X \= Z, substitute(X,Y,Xs,Ys).

(2)

% select(X,Xs,Ys) :-
%  Ysは，Xsの最先頭にあるXをXsから削除したリストである．
select(X,[X|Xs],Xs).
select(X,[Y|Ys],[Y|Zs]) :- X \= Y, select(X,Ys,Zs).

(3)

% no_doubles(L1,L2) :-
%  L2はL1から重複する要素をすべて取り除いた結果である．
no_doubles([],[]).
no_doubles([X|Xs],Ys) :- member(X,Xs), !, no_doubles(Xs,Ys).
no_doubles([X|Xs],[X|Ys]) :- no_doubles(Xs,Ys).

(4)

% even_permutation(Xs,Ys) :-
%  YsはリストXsの偶数順列である．
% odd_permutation(Xs,Ys) :-
%  YsはリストXsの奇数順列である．
even_permutation([],[]).
odd_permutation([],[]).
even_permutation([X|Xs],Ys) :- odd_permutation(Xs,Ys).
odd_permutation([X|Xs],[X|Ys]) :- even_permutation(Xs,Ys).

(5)

% margesort(Xs,Ys) :-
%  リストYsはリストXsの順序付けられた順列である．
margesort([],[]).
margesort([X],[X]).
margesort([X1,X2|Xs],Ys) :-
 partition([X1,X2|Xs],Lefts,Rights),
 margesort(Lefts,Ls),
 margesort(Rights,Rs),
 marge(Ls,Rs,Ys).

% partition(Xs,Lefts,Rights) :-
%  LeftsとRightsはXsを大体半分ずつに分けたものである．
partition(Xs,Lefts,Rights) :-
 length(Xs,Length),
 half(Length,L,R),
 prefix(Lefts,Xs),
 length(Lefts,L),
 append(Lefts,Rights,Xs),
 length(Rights,R).

half(X,L,R) :-
 X1 is X/2,
 integer(X1),
 L = X1,
 R = X1.
half(X,L,R) :-
 X1 is (X-1)/2,
 integer(X1),
 L = X1,
 R is X-X1.

% marge(Xs,Ys,Zs) :-
%  ZsはXsとYsを併合したものである．
marge([],Xs,Xs).
marge(Xs,[],Xs).
marge([X|Xs],[Y|Ys],[X|Zs]) :- X < Y, marge(Xs,[Y|Ys],Zs).
marge([X|Xs],[Y|Ys],[Y|Zs]) :- X >= Y, marge([X|Xs],Ys,Zs).

Prologの技芸 3.2節の練習問題

(2)

adjacent(X,Y,[X,Y|_]).
adjacent(X,Y,[_|Zs]) :- adjacent(X,Y,Zs).
last(X,[X]).
last(X,[_|Ys]) :- last(X,Ys).

(5)

% sum(Sum,ListOfIntegers) :-
%  Sumは整数のリストListOfIntegersの要素の和である．

(a) plus/3を使った定義

natural_number(0).
natural_number(s(X)) :- natural_number(X).
plus(0,X,X) :- natural_number(X).
plus(s(X),Y,s(Z)) :- plus(X,Y,Z).
sum_a(0,[]).
sum_a(X,[Y|Ys]) :- sum_a(Z,Ys), plus(Y,Z,X).

(b) 補助述語を使わない定義

sum_b(0,[]).
sum_b(s(X),[s(Y)|Ys]) :- sum_b(X,[Y|Ys]).
sum_b(X,[0|Ys]) :- sum_b(X,Ys).