Cまで三完。
コンテスト後のツイート
D B=[A[i]+1 for i in range(n)]みたいなのを用意すると、平面走査みたいなので最初の答えは分かる。あとはクエリで差分計算したいのだが上手くいかない。
— titia (@titia_til) January 4, 2025
E1 答え二分探索で毎回BFSするとTLEする。
D. Gifts Order
けんちょんさんの記事を参考にAC。
セグ木を使うのは第一候補だったのにこれを思いつかなかったのは良くない。可換性が成り立たないとセグ木が使えそうという判断が鈍ってしまうようだ。気を付けよう。
E2. Another Exercise on Graphs (hard version)
こたつがめさんの放送の振り返りを見てAC。
ワーシャルフロイド法で、一辺を変更するときは辺の二乗の計算量でできることは覚えておきたい。
妙に制約が厳しい気がするけど、クエリ問題だから仕方ないのかな。（と思ったら、公式解説の方法はもっと速いらしい）
G. Secret Message
証明は難しいが、「十字のマスのうち一マスを塗れば良さそう」というところから発想することは可能だったか。
ただ、制約が厳しく、二次元配列を一次元に直さないと通らなかったので、コンテスト中にACするのは厳しかったかもしれない。