G - Caeser Syllables Editorial by HBit

SIMD解法

この解説は ChatGPT を使用して作成しています

解法

\(k=0,\ldots,K-1\) を固定し、\(A'_i=(A_i+k)\bmod K\) とする。

\(A'\) の音節は母音の極大連続区間なので、先頭が母音である場合と、子音から母音へ変わる位置を数えればよい。したがって答えは

\[ V_{A'_1}+\sum_{i=2}^{N}(1-V_{A'_{i-1}})V_{A'_i} \]

である。これをすべての \(k\) について高速に計算する。

512 個の \(k\) を同時に処理する

AVX-512 の 1 レジスタを 512 個の bit として使う。ある \(k_0\) から始まる 512 個の \(k\) に対し、各 \(i\) について

\[ P_i[t]=V_{(A_i+k_0+t)\bmod K}\qquad(0\le t<512) \]

を表す 512-bit 列 \(P_i\) を考える。このとき

\[ D_i=(\neg P_{i-1})\land P_i \]

の \(t\) 番目の bit は、\(k=k_0+t\) のとき位置 \(i\) から新しい音節が始まるかを表す。よって各 bit について \(D_2+\cdots+D_N\) を数えればよい。

\(P_i\) を高速に取得するため、\(V\) を巡回する bit 列として詰める。開始位置の bit offset は \(A_i\bmod 8\) の 8 通りしかないため、8 通りにずらした列を前計算しておけば、任意の \(P_i\) を 512-bit load 1 回で取得できる。

2 遷移をまとめる

連続する 2 遷移

\[ D_i=(\neg P_{i-1})\land P_i,\qquad D_{i+1}=(\neg P_i)\land P_{i+1} \]

は、同じ bit について同時に 1 にはならない。したがって

\[ D_i+D_{i+1}=D_i\lor D_{i+1} \]

であり、2 遷移分を

\[ (\neg P_{i-1}\land P_i)\lor(\neg P_i\land P_{i+1}) \]

という 1 個の bit 列にまとめられる。この 3 入力の論理式は AVX-512 の ternary logic 1 命令で計算できる。

Carry-Save Adder

残るのは、多数の 512-bit 列について各 bit が何回 1 になったかを数える処理である。512 個の整数カウンタを持つ代わりに、カウントを \(1,2,4,8,\ldots\) の重みを持つ bit plane として保持する。

3 個の bit 列 \(a,b,c\) に対して

\[ s=a\oplus b\oplus c,\qquad t=(a\land b)\lor(b\land c)\lor(c\land a) \]

とすれば、各 bit ごとに

\[ a+b+c=s+2t \]

が成り立つ。これを Carry-Save Adder (CSA) として階層的に適用し、多数の bit 列を少数の bit plane に圧縮する。最後に各 bit の bit plane を読み取れば \(D_2+\cdots+D_N\) が復元できる。

最後に先頭の寄与 \(V_{A'_1}\) を加えれば、その \(k\) に対する音節数が求まる。

計算量

AVX-512 では 512 個の \(k\) を同時に処理でき、\(K\le2300\) なので必要なブロック数は最大

\[ \left\lceil\frac{K}{512}\right\rceil=5 \]

である。512-bit SIMD 演算を \(O(1)\) と数えると、計算量は

\[ O\left(N\left\lceil\frac{K}{512}\right\rceil+K\right) \]

で、メモリ使用量は \(O(N+K)\) である。

参考コード: https://atcoder.jp/contests/abc471/submissions/78445056 (34ms)