Codeforces Round 868 (Div. 2)

　Dまで。EもFも復習しておきたい。

コンテストへのリンク

コンテスト後のツイート

Codeforces Round 868 (Div. 2) Dまで。 A 全探索。同じ数字x個でx*(x-1)/2が作れる。
B mod kで分類
C p*p優先、ダメなら素数三つ
D 回文の個数を稼ぎたいなら同じ文字連打
E https://t.co/eDhtXDYtOd… を見に行ったがちょっと違った。
F 今sampleは合ったけど多分WA。

— titia (@titia_til) April 27, 2023

E. Removing Graph

　解法ツイートを見てAC。

　Grundy数を使う問題で、一見この問題に似ている。ただ、サイクルから一回切り取るとpathになることに気を付けなくてはいけない。そのときは、この問題の簡単なバージョンだった。これらによりGrundy数を計算すれば解ける。

　ただし、それらを思い出せなくても、Grundy数は実験すれば求められる。

　実際私もコンテスト中に実験していた。しかしpath graphのGryndy数のみ実験し、cycleの場合を実験しなかったため解けなかった。path graphのGryndy数を使えば元のcycleのGrundy数もすぐ分かるのだから、ちゃんと実験していれば解けていたはず。pathの場合に何か規則性があるのでは？　などと考え（実際、0にならない、という規則はあったのだが気付けなかった）最後まで実験しなかったのはダメ。

F. Random Walk

　解説ACしたが今一つ納得できていない。類題が出たら解けない気もする……。

　公式解説よりもこのコメントの解説の方が分かりやすかった。s～t間のpathに含まれる頂点の期待値がdeg(v)*d(v)になるというのは納得。

　それ以外の頂点の期待値も似たように考えて求めることはできる……というのはそう。だけど、他の方のツイートとかを見ると、もっとすっきりとした理解の仕方がある気がする。