人間だけど競プロやる

解けなかった問題を理解できたら記事を投稿します。日本語の解説が見つからなかったもの中心。

Codeforces Round #735 (Div. 2) B. Cobb

Codeforces

いまいち確信が持てないが、ACできたので書く。

数式を睨むと、 $i \times j$ は $N^2$ 程度まで大きくなるのに対して、 $(a_i | a_j)$ は $N$ よりちょっと大きい程度に抑えられるとわかる。
つまり基本的にはiとjの積が大きくなる、aの後ろの方を選ぶのが良さそう。

$O(N^2)$ は間に合わないので、 $i$ を固定して考えたい。
$i$ を1からNまで試すとき、 $j$ を試す範囲を狭くしたい。

求める最大値の下限を見積もる

$\displaystyle{i \times j - k(a_i | a_j) }$

について $i \times j$ の最大値は明らかに $N \times (N-1)$ 。
$(a_i | a_j)$ が大きいほど、与式の値は小さくなるので、 $(a_i | a_j)$ の最大値を知りたい。これは、Nを2進数で見たときに、各桁が全て1になってるいる状態と見て良い（ $\because a_i \le N$ ）。
（たぶんおそらく） $(a_i | a_j)$ の最大値は、 $2 \times N$ くらいになる（= $(N << 1)$ ）。
よって、

$\displaystyle{ i \times j - k(a_i | a_j) \ge N(N-1) - K \times 2N }$

$\displaystyle{ j \ge \frac{k(a_i | a_j) + N(N-1) - K \times 2N}{i}}$

右辺が小さいほど、 $j$ の取る範囲は広がるので $(a_i | a_j) = 0$ と仮定して、

$\displaystyle{ j \ge \frac{k(a_i | a_j) + N(N-1) - K \times 2N}{i} \ge \frac{ N^2 -2(k+1)N}{i} = d}$

とする。

以上から、iを1からNまで試して、それぞれのiについて、jを（この式はマイナスになり得るので、0とmaxをとって）dからNまで試した計算結果のmaxを答えてAC。

計算量の見積もりは？
たぶん $O(N \times \log{N^2})$ になるのかな？
$\sum_{i = 1}^{N}{\frac{N^2 -2(k+1)N}{i}}$ と和をとって、調和級数の見積もりになるんだと思われる。
自信なし。