blog.bouzuya.net

2022-02-21 ABC239 F - Construct Highway を解いた

デンソークリエイトプログラミングコンテスト2022 ( ABC239 : AtCoder Beginner Contest 239 ) F - Construct Highway を解いた。

問題: https://atcoder.jp/contests/abc239/tasks/abc239_f

本番では解けなかった。 N 頂点 N - 1 辺で連結なので木になることは分かった。入次数・出次数の和は 2 * (N - 1) なのも分かる。 D_i の和が 2 * (N - 1) でない場合は NG 。 DSU (Union-Find) を使って連結成分を調べた。既存の辺が連結済みの頂点を再度追加している場合は NG 。あとは非連結の頂点を結ぶ辺を追加していくだけだったのだけどうまく実装できなかった。

解説: https://atcoder.jp/contests/abc239/editorial/3388

解説によると連結成分ごとに次数の残っている頂点をまとめておき、 1 ものと 2 以上のものを連結し、最後に何も残らないか次数 1 のものが 2 つだけ残っていると良いらしい。解説を読んでからもなかなかうまく実装できなかった。難しい……。

提出: https://atcoder.jp/contests/abc239/submissions/29557047


今日のコミット。