オンサイトで未確認

ukuku09の活動記録。

ACM-ICPC 2018 Asia Yokohama Regional Problem E - Eulerian Flight Tour

問題概要

連結とは限らない $n$ 頂点 $m$ 辺のグラフ $G$ が与えられる。$G$ にいくつか辺を付け足して連結なオイラーグラフにしなさい。多重辺・自己ループは許されない。

制約

  • $3 \le n \le 100$
  • $0 \le m \le \frac{n(n-1)}{2}$

コンテスト中にした考察

以下、入力 $G$ の奇数次数頂点を黒、偶数次数頂点を白と書く。

 

まず「グラフがオイラーグラフ $\iff$ グラフに含まれるすべての頂点の次数が偶数」なので、問題文は「黒の次数を奇数・白の次数を偶数増やして、連結なグラフにしなさい」と言い換えられる。すると、$n$ が奇数のときは完全グラフ(すべての頂点の次数が$n-1$(=偶数))を作ればよいので、$n$ は偶数としてよい。

$G$ が連結な場合は簡単に解けると勘違いしていたので、非連結な場合を考えた。非連結な場合、

  • 連結成分がすべてオイラーグラフの場合
  • 連結成分がすべて非オイラーグラフの場合
  • どちらもある場合

が考えられる。

すべてオイラーグラフの場合が解けると嬉しそう。オイラーグラフが3つ以上ある場合は各オイラーグラフから頂点を1つずつ選んでサイクルを作ればよい。2つの場合、どちらも孤立点でなければそれぞれから適当な2頂点を選んで下図のように繋げばよい。

f:id:ukuku09:20181213130105p:plain
どちらかが孤立点 $x$ の場合、もう一方の連結成分 $C$ の頂点数は $n-1$(=奇数)なので、$C$ の頂点を使って完全グラフを作るとオイラーグラフになる。$C$ が完全グラフでなければ、完全グラフにする過程でどこかの辺に孤立点 $x$ を挿入すると、連結なオイラーグラフが作れる。$C$ が完全グラフの場合、ある $v \in C$ と $x$ とを繋ぐと必ず $v$ の次数が奇数になってしまうので、連結なオイラーグラフを作ることはできない("-1"が答え)。

オイラーグラフと非オイラーグラフがどちらもある場合、オイラーグラフ $C$ を1つ選んである $v \in C$ とすべての非オイラーグラフの黒との間に辺を張って $C^+$ を作ると、黒は必ず偶数個ある(握手補題)ことから、$C^+$ は連結なオイラーグラフになり、全てがオイラーグラフの場合に帰着できる。

オイラーグラフしかない場合、最も奇数次数頂点の少ない連結成分を1つ選んで下図のように繋げばよい(橙は選んだ連結成分の黒の集合、青はそれ以外の連結成分の黒の集合)。これも握手補題から各黒の次数は奇数増える。

f:id:ukuku09:20181213184228p:plain

非連結な場合が解けたので、連結な場合を考える。コンテストではこれが解けずに終了した。

連結な場合の解法

PFN企業見学の待ち時間に聞きました。待ち時間に問題解説が生えるのはPFNだけ!

 

$G$ の補グラフ $G^c$が 黒を奇数個含む連結成分を含む場合(例えばサンプル2)、答えは"-1"。

それ以外の場合、$G^c$ 上で全ての黒がちょうど1回ずつ端点になる(黒の数)÷2本のパスを適当に引き、奇数本のパスに含まれる辺を $G$ に追加すると、$G$ を連結なオイラーグラフにすることができる(!!!)。

$G^c$ が下図のような場合の例を示す。

f:id:ukuku09:20181213175106p:plain

黒は6個あるので、黒を両端点とする適当なパスを3つ選ぶ。

f:id:ukuku09:20181213175117p:plain

下図に奇数本のパスに含まれる辺を実線で示した。これらの辺を $G$ に追加すると、$G$ は連結なオイラーグラフとなる。

f:id:ukuku09:20181213175049p:plain

コード

上の考察通りにやったら結構長くなったので省略。実装が下手。

反省

聞いた瞬間確かにすぎて蟹になったんですが、5時間かけて思いつかないの頭が悪すぎて辛いです。やっぱり普段からちゃんと競プロやってないとダメなんだろうなぁ。