(記: 2022/10/24)

結局イラストのためにほぼ徹夜した。

---

なんかスプラトゥーンをやりまくっていた。エイムの調子が良かったが立ち回りはそれほどでもなく、まだまだ改善の余地があるなと思った。S+40代まで行ったが結局20代に戻ってしまった。

---

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

ARC151-A: 自力AC。ARC-Aにしてはちょっと難しめに感じた。

SとTで同じビットについては、Uは0にしても1にしても問題ない。どっちにしてもS-Uの距離とT-Uの距離が変わらないからだ。この問題では辞書順最小を求めるので無条件で0にすればよい。SとTで違うビットが問題になる。

SとTで異なるビットの場合、SとTのどちらかが0でどちらかが1ということなので、UはSともTとも異なるということはあり得ない。以上のことから、Uの各ビットは以下の3種類のいずれかになる。

• SとTで変わらないので無条件に0としたビット
• SとTで違うのでSと同じにしたビット
• SとTで違うのでTと同じにしたビット

後ろ2つの数は同数でないといけないので、SとTで異なるビットの数(SとTのハミング距離)は偶数でなければならないことが分かる。ということで奇数ならばUは構成不可能。

偶数の時は構成可能で、辞書順最小を求めるので上の桁から順になるべく0にしていきたい。SとTのハミング距離/2をdと定義する。

辞書順は上の桁が絶対なので、上から順番に0に出来るかを考えていく。Sと同じにしたビットの数とTと同じにしたビットの数の双方をdにしなければならない。これまで決定したビットのうち、Sと同じ値をとるビットの数もしくはTと同じ値をとるビットの数がdに達していたら諦めて1に変える。これで条件を満たすUのうち辞書順最小が求まる。