CodeChef March Challenge 2020 - Winning Ways 2

• 問題
• AC

区間$[l, r]$に登場する同じ数をまとめてそれぞれ個数を数える。grundy数を考えると、ゲームの勝敗は個数の組み合わせだけで決まっていることがわかる。つまり、現れる個数を$s_1, ..., s_k$個とした時に、その総xor $S = s_1 \oplus s_2 \oplus ... \oplus s_k$で勝敗が決まっている。先手が初手で$s_i$を減らして$s_i \oplus S$にすることができればxorがゼロになって、先手必勝の盤面になる。したがって、先手が勝てる初手の総数は

$$\binom{s_1}{s_1 \oplus S} +　 ... + \binom{s_k}{s_k \oplus S}$$

と計算できる。ただし、石を増やしたりパスしたりすることはできないので$s_i \le s_i \oplus S$の項は$0$とする。これを素朴に計算すれば部分点が取れる。

満点解法について。個数が同じもの、つまり$s_i = s_j$となるようなものはまとめて計算できることに注目する。つまり、個数$s_i$が$c(s_i)$個あると考えるとき、$c(s_i)$を係数として

$$c(s_i)\binom{s_1}{s_1 \oplus S} + ... + c(s_k)\binom{s_k}{s_k \oplus S} \qquad (i \neq j なら s_i \neq s_j とする)$$

と計算できる。登場する個数が$l$種類あるとして、$l$がもっとも大きくなるのは$1$回登場する数が1種類、$2$回登場する数が1種類、...、$l$回登場する数が1種類あるときで、このとき

$$1 + 2 + ... + l \le N$$

なので、$l = {O}(\sqrt{N})$と評価できる。これなら全体の計算量は${O}(Q\sqrt{N})$となって間に合うはず。

さて、問題は区間$[l, r]$に登場する数をどのように数えるかだが、Mo's algorithmでできるのでそうした。

• $\operatorname{size}[x] :=$ ある区間に登場する数$x$の個数
• $\operatorname{coef}[y] :=$ 個数$y$にかかる係数。

というデータを持ちながら伸縮すれば${O}(1)$で遷移できるので、$Q$個のクエリに対しては ${O}(N\sqrt{Q})$ となる。つまり、計算量をまとめると ${O}(Q\sqrt{N} + N\sqrt{Q})$。

ただ、$\operatorname{size}$と$\operatorname{coef}$をハッシュテーブルで持つと定数倍が重すぎて間に合わなかった。$\operatorname{size}$に関しては、登場する数を座標圧縮すれば長さ$N$以下の配列で持てる。しかし、$\operatorname{coef}$は ${O}(\sqrt{N})$ で走査する必要があるので、素朴に配列を使うと方針が破綻する。これは双方向リストっぽい持ち方で解決した。つまり、 長さ$N$の配列で持った上で、

• $\operatorname{next}[y] :=$ $t > y$で$\operatorname{coef}[t] > 0$となるような最小の$t$
• $\operatorname{prev}[y] :=$ $t < x$で$\operatorname{coef}[t] > 0$となるような最大の$t$

という風に前後のインデックスを保持しておく。$\operatorname{coef}$のある項を増やしたり減らしたりするときには$\operatorname{next}$と$\operatorname{prev}$を適切に変更する。こうすると、先頭から$\operatorname{next}$をたどれば$\operatorname{coef}$の正の要素だけを走査できるようになる。これで間に合った。

---

SBCLについて。これでも11秒くらい掛かって不思議に思っていたのだが、原因はコード変換に失敗していたことだった。sb-c:define-source-transformはdefine-compiler-macroと違ってコンパイル時実行ではないので、eval-whenで括らないとコンパイル時には存在しないことになってしまう。直したら余裕で間に合った。AtCoderだとスクリプト実行だからこの問題が起きなくて気づけなかった。