ABC 075: C – Bridge

今日の反省はこの問題。

https://atcoder.jp/contests/abc075/tasks/abc075_c

まあ色々反省点はあるのだが、一番大きな反省点は時間だろう。 解くのに１時間１７分もかかってしまった。ABC-C問題にこれは掛かりすぎだろう。

何故こんなに掛かってしまったかを見るために、いろはすの思考を辿ってみよう。

考察

まず、考察を初めて数分でいろはすは閃く。任意の辺について、それが

「橋でない⇔ループの一部でない」

という事実に。これはこの問題を解くための最も重要なキーと言えるポイントである。

しかし、ここからいろはすの思考は迷走を始める。

橋の本数を数えるにはどうすればよいだろう。 橋の定義より、グラフ全体から橋となる１辺を取り去ると、グラフは２つの連結成分に分かれる。 そのどちらかに含まれる橋をまた取り去ると、この連結成分がさらに２つの連結成分に分かれる。 こう考えると、次の関係が成り立つことが分かる：

「橋の本数＝全ての橋を取り去ったときの連結成分の個数-1」

ここまではまあいい。結局役に立たない考察ではあったが、間違いではない。 しかし、ここからが酷い。

いろはす「先程の考察から、全ての橋を取り去ったときの連結成分の個数はグラフに含まれるループの個数に等しい」←！？ｗｗｗｗｗ

いろはす「つまり・・・・・・こうだっ！！！」

「橋の本数＝グラフに含まれるループの個数-1」（※違います）

そしてコードをガリガリ書いた。サンプル入力を試す。当然合わない。

いろはす「何故だ！？」

いろはすよ。コード書く前にサンプルで考察が合ってるかぐらい確認しようぜ。 親切に図まで書いてあるじゃないか。見たらひと目で違うと分かるだろう。

ここでようやく考察の間違いに気づいたいろはす。 この時点で30分は経っていたと思う。

ここからようやく思考は正しい方向に軌道修正される。 要は、最初の考察を起点に、真面目にループの一部でないような辺を数えるしかないのだ。 どうすれば数えられるかは、比較的すぐに思いついた。 何せ、先程のクソ間違った考察の際、ループを数えるのにDFSを用いていたからである。 これを応用することで、何とか任意の辺がループの一部か、そうでないかを判定するルーチンが書けた。 [このブログは「正解」を書くことが目的ではないので詳細は本家の解説に譲るが、要は出発ノードを保持した状態でDFSを行い、元のノードに戻ってきたらループに含まれる、という方法で判定できる]

まあそんな感じで気づいたらめっちゃ時間経ってました。

https://atcoder.jp/contests/abc075/submissions/4138916

というわけで、本日の教訓

「実装する前に考察が合ってるかサンプルで確認しよう」