日々drdrする人のメモ

今日も明日もdrdr

ABC009 - D問題: 漸化式 (ビット行列解法)

ちょっと昔の話だけど書いとく。

今回はABC009のD問題: "漸化式" をビット行列として解いた話 (Python)

D: 漸化式 - AtCoder Beginner Contest 009 | AtCoder

想定解法

想定された解法は、行列で繰り返し二乗法を計算して、
 {A_M = (C'_1 \text{ AND } A_{K}) \text{ XOR } \ldots \text{ XOR } (C'_K \text{ AND } A_1)}
となるような {C'_1, \ldots, C'_K}を求めるみたいな感じ。これは {O(K^3 \log M)}である。

C++などであれば余裕だけど、Pythonだと配列処理が遅くて行列計算がアレなので {K = 100}では厳しくなる。
以下が上の解法で実装したやつ。当然TLE
Submission #175602 - AtCoder Beginner Contest 009 | AtCoder

いろいろ試行錯誤したけど想定解法では結局ダメだった...。

ビット行列

今回参考にしたものは以下。
anond.hatelabo.jp

一つの整数値にビット行列のビットを詰めまくって、行列乗算をまとめて行う(ビットパラレル行列乗算)ことで高速に解く方法である。
この方法ならPythonでもいけそうだと思い、実装してみることにした。

解法

求める {A_M}のビット演算がビットごとに独立していることを利用し、各ビットでビット行列を用いて繰り返し二乗法を行う、という感じ。
32ビット分の行列演算を行うことになるが、配列処理が減らせるので、結果的に早くなってACできる、というのが狙いだった。

ビット行列の実装

Python多倍長整数が扱えるので、一つの整数値に無限にビットが詰められる。そこで、とりあえずL*L個のビットを一つのブロックとして、(K/L)*(K/L)の二次元配列で行列を持つように実装。

そして、以下のようにLの値を変えながら何回かsubmitしてみる。
L = 8 (TLE): Submission #726799 - AtCoder Beginner Contest 009 | AtCoder
L = 32(TLE): Submission #726805 - AtCoder Beginner Contest 009 | AtCoder
L = 64(TLE): Submission #726807 - AtCoder Beginner Contest 009 | AtCoder
L = 99(TLE): Submission #726812 - AtCoder Beginner Contest 009 | AtCoder

TLEしまくって、ビット行列にしてもダメな感じが漂ってたけど、L = 100の時にACできた。
Submission #726810 - AtCoder Beginner Contest 009 | AtCoder
L = 99がTLEして、L = 100の時がACになった。このことから、配列としてビット行列をブロックに分割せず、ブロック全体を一つの整数値に突っ込んだほうが早い、ということが分かる。

次に、二次元配列を使わずに一つの整数値に全てのビット(K*K)を突っ込んだ実装をしてみる。
Submission #726855 - AtCoder Beginner Contest 009 | AtCoder
こっちもACできた。計算量はビット行列の積回数(+ Karatsuba法の多倍長乗算)が {O(K^{2+2 \log_23})}と繰り返し二乗法が {O(\log M)}で、 {O(K^{2+2 \log_23} \log M)}ぐらいになる。(計算量的には想定解法よりも重そうに見えるけど、Python的には配列使ってないし内部で乗算しているので速い)


Pythonは2次元配列がでかくなる場合はダメなケースが多い(例えば、10^6~10^7サイズのナップサック問題とか)けど、ビット行列など、ビットに押し込んで一気に演算できれば高速に処理できて解けるケースがありそう。

その他の解法

あと、この問題はKitamasa法を使うことでも解ける。 {O(K^2 \log M)}
今回の解法よりも速い: Submission #1050143 - AtCoder Beginner Contest 009 | AtCoder

これは今回の記事では扱わないけど、雑な理解メモは以下に書いた。
smijake3.hatenablog.com