AtCoder Grand Contest 071

　A一完。

コンテストへのリンク

コンテスト後のツイート

計算量は四乗な気もするけどRUSTで提出するとAC。（PyPyだとTLEなので、もっと高速化できるのだろうけど……）
C サイクルがあってもYesになる条件を考えていた。二部グラフじゃないならYesっぽい！　とか、サイクルの全部の頂点に毛が生えていて欲しい！　とか。

— titia (@titia_til) March 30, 2025

C - Orientable as Desired

　解説AC。解説放送も見た。

　全く惜しくはなかったが、サイクルがあってもYesになる条件を考える、という方針自体は良いのかも。そういうグラフを列挙していけば正しい条件にたどりつけるかもしれない。

　ただ、解法を理解した後も、二重頂点連結成分分解を実装したことがなかったため、自力で実装できなかった。LOWLINKを使った関節点や橋は実装したことがあるので、あと一歩なはずなのだが……。

　とりあえず、二重頂点連結成分分解をChat-GPTに実装してもらいAC。原理は理解したつもりだけど、実装がよく分かっていない。ちゃんと自力で実装しなきゃなぁ。

　ついでに、二重頂点連結成分分解を調べる仮定ででてきたこの問題も解説（放送）ACした。ポリアの数え上げ定理（バーンサイドの補題）はこういうときに使うのか。数え上げパートまでいけたとしても解けなかったと思うので、そこまでいけたら解けるようになりたい。