(gn-gm).abs。提出 #27485094 (AC / 515 Byte / 188 ms)。ほぼ一日かかった。■考え方はいろいろあるのかな。自分はまず反対側の領域にもぐりこんでいる要素を探した。そしてそこに本来収まるべき要素を探し、探した要素があった場所に本来収まるべき要素……を芋づる式に探してグループとした。ただしグループは前半領域、後半領域のどちらかの中にだけ作って、領域をまたぐグループは考えなかった。こうやって１つずつ反対側に移動している要素の位置を移動しながらついでにソートもしていくと、最終的に反対側に移動している要素はなくなり、前半後半のどちらかに閉じて位置を交換していてソートされなかったグループが残る。反対側の未ソートグループが利用できる場合は利用して互いに交換回数を節約しながら全グループをソートする。この、手続きに基づいた解法がどのような考えからひねり出されてきたかというと、必ず行わなければいけない操作を無駄なく行う、というところから。貪欲法？最終更新: 2021-11-12T21:42+0900
解けなかった。
これはコンテスト中の提出。WA と AC の比率からして惜しいのかなという感じ。おそらく 0 を返すべきケースで 0 が返せていない。それはどういうケースか。連結成分が８の字になっていたりして輪っかが１つではないケース。
しかしそれをどうやって検出するのか解らなかった。
これはコンテスト終了後の提出。さっきの WA 提出では UnionFind で閉路の検出(だけ)をしていたのだけど、もうちょっと細かく、ノード数と辺の数の両方がわかるように記録をつけた。
辺の数がノード数より１だけ小さい連結成分は木であり、辺の数はこれが最小。辺の数とノード数が同じ連結成分はループが１つとオプションで突起をいくつか持っている。辺の数がノード数より多い連結成分は複数のループを持っている。
題意を満たせるような連結成分は３種のうちの１つだけ。他の２つが存在すれば答えはゼロだし、適合する連結成分のみが A 個あったなら答えは 2.pow(A,998244353)。
ここまで考えがまとまるのに２時間かかってるんだよなあ。
なんか「なもりグラフ」という名前があるらしかった。調べようとしたらゆるゆりの人と名前がかぶってて検索性が悪かったのだけど、別に間違ってはいなかった。なもりを検索してなもりが見つかるのは当然。
chokudai(高橋 直大)🍆@chokudai
F問題の由来です。（N頂点N辺の連結なグラフを「なもりグラフ」と呼ぶ人がいるのもこれが理由です。） https://t.co/saSTvA1lep
F 問題って、AGC の F 問題「Namori」じゃないですかー(やだー)。赤 diff の精進は 10 年後も手つかずの見込みですから。
これもあった。ARC079-F「Namori Grundy」。橙 diff は、どうかなあ。解説 AC が１つあるだけだけど、10 年後は。