最終更新: 2021-04-30T21:11+0900
「10分間３問早解き」回だったわけなので４問目(D 問題)は時間中に解けなかった。90 分使っても解けなかった。辺がないケースで TLE が避けられなかった。
AC のきっかけはこのツイート。
chokudai(高橋 直大)ナス@chokudai
D問題、非連結ですって言うだけでDiff400くらい落ちそう
chokudai(高橋 直大)ナス@chokudai
非連結ですって言っても落ちないわ（サンプルにあるし）
連結で出題しないと400落ちなさそう。
「連結で出題しないと落ちない
」がよくわからないけど、ともかく、非連結なら問題を分割できるじゃん、と気がつきました。ツイートを読んで初めて気がつきました。
サンプル４つのうち２つが辺がゼロのケースだったんだけど、極端すぎてそれが全体としては非連結なグラフであること、個々の頂点としては最も簡単な連結成分を構成している、ということがわかりませんでした。そんなことってある？
テストケースが公開されていないので、提出前のテストには一直線の木を使っていた。連結成分の数を増やしても、辺の数を増やしても、探索を助ける制約が増えるだけだと思ったので。
しかしまだ TLE。どういう木が嫌か考えると、この提出は次のような入力に弱い。
だけど次のように番号の付け方を変えただけで問題が問題でなくなる。
たぶん頂点を次数でソートしてから DFS をすれば緩和されたと思う(が、AC 提出では違う方法(先読み)をとった)。
ソートするにせよ先読みするにせよ、２番目の問題に対処するには非連結なグラフを連結成分に分割する必要があったが、それをしないまま DFS の処理量を削減する方法を考えていた、というのが失敗に終わったコンテスト中の時間の使い方だった。
DFS の処理順を次数の降順にしたら悪くなりにくいのか、343 ms からタイムが大いに改善した。このムラが DFS の沼であり抜け出せない楽しみなんだよなあ>20201101p02、20201107p01.05。