けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

最適化の考察:最適性条件を深く考える

AOJ 1462 Remodeling the Dungeon 2 (ICPC アジア 2024 H) (6D)

ICPC 本番に正解チームの現れなかった難問! 問題へのリンク 問題概要 サイズのグリッドグラフから、いくつかの頂点と辺を削除してできる連結なグラフが与えられる。 このグラフの全域木であって、どの 2 つの葉も、その間の距離が偶数であるものを 1 つ求め…