M-SOLUTIONS(2019)-D

問題

atcoder.jp

解けなかった...
これ水で解けないのはさすがにひどい。完全に茶色適正

解法

そもそもこの問題でまず自分が詰まったのが「木構造のデータの持ち方（データ構造）」について。

リアタイではNodeやEdgeといったクラスを作ったりMapやSetを使ったりして試行錯誤しながら2時間椅子を温めてましたが、普通に隣接リストでいいんですね...(隣接行列は空間計算量の制約的にダメってぱっと思い浮かぶのにこっちは思い浮かばない)

他人のコード見てると

List<Integer>[] g=new List[n];
//Set<Integer>[] g=new Set[n];じゃない理由はあるんだろうか...

の形式が一番多いっぽい

次点で

int[][] g=method(n,from[],to[]);//とか(2番手)
Map<Integer,Set<Integer>> tree;//とか
Map<Integer,List<Integer>> tree;//とか
List<List<Integer>> g;//とか

あと次数を

int[] deg;

で持っとくのもいいテクニックだなって思った（小学生並みの感想）（リアタイではNodeが隣接してるノードの番号を示すSetを持ってて.size()で次数を取ってて詰んだ）。

あとwhileなんかで配列やリストにアクセスするとき

int idx=0;
while(hoge()){
    ~~~c[idx++]~~~
}

と自然にやれると良いな。

本質的な解法は単純に木の葉っぱの方からスコアが小さい順に埋めていくだけ。
やり方は思いついてただけに悔しいかんじ。

敗因は上記の「木のデータ構造」とDequeの扱い。

追伸

今JavaGold取ろうとしててその勉強しているけど、言語の詳細を覚えるにつれて競プロっぽい書き方が抜けて行ってる気がする。
ライブラリとか覚えるとどうにかしてそれ使おうとしちゃうんだろうな。