\(O(N\log(\max A))\) で解くことができます。

\(A_{i}<2^{20}\) より \(D=20\) とします。

公式解説のスライドにもあるように、以下の問題が解ければ良いです。

\(f(x):=(x \;\text{AND}\; (2^{k}-1))=(2^{k}-1)\) を満たす最大の \(2^{k}-1\)

として、

\(\sum_{i=1}^{N-1} \sum_{j=i+1}^{N} f(A_{i}+A_{j})\) を求めてください。

他の部分の計算は \(O(N)\) でできるので、この問題を高速で解きたいです。

上記の問題は次の問題の答えと同じです。

\(g(k,x):=(x \;\text{AND}\; (2^{k}-1))=(2^{k}-1)\) を満たすとき \(2^{k-1}\)、そうでないとき \(0\)

として、

\(\sum_{k=0}^{D-1}\sum_{i=1}^{N-1} \sum_{j=i+1}^{N} g(k,A_{i}+A_{j})\) を求めてください。

この問題は \(k\) ごとに例えば std::map を用いて、 \(O(N\log N)\) で解くことができます。

よって、全体で \(O(ND\log(N))\) で解くことができます。

実装例 c++

また、std::vector を用いても同じ問題を \(k\) ごとに\(O(N\log N)\) で解くことができます。

具体的には以下のようにして解けます。

長さ \(N\) の数列 \(B\) を \(B_{i}=(x \;\text{AND}\; (2^{k}-1))\) とした後、ソートする。

そして、 \(B_{i}+B_{j}=(2^{k}-1)\) となる整数の組 \((i,j)\) の場合の数を数え上げる。これは \(B\) がソートしてあれば \(O(N)\) で解くことができる。

実装例 c++

この解法はソートする部分がボトルネックとなって計算量が \(k\) ごとに \(O(N\log N)\) なっていました。

しかし、 \(k=a\) のときに \(B_{i}\) がどの \(A_{j}\) に基づいているかが分かれば \(k=a+1\) のときに\(B_{i}\) がどの \(A_{j}\) に基づいているかは \(O(N)\) で求めることができます。

よって、ソートが \(O(N)\) でできるので、 \(k\) ごとに \(O(N)\) で求めることができます。

以上より全体で \(O(ND)\) つまり \(O(N\log \max A)\) で求めることができます。

(別の言い方をすると、radix sort を桁ごとに止めながら\(g(k,x)\) を求めているので、ソート全体の計算量は \(O(ND)\) です)

実装例 c++