2020年3月16日月曜日

CodeChef March Challenge 2020 - Winning Ways 2

CodeChef March Challenge 2020 - Winning Ways 2

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

(s1s1S)+ ...+(skskS)\binom{s_1}{s_1 \oplus S} +  ... + \binom{s_k}{s_k \oplus S}

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

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

c(si)(s1s1S)+...+c(sk)(skskS)(ijsisj)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 とする)

と計算できる。登場する個数がll種類あるとして、llがもっとも大きくなるのは11回登場する数が1種類、22回登場する数が1種類、…、ll回登場する数が1種類あるときで、このとき

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

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

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

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

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

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

  • next[y]:=\operatorname{next}[y] := t>yt > ycoef[t]>0\operatorname{coef}[t] > 0となるような最小のtt
  • prev[y]:=\operatorname{prev}[y] := t<xt < xcoef[t]>0\operatorname{coef}[t] > 0となるような最大のtt

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


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