最終更新: 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 年後は。
Rubyが他の言語に比べてときどき遅くなることがある理由を聞かれたら、私なら「もしも〜だったら」を筆頭の理由に挙げます。 Rubyの実装では、プログラムを実行するときに「もしもこうだったら、ああだったら」を考えるのに多くの時間を費やします。足し算のたびに「オーバーフローしたらどうするか」、メソッドを呼び出すたびに「メソッドがモンキーパッチされていたらどうするか」、コードの1行1行で「トレースが有効にされていたらどうするか」といったことを判断しなければなりません。」 型付けによってプログラマが違反に対するペナルティを引き受けるから、Ruby は高速で突っ走ってくれ、と指示するモードが欲しくなったりする。Ruby で導入されつつある型はそういう用途ではないらしいけど、「シェイプ」が期待に応えるという話。ペナルティはありません。■これも読んだ。「Async Ruby - Bruno Sutic」 すごく楽しみな機能。「
A word of notice: Async does not get around Ruby's Global Interpreter Lock (GIL).」という前置きの解釈がわからないし、なんなら直訳も理解してないけど。共有リソースにアクセスすると全然 async にならないよ、ってことなら想定内だけど、デッドロックしない/させないやり方は想像できない。Fiber についても知らない。最後にこう書かれてるし、サンプルのチョイスもこの通りなので、「
Async's strongest point is scaling network I/O operations, like making or receiving HTTP requests. Threads are a better choice for CPU-intensive workloads, but at least we don't have to use them for everything anymore.」、自分には使い道がないかもしれない。それでも「
but ～」には同意するほかない。