LoginSignup
1

posted at

AtCoder ABC286-G のグラフを図示してみる

はじめに

ウルシステムズプログラミングコンテスト2023(AtCoder Beginner Contest 286) - AtCoder 2023/01/21 お疲れさまでした。

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

TL;DR

image.png

入力例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 問題に挑む勇気はありませんでした。

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
What you can do with signing up
1