はじめに

今回の G 問題は一見難しそうですが、気づくと簡単というものでした。グラフでざっくり図示してみます。

TL;DR

以下のグラフが与えられます。
実線を 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 のような経路があります。

奇数本のエッジが出ているノードは 1,5,6, 2, 3, 4 の 4つです。このノードが 4つ以上ある場合は、一筆書きできません。

破線でつながったノードの組を UnionFind に登録していけば、破線をつぶしたノード群が得られます。

このノード群に対して実線のエッジ数をそれぞれ数えます。エッジ数が奇数のノードが 0 個または 2 個なら一筆書きできる、それ以上なら一筆書きできないと答えます。終了。

コンテスト中に F 問題を飛ばして先に G 問題に挑む勇気はありませんでした。