/ 最近 .rdf 追記 編集 設定 本棚

脳log[20211107] AtCoder Beginner Contest 226/E 問題 Just one



2021年11月07日 (日)

最終更新: 2021-11-12T21:42+0900

[AtCoder] AtCoder Beginner Contest 226E 問題 Just one

解けなかった。

 提出 #27107258 (WA×9 / AC×24)

これはコンテスト中の提出。WA と AC の比率からして惜しいのかなという感じ。おそらく 0 を返すべきケースで 0 が返せていない。それはどういうケースか。連結成分が8の字になっていたりして輪っかが1つではないケース。

しかしそれをどうやって検出するのか解らなかった。

 提出 #27118298 (AC)

これはコンテスト終了後の提出。さっきの WA 提出では UnionFind で閉路の検出(だけ)をしていたのだけど、もうちょっと細かく、ノード数と辺の数の両方がわかるように記録をつけた。

辺の数がノード数より1だけ小さい連結成分は木であり、辺の数はこれが最小。辺の数とノード数が同じ連結成分はループが1つとオプションで突起をいくつか持っている。辺の数がノード数より多い連結成分は複数のループを持っている。

題意を満たせるような連結成分は3種のうちの1つだけ。他の2つが存在すれば答えはゼロだし、適合する連結成分のみが A 個あったなら答えは 2.pow(A,998244353)。

ここまで考えがまとまるのに2時間かかってるんだよなあ。

 なもりグラフ

なんか「なもりグラフ」という名前があるらしかった。調べようとしたらゆるゆりの人と名前がかぶってて検索性が悪かったのだけど、別に間違ってはいなかった。なもりを検索してなもりが見つかるのは当然。

chokudai(高橋 直大)🍆@chokudai

F問題の由来です。(N頂点N辺の連結なグラフを「なもりグラフ」と呼ぶ人がいるのもこれが理由です。) https://t.co/saSTvA1lep

F 問題って、AGC の F 問題「Namori」じゃないですかー(やだー)。赤 diff の精進は 10 年後も手つかずの見込みですから。

これもあった。ARC079-F「Namori Grundy」。橙 diff は、どうかなあ。解説 AC が1つあるだけだけど、10 年後は。