Eまで五完。
コンテスト後のツイート
E 市松模様に色分けすることでNoの条件は分かるが、構築に苦戦。(A,B)を含む二行を特別視することで構築できた。
— titia (@titia_til) April 18, 2026
F 区間+1/-1加算によりmod Mで全ての要素を0にする操作回数の最小化になった。この問題が解けない。
F - Make it Palindrome 2
解説放送を見てAC。
結局のところ、「区間加算がきたら差分を取って考える」ができていなかった。この典型にはいつもやられている気がする。
今回は忘れていたわけではなくて、コンテスト中、差分を取って考えてみようとはしたのだが上手くいかないと思ってやめてしまっている。
しかし、区間の話を二点の足し引きにできているという時点で前進しているのだから、捨てたりせずちゃんと思考を進めるべきだった。
あまり意味のない言い換えに思えたとしても、やっておかなくてはいけない。
G - Mode in the Subtree
解説、解説放送など色々参考にしてAC。
その過程で、HL分解について、HL分解した後にセグ木などに乗せる場合の並べ方を勘違いしていたことに気付き、自分がHL分解を初めて知ったこの問題をようやくACした。
HL分解した後、色々したいなら、オイラーツアー順に並べるのが鉄則！ そうすることで、子孫たちが区間に並ぶので、上手く処理することができる。
このこと自体は知っていたけど、当時は知らなかったのかな？ HL分解とこの処理を組み合わせられるというのは初めて知りました。
さて、この問題ではDSU on Treeを初履修した。
アルゴリズム自体は分かりやすいけど、正当性の胆は、「全ての頂点における「light edgeたちに関する子孫の個数」の総和はO(NlogN)になる」ということだと思う。公式解説でもそう書いてあるのだけど、理解できず生成AIに相談してようやく理解できた。
その上で、定数倍が厳しく、PyPyじゃ通せずcodonで通したのだけど、PyPyで通している人もいますね。もっと上手くやる方法があるのかな。
0 件のコメント:
コメントを投稿