AtCoder Grand Contest 004:D - Teleporter
問題
https://atcoder.jp/contests/agc004/tasks/agc004_d
制約
考え方
首都 (頂点 ) は自己ループを持たないといけないことは感覚的にすぐわかる。そのとき葉から考えて、高さが 未満の場合はそのまま辺をつけておいて、高さが になる場合は、その辺を首都に向けるように修正することで最小の回数を実現することができる。
実装としては、DFSで葉まで遷移して、そこからさかのぼっていき、高さが になったときに高さを として修正回数を すればよい。
Submission #3865480 - AtCoder Grand Contest 004
どこに着目して考察するべきだったか
根から考えるのではなく、葉から考えてみる。