ABC091 D - Two Sequences
問題
概要
長さ $N$ の整数列 $A,B$ に対して $\displaystyle \bigoplus _{1\leq i,j\leq N} A _ i + B _ j$ を計算する問題。
解法
数列の要素は $2^{28}$ 未満なので、和は $32$ bit に収まる。$256$ bit に $A$ を $8$ 要素ずつ詰めて愚直にやる。
実装
Submission #29355762 - AtCoder Beginner Contest 091
AC135 F - Delete 1, 4, 7, ...
問題
解法
$k$ 回篩った後に残る数のパターンは $3 ^ k$ の周期を持つ。詳細は省くが周期毎の和は計算できるので、端数が計算出来ればよい。そこで、以後 $N\lt 3 ^ K$ を仮定する。
$1$ 回篩うたびに列の要素数 $n$ は $n - \left\lceil \dfrac{n}{3} \right\rceil = \left\lfloor \dfrac{2n}{3} \right\rfloor$ へと減少する。$3 ^ {29} \lt 10 ^ {14} \lt 3 ^ {30}$ であり、$N = 3 ^ {29} - 1, K = 29$ では $536870911$ 個、$N=10 ^ {14},K=30$ では $521509504$ 個の要素が残り、この辺りが最悪ケースと考えられる。
$K$ 回篩った後の $i$ 番目 (1-indexed) の要素は、$f(x):=\left\lceil \dfrac{3x}{2}\right\rceil$ に対して $\underbrace{f(f(\cdots f}_{K 個}(i)\cdots ))$ として計算される。従って、愚直に答えを計算しようとすれば約 $1.56 \times 10 ^ {10}$ 回程度の演算を要する。
各要素は最大で $10 ^ {14}$ にも及ぶので、$64$ bit 整数を用いて記憶する必要がある。従って、avx2 で用いる $256$ bit のレジスタに $4$ つ格納でき、理想的には $4$ 倍の高速化が期待される。
計算回数が (理想的に) $1/4$ になると仮定しても依然として $3.90 \times 10 ^ 9$ 回程度となるが、上記の最悪ケースを試すと 1650 ms 程度で実行が終了するので投げてみるとおおよそ同じような実行時間で AC が得られる。
実装
Submission #29357608 - AtCoder Regular Contest 135
Educational Codefoeces Round 107 G. Chips on a Board
問題
概要
問題を言い換えると，次のような問題が解ければよいことが分かる．
長さ $N$ で各要素が $0$ 以上 $M $ 未満の非減少な非負整数列 $c$ が与えられる．以下の形式で表されるクエリが $Q$ 個与えられるので，それぞれ順番に処理せよ．
l r v: $\displaystyle \bigoplus _ {i = l} ^ {r - 1} (c _ i - v)$ が $0$ でなければAと出力，$0$ ならばBと出力．ここで，$\oplus$ はビット毎の排他的論理和であり，また $c _ l \geq v$ が保証される．
実行時間制限 : 5 sec
制約
- $1\leq N, M, Q \leq 2\cdot 10 ^ 5$
- $0\leq c _ i \lt M $
- 各クエリ
l r vについて，- $0\leq l \lt r \leq N $
- $0\leq v \lt M $
解法
如何にも SIMD で頑張れば通りそうな問題．クエリ処理で現れる $c _ i - v$ は $2\times 10 ^ 5$ 未満なので，32 bit 整数で扱うことができる．従って，256 bit のレジスタで $8$ つずつまとめて処理することで，高速化できる．
