なんかぷよぷよの練習をしていたら日が落ちていた。俺はなぜこんな時間を…

---

今日解いた競プロの問題。

CPSCO2019-Session3-E: XORと足し算の間に都合のいい性質など考えようもないが、ビットごとに分けてXORの話をしてそれから足し算にすれば良いということに気付いたらあとは簡単だった。

$A_i xor X$の$j$ビット目について考えると、$A_1$から$A_k$までの中で$j$ビット目が1であるものが$s$個あるとして、$A_i$の$j$ビット目が1ならば$(s+1)%2$、0ならば$s%2$であることが分かる。

$A_1 xor X$,$A_2 xor X$,…の$j$ビット目について考えてみると、$(s+1)%2$であるようなものが$s$個、$s%2$であるようなものが$k-s$個ある。これの総和は$s\times ((s+1)%2)+(k-s)\times(s%2)$で求まる。

あらかじめ各k各ビットについてsを求めておけば、$O(N\log \max A)$で解ける。

---

注文していた「寺山修司少女詩集」が届いた。できれば古本屋やbookoffで手に入れたかったのだが、新品しかなかった。

とりあえず開いてみた最初の章に、海に関する詩がまとめてあった。自分の描いた海におぼれ死ぬ画家、自分の録音した波の音に飛び込んだ女、海を採譜しようとした音楽家。なにかこう、一貫しているような一貫していないような強い情念を感じるのだが、海に何を見ていたのかが今一つピンとこない。写し取ろうとしても写し取れない、それでいて全てを飲み込んでいく、そんな何か…