Codeforces Round 865 (Div. 1)

　AB二完。

コンテストへのリンク

コンテスト後のツイート

Codeforces Round 865 (Div. 1) AB二完。
A nが奇数なら調整可能。
B 「+ n+1」「+ n+2」を聞くと直線になる。
C SCCすると各数字最高何個おけるか調べられるのかと思ったが、実装した後で破綻に気付き、修正できず終了。

— titia (@titia_til) April 9, 2023

C. Between

　具体例を考えたとき、色々間違えていた。

　n=3で、

2 1 3 2 2 3

　なら、2を二個にしたら3は一個にしなきゃいけないものと勘違い。これ、3は（二個どころか）三個おいても大丈夫だった。

・3 2 1 3 2 3

　で良い。

　n=3で、

2 1

3 1 3 2 2 3

　でも、

・2 3 1 2 3

　が最善。（2, 3の順番に注意。1の左右で同じ順番でなくてはならない。私は、左右で逆の順番にした方が良いと勘違いしていた）

　つまり、1からの距離だけ見ればOK。

　それさえ分かれば、1からの距離が偶数のものは、index 0, 2, 4, ...に割り振り、奇数のものはindex 1, 3, 5, ...に割り振る感じで構築できる。

D. XOR Counting

　解説AC。

　N=2以外のときは自明で、n=2のときは桁DPでできる、というような解法ツイートを読んだ。

　桁DPと言われてもぱっとは理解できなかったのだが、下の桁が1のときと0のときで場合分けを書いて見ると、桁で場合分けすれば再帰で計算できることは分かった。

　一番下の桁が0のとき、0,0と、1,1の二つに分かれるが、それらでは一つ上の桁が1変わってくる。なので、その二つで値がかぶることはないことから、場合分けして考えられる。

　ただ、その後の高速化ができず解説を見た。

　一気に再帰で計算しようとするのではなく、

・一番下の桁が1のとき、その桁に関するxorは1になるが、その値がどんな数字にかかってくるのか、個数を求める

　ものを再帰で書けば良かった。