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)
