昨日宴会があったのでしばらく謹慎するかとか言ってたのに、めっちゃいい天気でハイになって動物園に行くなどしていた。たわけ！

たまたまアシカの餌やり現場に遭遇するなどした。餌は魚なのだが、飼育員さんがそれを広いプールのあっちに投げたりこっちに投げたりするなどしてアシカに泳いで取りに行かせていた。ちゃんと運動させる、動物に適度な刺激を与えるみたいな意味合いがあるのだろうか。

飼育動物ではないのだが、たまたまカラスが太陽を背にして飛ぶところを見た。太陽の陽光が透けた羽根は、黒というよりも鷲のような美しい茶色に見えた。

---

ABCに参加した。久しぶりに青prfが出た。どうやら自分はまだ青コーダーだったようだ。

A: やるだけ。こういう短い数列での最大値とか中央値とかをどうするか、せっかく短いんだからなんかifとかそういうのでやった方がいいのかみたいなのを毎回悩むのだが、結局面倒なので普通にソートしている。

B: やるだけ。それぞれ座標出してマンハッタン距離。

C: multiset貼るだけ。Pythonとかいう欠陥言語を使ってる人類は大変らしい。

D: 包除やるだけなのだが、「Aの倍数かつBの倍数」をなぜか「A×Bの倍数」としてしまってバグらせた。当然正しくは「LCM(A,B)の倍数」。数学が出来なくなってる…

E: 愚直な$O(NM^2)$解を適当に累積和で高速化するだけ。なのだが、k=0の時になんか挙動がちょっと特殊になるということに気が付くのに時間がかかり2WAした。ちくしょう。こういう高速化は脳死で書けるようになったと思っていたんだが、ちゃんと詰めないと死ぬ場合もあるのだな。

F: 「最後にリセットしたタイミングを記録しておく」というのを最近どこかでみたので適用できた。それはいいのだが、区間更新クエリがあって任意のタイミングの状態と現在の状態を同時に参照しなければいけなさそうなのでそこで悩んだ。永続セグ木みたいなテクもあるっぽいので今から勉強するかみたいなこともちらっと考えたが、普通にクエリ先読みして「どのタイミングのどこのデータが欲しくなるのか」をあらかじめ調べておけばよいという結論になった。ちゃんとやったら通った。

G: なんかちゃんと詰めたら普通に今の実力で通せそうな雰囲気があるが、時間が足らなくて無理だった。任意のX番目の整数の組は$O(\sqrt{X})$で算出できるので、愚直にやれば$O(N+ (R-L))$で解くことができる。そして、数列Aに対しある数$x$について$(A_x, A_{x+1})$の交換から$(A_x, A_N)$の交換までをやると、結果としては単に$A_x$から$A_N$までがぐるっと1個ずれる感じになるっぽい。たぶんちゃんと実装すればこの「ずらし」処理k回分をやるのは$O(N)$で出来るので、あとはL番目付近やR番目付近の処理を$O(N)$でちょちょっとやれば多分全体$O(N)$で解けるはず。明日がんばってみる。