Codeforces Round #699 (Div. 2) D. AB graph

あらすじ

Graphvizの練習　

問題概要

codeforces.com

$n$ 頂点の完全有向グラフが与えられる。
各辺には"a"または"b"というラベルがついている(辺 $u→v と v→u$ のラベルは異なる場合もある。)

f:id:socha77:20210221005448p:plain

このグラフ上の経路で、通った辺のラベルをその順につなげたときに長さ $m$ の回文になるようなものはあるか。
あれば構築して出力し、なければ"NO"と答える。

同じ辺を何回通過してもよい。

$2 \le n\le 1000,$ $1 \le m \le 100000$ (本当はマルチケースだけど省略)

f:id:socha77:20210221005149p:plain — Your friend Salem 誰?

解法

問題ページにも太字で表記されていましたが同じ辺を何回通過してもいいというのがかなり考察を簡単にしてくれます。

以下、自明なパターンから場合分けを潰していきます。

出入りのラベルが々頂点対が一つでもあれば、まずこれですべてが解決です

f:id:socha77:20210221012005p:plain — aaaa ... aaa

一種類の文字だけでできた文字列は回文になります。

ということで以降はすべての頂点対は出入りでラベルが異なるとして考えますこの場合でも、mが奇数の場合は2頂点を行き来するだけで解決します

f:id:socha77:20210221012301p:plain — ababa, ababababababa など

さて $m$ が偶数の場合は2頂点では無理なので3頂点を使います。
グラフ上の任意の3頂点を見たとき、(すべての頂点対で出入りのラベルが異なると仮定しているので、)以下のどちらかの関係になるはずです。

f:id:socha77:20210221024200p:plain — aのラベルを辿ると周回する

f:id:socha77:20210221024349p:plain — どこかの頂点にaのラベルが流入している

前者はaのラベルを辿ってループするだけで良いので終了です。
後者の場合はもう一つ場合分けをします。

m % 4 == 0 の場合　
- "abba" を複数回繋げて終了
そうでない場合(残りは 6, 10, 14 ... 4k + 2)
- "aabb" をk回繋げた後"aa"で蓋をして終了

です。

f:id:socha77:20210221025755p:plain — 前者 3-1-3-2-3 ... でラベルがabbaabbaabba...に

f:id:socha77:20210221025907p:plain — 後者 2-3-1-3-2-...-2-3-1でaabbaabb....aabbaaに

あと最後にまだ考慮していなかったのが「頂点が2つしかなくてラベルが違う、かつmが偶数の場合」ですが、この場合のみNOになります。

まとめ

u->vとv->uで同じラベルの頂点(u, v)がある -> 一生往復 〇
　|- mが偶数 -> 一生往復 〇
    　|- 頂点が二つ -> ×
　　　　|- 頂点1, 2, 3を見たとき、同じラベルだけで巡回できる -> 一生巡回  〇
　　　　　|- m % 4 == 0 -> abbaabba ... abba 〇
　　　　　|- m % 4 == 2 -> aabbaabb ... aabbaa 〇

です。

計算量は、一度全頂点対を調べる必要があるのとまあ長さmの経路を構築しなければならないので O( $n^{2} + m$ )　になります。たぶん

雑感

考察していた時はギャグのタイプの問題かなと思っていたけどまとめていたら結構場合分けが面倒で、沼にハマらずに通せたのは割とよかったなと思います。
codeforcesで腕力を鍛えよう