久々の更新となりました。
さて、タイトルの通り、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)); } }
やっぱグラフとか勉強しなきゃダメですね。
そのうちやります。そのうち。
はいはい。
では、今回はこれで終わりです。