JOI 感謝祭 2020

　二完で部分点もほとんど取れない悲しい結果。
　双子のコンテストは解説がしっかりしてることもあって好きなのだけど、最近は良い結果が出せていませんね。

コンテストへのリンク
解説PDF
コンテスト後のツイート

鏡のような分割（Mirror-like Division）

　公式解説を参考に実装したら80点は取れました。

　再帰を使っていて、あまり良い実装ではないと思うので、上手く実装すればPython/PyPyでも100点取れるのかもしれないけど……。

　Nが47以下ということで、半分全列挙や、bit全探索がまず思いつくと思う。

　で、結局、半分全列挙でこそないものの、「半分に分けてbit全探索」（の高速化）が正しい解法。自然で思いつきやすい方針だと思うのに、なんで考え付かなかったんだろう……。

　解説スライドの最後、bit全探索をDFSで実装した方が速くなる、というのは意外でした。

塗り箸2（Chopsticks 2）

　問題文を理解するのに苦労しました。やること自体は分かりやすいんだけど、読み解くのが難しい……。特に、クエリについて、区間L～Rが変化するという設定は必要あったんだろうか？　一点変更クエリだけじゃ何かまずいことがあったのかな。

　解説を読んで46点は取りました。そこまでやればBIT＋座標圧縮は思いつけると思うので、そこから90点までは実装問題に見えます。

　一番の本質は、「中央値を求めればOK」というところだと思います。

　そう言われてもなぜそうなるのかすぐには分からなかったのですが、図を描くと分かりました。

　「大きくしたい値」（今回であれば奇数個目）と「小さくしたい値」（偶数個目）がそれぞれ何個かずつあるとします。

　このとき、境界より下にある「大きくしたい値」の個数と、境界より上にある「小さくしたい値」の個数が同じだけあれば、そこを境界にするのが最適です。（図を描いて考えると、そこからずれたらもっとコストがかかることが言えます）

　で、今回は、「大きくしたい値」と「小さくしたい値」の個数が同じなので、中央値を境界にすると、境界より下にある「大きくしたい値」の個数と、境界より上にある「小さくしたい値」の個数は同じになり、条件を満たします。

　こういうタイプの問題で中央値を考えるのは一つの定石だと思うので、思いつけるようになりたい。