AtCoder Regular Contest 213 (Div. 1)

　Aしか解けず。そのAで酷く時間がかかってしまった。

コンテストへのリンク

コンテスト後のツイート

AtCoder Regular Contest 213 (Div. 1) Aのみで破滅
A costは転倒数。転倒数は高々36なので36歩以上進む場所は必ずいけるとして良い。DP[i]でi番目を使ったとき獲得したお金として、累積maxを組み合わせればOK。が、DPの初期値を0にしてずっと気付かず13ペナ。序盤、絶対使えないやつがあるもんねぇ。

— titia (@titia_til) January 25, 2026

B - Hamming Distance is not 1

　ヒントだけ見て解こうとしたが、全然答えが合わず20ペナ以上を重ねた。

　bitcoutを2で割った余りが重要なのは分かる。

　bitcountが奇数のもののみ、もしくは、偶数のもののみを集めたものは条件を満たす。

　ところで、2nと2n+1はbitcountの偶奇が必ず異なる。（これを利用することはコンテスト中気付いていなかった）

　なので、全体の約半分は必ず含めることができる。

　問題は、Lが奇数、Rが偶数のとき、L～lastまではbitcount偶数（奇数）、last+1～Rはbitcount奇数（偶数）のものを採用すると、答えが一個増える場合があること。（このことにはコンテスト中気付いていた）

　そのようなlastをどう求めれば良いか？　というのが分からなかった。

　あるbit iについて、R^(1<<i)がL以上だったとする。すると、それとRが同じグループに入っていてはいけない。なので、lastはR^(1<<i)以上と分かる。

　これを繰り返していけば、lastの候補を絞っていってACした。

　公式解説では、LとRで異なる最上位bitに着目しているよう。なるほど。結果的には同じものを求めていそうですね。

　二部グラフへ持ち込む証明は思いつかない。というか、最大独立集合（参考）について理解していなかったことに気付きました。