Educational Codeforces Round 125 (Rated for Div. 2)

　pretestはDまで四完。Dの前にしばらくEを考えていたけど、分からずDへ戻った。

　システムテストでDが落ちた。

コンテストへのリンク

コンテスト後のツイート

Educational Codeforces Round 125 (Rated for Div. 2)
A 高々二回でできる
B 貪欲
C regularで消せるのは()のみ。回文はManacherで判定した。
D Cが小さいことに注目。各コストで倒せるD*Hを前計算する。cが小さい順、d*hが大きい順にソートしてやればlogでできる。
E 立式は簡単だがそこから進まず。

— titia (@titia_til) March 22, 2022

D. For Gamers. By Gamers.

　システムテストで落ちたのは、枝刈りが悪さをしていたためでした。

　コストの小さい順に見ていく際、「あるコストで倒せるD*Hの値」が今調べているものを上回っていたら次のタイプは移していたのだけれど、それではダメですね。

　たとえば、

　コスト2で2, 4, 6, 8, ...と処理し、

　コスト３で3, 6, 9, ...と処理しているとき、6ではお得じゃないけれど、9ならお得なことがあり得た。（具体的には、testcase 125。これで落ちた）

　これを直すとTLE→PyPy3-64にしたらAC。こどふぉのPyPy3とPyPy3-64の速度感覚はいまだに全く分からない。大きい数を使いたいときは-64にした方が良いっぽいというのが基本だろうけど、それで遅くなることもあるため。

E. Star MST

　解法ツイートを見てAC。

　1から頂点iに重みxの辺が、頂点jに重みyの辺が張られているとき、iとjの間の辺の重みはy以上k以下になる。それらを掛け合わせたものの和が答え。

　それをDPで求める。制約を見るとDPっぽいが、それで正しかった。

　ある頂点まで見て～だと上手くいかないが、

　1と重みx以下の辺が張られている頂点の個数がy個のとき～と考えると上手くいく。

　次に重みx+1の頂点をz個張るとき、y+z個の頂点間で、今まで辺が張られていなかったところ全てについて、重みx+1以上の辺を選んで良いと確定するため。

　頂点ごとに見ると上手くいかないが、このように重みの小さい辺から張っていく、とするとDPが回る。