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上昇は見込めません．