AtCoder Regular Contest 133

　Cまで三完。

コンテストへのリンク

コンテスト後のツイート

AtCoder Regular Contest 133 Cまでは割と早かったが三完。
A 最初か、最後か、最初に上っていった頂点を削る
B 結ばれる可能性があるのはNlogN個。それらについて平面走査みたいにセグ木DP
C 和がmod Kで一致すれば作れる。全部K-1を入れたときよりどれだけ減らなきゃいけないか列か行のmaxだけ引く。

— titia (@titia_til) January 22, 2022

D - Range XOR

　kaageさんのブログの解法を参考にしてAC。

　累積xorの性質として、偶数とその次の奇数のxorは1とか、偶数から四つ連続したもののxorは0といったものは有名。それを使う問題なのは分かるけれど、詰めるのは大変。

　最終的に桁DPになりそう、というのも分かるが、使うところまで詰めるのも難しい。

　上のkaageさんのブログの解法では、l, rを偶奇で分類し、「lが奇数、rが偶数」のときだけ桁DPで処理している。（他の場合は、最初に書いたxorの性質を用いて処理）

　ただ、私は、桁DPは下の桁で場合分けしてメモ化再帰を使って実装した。

　calc(L, R, x, eqflag)で、「L以上R以下の数iに対して、i^xもL以上R以下であり、eqflag=1なら、i<=i^x、eqflag=0ならi<i^xとなるような場合の数」とした。

　不等号の計算を間違えたためちょっと実装に苦労してしまったが、この問題だと下の桁を場合分けする実装の方がやりやすいと思う。