drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ AtCoder AtCoder900点 構築 Greedy Greedy：先に進むほど新たな選択肢が挿入される 決めてから整合性を確認する 最大値や最小値に着目する 葉から考える 木 構築:木 復元 考察：順序を工夫して解く 赤色diff ARC-F 木の問題に対してパスの場合から考える 900 点なので備忘録程度に... 久しぶりに競プロでめちゃくちゃ楽しかった！！！ 2 時間 10 分かかったので本番だったら通せていないけど、どうすればもっと早く解けたのかの反省もこめて。 問題へのリンク 問題概要 以下の条件を満たす 頂点の木を復元せよ。ただし、存在しない場合には -1 と出力せよ。 各頂点 について、その頂点から他の頂点への距離の総和が である 制約 考えたこと こういう構築系では、きっと なにか上手に上手い視点で見ると、木の形があれよあれよと一意に決まるので、最後に整合性を check する という風になるんだろうな...という想定があった。ましてや なので... とか… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2019%2F12%2F15%2F170300" title="AtCoder ARC 103 F - Distance Sums (赤色, 900 点) - けんちょんの競プロ精進記録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn.user.blog.st-hatena.com/default_entry_og_image/80936665/1687765056723440 Hatena Blog https://hatena.blog 2019-12-15 17:03:00 rich https://drken1215.hatenablog.com/entry/2019/12/15/170300 1.0 100%