プログラミングを上達させたい

情報学専攻の大学院→放送局でCMの営業など@大阪→舞台俳優&IT営業@東京

AtCoderRegularContest030に参加しました

久々の更新となりました。

さて、タイトルの通り、ARC030に参加してきました。
4問あるうち、2問目までしか解けませんでした。
とある強い人曰く、「グラフが初心者の最後の関門」とのこと。
初心者らしく、3問目がちっともでした。
他の上位の方を見てみると、やはり3問目までは結構速く通していて、経験の差を感じました。


反省はこのくらいにして、とりあえず解けたとこまでのコードを。
問題A
なんかこう、グラフの問題っぽく書いてますが、グラフの頂点数をnとすると、一個ずつにバラバラにしたら、最大でn/2個の連結成分に分けられますね。というわけで、kがn/2より大きいかどうかをチェックすればよいです。

import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
 
                int n = sc.nextInt();
                int k = sc.nextInt();
 
                if(2 * k <= n){
        	       System.out.println("YES");
                }else{
                	System.out.println("NO");
                }
        }
}

次、問題B。僕が解けたのはここまでです。
これは、僕が最近やった勉強の集大成的な感じのコードになったので、嬉しかったです。順序集合とか、そういうの!まぁ、もっと簡潔に書けたかもしれませんが。
方針として、
・根付き木を作る
・葉がどれかを求める
・この木から、取り除いてもよい部分(=宝石が含まれない部分)を求める。具体的には、各葉の、より深い順に見ていき、
 ・宝石があるなら、そこで終わり
 ・宝石がないなら、そのノードを取り除く部分として印をつけ、その親のノードを見る
という感じです。

import java.util.*;
 
class oneNodeList{
  LinkedList<Integer> list = new LinkedList<Integer>();
 
  public void add(int a){
    list.add(a);
  }
  public int poll(){
    int a = list.poll();
    return a;
  }
  public int peek(){
    int a = list.peek();
    return a;
  }
  public boolean isEmpty(){
    return list.isEmpty();
  } 
}
 
class node implements Comparable{
        int index;
        int depth;
 
        public int compareTo(Object other){
        node othernode = (node)other;
        return othernode.depth - depth;
  }
}
 
public class Main {
        public static void main(String[] args){
                Scanner sc = new Scanner(System.in);
 
        int n = sc.nextInt();
        int start = sc.nextInt() - 1;
 
        boolean[] ruby = new boolean[n];
        for(int i = 0; i < n; i++){
                if(sc.nextInt() == 1){
                        ruby[i] = true;
                }else{
                        ruby[i] = false;
                }
        }
 
        oneNodeList[] rinsetsu = new oneNodeList[n];
        for(int i = 0; i < n; i++){
                rinsetsu[i] = new oneNodeList();
        }
 
        for(int i = 1; i < n; i++){
                int kata = sc.nextInt() - 1;
                int moukata = sc.nextInt() - 1;
                rinsetsu[kata].add(moukata);
                rinsetsu[moukata].add(kata);
        }
 
        int[][] netsukigi = new int[n][2];
        //netsukigi[i][0] には深さを、[i][1]には親のノードを入れる。
        LinkedList<Integer> indexqueue = new LinkedList<Integer>();
        LinkedList<Integer> depthqueue = new LinkedList<Integer>();
        boolean[] check = new boolean[n];
        boolean[] isha = new boolean[n];
        //isha[] は、葉かどうかを判定するもの。
        for(int i = 0; i < n; i++){
                check[i] = false;
                isha[i] = false;
        }
        indexqueue.add(start);
        depthqueue.add(0);
        netsukigi[start][0] = 0;
        netsukigi[start][1] = -1;
        check[start] = true;
        while(!indexqueue.isEmpty()){
                int nowfrom = indexqueue.poll();
                int nowdepth = depthqueue.poll();
                boolean ha = true;
                while(!rinsetsu[nowfrom].isEmpty()){
                        int nowto = rinsetsu[nowfrom].poll();
                        if(!check[nowto]){
                                indexqueue.add(nowto);
                                depthqueue.add(nowdepth + 1);
                                netsukigi[nowto][0] = nowdepth + 1;
                                netsukigi[nowto][1] = nowfrom;
                                check[nowto] = true;
                                ha = false;
                        }
                }
                if(ha){
                        isha[nowfrom] = true;
                }
        }
 
        PriorityQueue<node> nodequeue = new PriorityQueue<node>();
        // System.out.println("ha is");
        for(int i = 0; i < n; i++){
                if(isha[i]){
                        // System.out.println(i);
                        node nownode = new node();
                        nownode.index = i;
                        nownode.depth = netsukigi[i][0];
                        nodequeue.add(nownode);
                }
        }
 
        boolean[] usecheck = new boolean[n];
        for(int i = 0; i < n; i++){
                usecheck[i] = true;
        }
 
        boolean[] stop = new boolean[n];
        for(int i = 0; i < n; i++){
                stop[i] = false;
        }
 
        while(!nodequeue.isEmpty()){
                node nownode = nodequeue.poll();
                if(ruby[nownode.index] || stop[nownode.index]){
                        int nowind = netsukigi[nownode.index][1];
                        while(nowind >= 0){
                                stop[nowind] = true;
                                nowind = netsukigi[nowind][1];
                        }
                        continue;
                }else{
                        usecheck[nownode.index] = false;
                        int oyaindex = netsukigi[nownode.index][1];
                        node newnode = new node();
                        if(oyaindex < 0){
                                continue;
                        }else{
                                newnode.index = oyaindex;
                                newnode.depth = nownode.depth - 1;
                                nodequeue.add(newnode);
                        }
                }
        }
 
        int count = 0;
        // System.out.println("use is");
        for(int i = 0; i < n; i++){
                if(usecheck[i]){
                        // System.out.println(i);
                        count++;
                }
        }
 
        if(count == 0){count = 1;}
        System.out.println(2 * (count - 1));
        }
}


やっぱグラフとか勉強しなきゃダメですね。
そのうちやります。そのうち。
はいはい。

では、今回はこれで終わりです。