Zenn
🍣

Advent Calendar Contest 2020 - yukicoder - 12/01

2020/12/02に公開
競技プログラミング
yukicoder
idea

この記事は Advent Calendar Contest Advent Calendar 2020 に出題された問題の解いた記録です. 半分解説, 半分メモくらいの質を目指します. また私の実力的に星3になると解けるかだいぶ怪しいです. 公式に 「 解説は公開時間の23.5時間後に公開します。」 とありますので, これを目安に公開するようにします.

2020/12/01 - No.1304 あなたは基本が何か知っていますか？私は知っています．

DP 解法

2つの問題の複合になっていて,

  • 2つ同じものが並ばないような数の並びは何通りあるか
  • 総xor和が狙った数になるような数の組合わせは何通りあるか

という問題を同時に解く. そして, これらはともにDPで解ける.

さて, 明らかに気になる点があって,

  • 各要素 A_i は 0 以上 1024 未満なのでその総xor和も 0 以上 1024 未満
    • X,Y がやたらに大きな数が許されているが, 実際には区間 [0, 1024) との積を取ったその範囲だけ見れば良い
  • 数列 A の数の重複は取り除いたほうが良い
    • （直接に言及されていないが）異なる添字から取ってきても同じ数なら同じ数列と数えそうなので, 重複は最初に取り除いてから扱うほうが良さそう

他に気になる点は本当はあるけど, DP 解法ではここまでで良い.

2つ同じものが並ばないような数の並びは何通りあるか

長さ N の数列を先頭から1つずつ i=0,1,\ldots,N-1 と作っていくことを考えて,

dp_i^x = (\text{ 末尾がちょうど $x$ で終わる数列の個数 })

とすると,

  • dp_0^x = \begin{cases}1 & \text{ if } x \in A,\\0 & \text{ otherwise } \end{cases}
  • dp_{i+1}^x = \begin{cases} \sum_z dp_i^z - dp_i^x & \text{ if } x \in A,\\0 \end{cases}

という漸化式が組み立てられる.
ただし2式目の更新で \sum があるが, これを毎度足し算してると遅いかもしれない.
遅くないなら分かりやすいしそのまま書いてもいいけど, 今回は遅い.
別途 \overline{dp} みたいな変数を作って, dp の更新と一緒に更新シておくのが良い.
更新式はもちろん,

  • \overline{dp}_{i} = \sum_z dp_i^z

総xor和が狙った数になるような数の組合わせは何通りあるか

dp_i^x = (\text{ 総xor和が $x$ になる数列の個数 })

xor の演算子を \oplus と書くことにする.

  • dp_0^x = \begin{cases}1 & \text{ if } x \in A,\\0 & \text{ otherwise } \end{cases}
  • dp_{i+1}^{z} = \sum_z \sum_{x \in A} dp_i^{z \oplus x}

複合バージョン

以上2つを組み合わせれば,

dp_i^{z, x} = (\text{ 総xor和が $z$, 末尾が $x$ で終わる数列の個数 })

これを計算すればいい. コレと一緒に,

\overline{dp_i}^z = (\text{ 総xor和 が $z$ の数列の個数 }) = \sum_x dp_i^{z,x}

も持っておくと便利.

更新式は次の通り.

  • 初期化
    • dp_0^{x,x} = \overline{dp}_0^x = 1 ~ \text{ if } x \in A
  • 更新
    • dp_{i+1}^{z,x} = \sum_z \overline{dp}_i^{z \oplus x} - dp_i^{{z \oplus x},x}
    • \overline{dp}_{i+1}^z = \sum_z \sum_{x \in A} \overline{dp}_i^{z \oplus x} - dp_i^{{z \oplus x},x}

注意として, \sum_z は [0, 1024) 区間だけ見れば良いのと, A は重複を除いた作った集合として扱えば十分なこと.
さてこの更新は, 全体で 1024 \times 1024 \times N 回程度の加算, 代入操作を行うことになる.
今回は計算時間は大丈夫だったが, 三次元配列でこれを全部持つとメモリのほうがオーバーしてしまった（私の場合はかなり冗長な ModInt をこれに載せてたので）ので, 節約する必要があった.

半分全列挙 (TLE)

これを書いてて気づいたが,

  • N \leq 40
  • N が偶数！
  • K^N \leq 2 \times 10^{15}

如何にも半分全列挙しろと言っている.

m=N/2 として, 長さ N の数列を, その前半長さ m と後半長さ m について全通り作って突き合わせることが出来そう.

  • K^m 通りの数列を全て作る
    • この中で同じ数が2つ並んでるものは予め省く
    • それぞれの総xor和 S をメモする
    • 一番末尾の数 B をメモする

中で同じのが2つ並んでないかチェックの必要はあるので, そこに毎回 O(m) だけ掛かって, 全体として O(K^m m) で大体 10^8 \times 20 程度掛かる. ここが遅い????

最終的に出来上がる (S,B) の組はやっぱり 1024 \times N 通りしかない.

T_S^B = (\text{ そのような数列の個数 })

を二次元配列とかで記録しておく.

さて前半の (S,B) に後半 (S',B') を適当に付け足して xor を x にするためには,

  • S \oplus S' = x
    • \iff S' = S \oplus x
  • B' \ne B

S' 部分は全部調べなくてもただ一通りに決まる. B' はたかだか N-1 通りだからここは全部調べてしまう. というわけで, 前半と後半の組み合わせ方はたかだか 1024 \times N^2 通りしかなくて, これを素直に調べても十分速い.
ただし, x について全通り調べる必要はあるので, [x,y] の範囲を 1024 でキャップするとしても, 計算時間は更に \times 1024 掛かる.

TLE した. 半分を列挙するところが間に合ってないんじゃないかと睨んでる.
その中でDPするとか工夫の余地はあるけれど, もはや半分全列挙する意義とはとなる. これは引っ掛け用に用意した制約？

Discussion