まず、この問題において、以下のような計算量の悪そうな方針が立ちます。
- ある頂点Vを始点とする。
- VからDFSを行い、条件を満たすサイクルを直接探していく
- サイクルが見つかれば終了、見つからなければ頂点Vを削除し、別の頂点Wを始点として1.に戻る
ここで、Vに着目しているときに、
まず、辺 V->A を選んだとする。すると、 V->X を満たす頂点XはAを除いて行くべきではない。
次に、辺 A->B を選んだとする。すると、 A->Y を満たす頂点YはBを除いて行くべきではない。さらに、Aに突き刺さる Z->A が存在する頂点ZにもVを除いて行くべきではない。
といったことを、フラグ管理で工夫して行うと、枝刈りがたくさん発生して定数倍は相当いいが計算量の悪い解法(僕はこの解法の計算量を正確には見積もれませんでした…もし計算量を正確に見積もれる方がいたらコメントください)ができ、これをO(N)回繰り返すことになります。詳しくは末尾に挙げる僕の実装を参照してください。
何を血迷ったかこの解法はグラフが疎なことも二重辺自己辺がないことも効くのでO(N^3)程度で、しかも頂点削除が絡むのでΣN^2になって定数に1/3が入ったりするのでもしかすると間に合うかもと見積もった僕はこれを実装しましたが、TLE。結果的に実行時間感覚としてこの見積もりはそう誤ってはいませんでしたが。
そこで僕は頂点番号を乱択で付け替えることを考えました。
頂点番号を乱択すると以下のようなメリットが発生します。
- 解が(998,999,1000)のような恣意的なケースでも、解に含まれる最小の頂点番号(=発見するタイミング)の期待値を333まで抑えることができる。(∵サイクルは最低でも3頂点を含む)ここで、頂点番号750あたりまで探索すれば、見落としの可能性を1.5%程度に抑えつつ計算を打ち切れる。
- もしVとして関節点を選ぶことができれば、Vを始点とした探索が終わるタイミングでグラフが2つに分裂して問題のサイズが縮まる。しかも1000辺2000頂点のグラフは思いの外疎なのでこの現象が起こりやすい。こちらもグラフが分裂しにくい恣意的なケースを回避できる。
このような要因から、結果的に定数倍やならし計算量のよいアルゴリズムとなり、結果的にはACできました。計算量が見積もれてないのにACってなんなのでしょうか…
実際末尾のコードと同じものを10提出すると、4回のACが確認できました。
