Bestcoder #53

30分遅れて電話をかけたが、そうしないとrankはもっと見どころがいい......
1001 Rikka with Graph
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

/** Aug 29, 2015 7:39:29 PM
 * PrjName:Bc53-01
 * @author Semprathlon
 */
import java.io.*;
import java.util.*;
public class Main {

    /**
     * @param args
     */
    public static void main(String[] args) throws IOException{
        // TODO Auto-generated method stub
        StreamTokenizer in=new StreamTokenizer(new BufferedInputStream(System.in));
        PrintWriter out=new PrintWriter(System.out);
        while(in.nextToken()!=StreamTokenizer.TT_EOF){
            int n=(int)in.nval;
            in.nextToken();
            int m=(int)in.nval;
            boolean has=false;
            //out.println(n+"-"+m);
            for(int i=1;i<=m;i++){
                in.nextToken();
                int u=(int)in.nval;
                in.nextToken();
                int v=(int)in.nval;
                if (u==1&&v==n||u==n&&v==1)
                    has=true;
            }
            if (has)
                out.println(1+" "+n*(n-1)/2);
            else
                out.println(1+" "+1);
        }
        out.flush();
        out.close();
    }
}

点1が点nに直接接続されている場合、距離が最も短い.
1002 Rikka with Tree
異なる点と類似点を同時に満たすには、ノード数が等しく、各ノードからツリールート1までの距離がそれぞれ等しく(すなわち、深さがそれぞれ同じ)、親ノードが異なるノードが存在する.同一深さでのノード交換後に新たな構造が得られるか否かを判断するといえる.ある深さのノード数が1つ以上あると,ほぼ同層交換により新しい構造を得ることができる.

/** Aug 29, 2015 7:59:14 PM
 * PrjName:Bc53-02
 * @author Semprathlon
 */
import java.io.*;
import java.util.*;
public class Main {

    /**
     * @param args
     */
    final static int maxn=2010;
    static Graph G=new Graph(maxn);
    static int[] dep;
    static HashSet st=new HashSet();
    static void bfs(int st){
        Queue que=new LinkedList();
        que.add(st);
        while(!que.isEmpty()){
            int u=que.poll();
            for(int i=G.h[u];i>-1;i=G.edge[i].next){
                int v=G.edge[i].to;
                if (dep[v]>0) continue;
                dep[v]=dep[u]+1;
                que.add(v);
            }
        }
    }
    public static void main(String[] args) throws IOException{
        // TODO Auto-generated method stub
        StreamTokenizer in=new StreamTokenizer(new BufferedInputStream(System.in));
        PrintWriter out=new PrintWriter(System.out);
        while(in.nextToken()!=StreamTokenizer.TT_EOF){
            int n=(int)in.nval;
            G.clear();
            dep=new int[n+1];
            dep[1]=1;
            for(int i=1;iint u=(int)in.nval;
                in.nextToken();
                int v=(int)in.nval;
                G.add(u, v);
                G.add(v, u);
            }
            bfs(1);
            boolean ans=true;
            st.clear();
            for(int i=1;i<=n;i++)
                if (st.contains(dep[i])){
                    ans=false;
                    break;
                }
                else
                    st.add(dep[i]);
            out.println(ans?"YES":"NO");
        }
        out.flush();
        out.close();
    }

}
class Edge{
    int to,next;
    Edge(int _u,int _v){
        to=_u;next=_v;
    }
}
class Graph{
    int[] h;
    int sz;
    Edge[] edge;
    Graph(int size){
        sz=size;
        h=new int[sz+1];
        edge=new Edge[sz+1];
        Arrays.fill(h, -1);
        h[0]=0;
    }
    void clear(){
        h=new int[sz+1];
        edge=new Edge[sz+1];
        Arrays.fill(h, -1);
        h[0]=0;
    }
    void add(int u,int v){
        edge[h[0]]=new Edge(v,h[u]);
        h[u]=h[0]++;
    }
}

しかし、間違っています.いくつかのケースを適切に列挙すると,木の深さが2しかない場合,それは常に特殊であることが分かった.しかし、この判断を加えるとまだ足りない.さらに例を挙げると,ツリー上の非最下層に1つ以上のノードがあれば,新しい構造に変換できることが分かった.

/** Aug 29, 2015 7:59:14 PM
 * PrjName:Bc53-02
 * @author Semprathlon
 */
import java.io.*;
import java.util.*;
public class Main {

    /**
     * @param args
     */
    final static int maxn=2010;
    static Graph G=new Graph(maxn);
    static int[] dep;
    static HashSet st=new HashSet();
    static void bfs(int st){
        Queue que=new LinkedList();
        que.add(st);
        while(!que.isEmpty()){
            int u=que.poll();
            for(int i=G.h[u];i>-1;i=G.edge[i].next){
                int v=G.edge[i].to;
                if (dep[v]>0) continue;
                dep[v]=dep[u]+1;
                que.add(v);
            }
        }
    }
    public static void main(String[] args) throws IOException{
        // TODO Auto-generated method stub
        StreamTokenizer in=new StreamTokenizer(new BufferedInputStream(System.in));
        PrintWriter out=new PrintWriter(System.out);
        while(in.nextToken()!=StreamTokenizer.TT_EOF){
            int n=(int)in.nval;
            G.clear();
            dep=new int[n+1];
            dep[1]=1;
            for(int i=1;iint u=(int)in.nval;
                in.nextToken();
                int v=(int)in.nval;
                G.add(u, v);
                G.add(v, u);
            }
            bfs(1);
            boolean ans=true;
            st.clear();
            int maxd=0;
            for(int i=1;i<=n;i++)
                maxd=Math.max(dep[i], maxd);
            for(int i=1;i<=n;i++)
                if (st.contains(dep[i])){
                    if (dep[i]false;
                        break;
                    }
                }
                else
                    st.add(dep[i]);
            if (maxd<3)
                ans=true;
            out.println(ans?"YES":"NO");
        }
        out.flush();
        out.close();
    }

}
class Edge{
    int to,next;
    Edge(int _u,int _v){
        to=_u;next=_v;
    }
}
class Graph{
    int[] h;
    int sz;
    Edge[] edge;
    Graph(int size){
        sz=size;
        h=new int[sz+1];
        edge=new Edge[sz+1];
        Arrays.fill(h, -1);
        h[0]=0;
    }
    void clear(){
        h=new int[sz+1];
        edge=new Edge[sz+1];
        Arrays.fill(h, -1);
        h[0]=0;
    }
    void add(int u,int v){
        edge[h[0]]=new Edge(v,h[u]);
        h[u]=h[0]++;
    }
}

これは、「1本の木が独特で、それぞれの深さにある任意の点数が1 1 1 1 1...1 xである場合」という問題解と一致する(個人的にはこの形態を「ほうき状」と呼ぶ)