はじめに
ウルシステムズプログラミングコンテスト2023(AtCoder Beginner Contest 286) - AtCoder 2023/01/21 お疲れさまでした。
今回の G 問題は一見難しそうですが、気づくと簡単というものでした。グラフでざっくり図示してみます。
TL;DR
入力例1
以下のグラフが与えられます。
実線を 1 度ずつ通る方法はあるか、という問題です。破線は通らなくても良いし、複数回通っても良いです。
1 → 3 → 4 → 5 → 6 → 4 → 3 → 2 のような経路があります。
破線をつぶす
破線の中は自由に行き来できるということは、破線でつながったノードは一つにまとめて考えられます。
たとえば自由に行き来できる 3,4 のノードをひとつにまとめて、1, 2, 5, 6 行きの 4本の経路が伸びている、と考えられます。
5,6 も同様にまとめられます。まとめると次のようになります。
こうなると普通の一筆書き問題です。 奇数本のエッジが出ているノードは 1, 2 の 2つで、これが始終点となります。 1 → 3,4 → 5,6 → 3,4 → 2 のような経路があります。
入力例2
破線をつぶす
奇数本のエッジが出ているノードは 1,5,6, 2, 3, 4 の 4つです。このノードが 4つ以上ある場合は、一筆書きできません。
実装方針
破線でつながったノードの組を UnionFind に登録していけば、破線をつぶしたノード群が得られます。
このノード群に対して実線のエッジ数をそれぞれ数えます。エッジ数が奇数のノードが 0 個または 2 個なら一筆書きできる、それ以上なら一筆書きできないと答えます。終了。
Rust 解答例: 提出 #38232470 - ウルシステムズプログラミングコンテスト2023(AtCoder Beginner Contest 286)
最後に
コンテスト中に F 問題を飛ばして先に G 問題に挑む勇気はありませんでした。