ABC142 - koga9999の日記

寝てたのでリアタイできず。

F問題の話

閉路が存在しない場合は、-1を出力すればACになります。

閉路が存在する場合、正規の解答ではなく、おそらく-2以下の数値を入力することでもACになってしまいます。

問題文を読む限りでは判定器のバグに思えます。

以下、実際に解いていた時の話。

解説読んだけれど実装がわからず、とりあえずいろいろ調べて閉路検出はなんとなく理解した。

DFSで再帰関数を回し、閉路が見つかったらそれを一時的な回答として保存して終了。

その後、閉路の中の接続点を見つけて小さくしていき、問題の条件を満たせばクリア、というところまできてうまくいかない。

ここで、コンテストは終わっているので、一旦解答を探ってみることにした。

閉路がなかった場合、「-1」、

閉路が存在する場合、「-222」、

を投げることで、閉路を正しく検出しているかどうか確認しようとした。

この時点では、-222はすべての問題においてWAとなることを期待していた。

ところが、予想と違ってACが多すぎる。WAが2つしかない。

いろいろ調べたところ、閉路の検出部分に誤りがあることがわかったので該当箇所を修正した。

その後、閉路がなかった場合「-1」、存在する場合「-99999」を出力する形で提出したところ、AC。

この時点で判定機のバグっぽいなあということをボソっとツイートした。

閉路を短縮する部分の効率が悪かったのでそこらへんを書き直して正規ルートでもACが出せたので終了。Python3とPyPyの速度問題で悩むのもだるいなあという感じがしたのでしばらくはGolangを練習するつもり。