この記事の内容は、 Blogewoosh #6 の内容に基づいています。

問題

長さ $N$ の数列 $\{a_i\}$ がある。各要素の値は明かされていない。 以下のクエリを $103000$ 回以内行うことで、数列 $a$ の最大値を求めよ。

各クエリでは、 $1 \leq i \leq N, 1 \leq x \leq 10^{18}$ を満たす好きな整数 $(i, x)$ を投げる。 すると、 $a_i \geq x$ かどうかが返ってくる。

ただしこの問題は adaptive ではない (クエリに依らず、数列は固定されている)ものとする。

制約

• $1 \leq a_i \leq 10^{18} (= D)$
• $1 \leq N \leq 10^5$

解法

まず競プロ慣れしている人なら、「各要素に対して二分探索を行う」という解法が真っ先に思いつくだろう。 しかしこの解法でのクエリ数の期待値は $N \log_2 D$ 回であり、とてもじゃないが間に合わない。

そこで枝刈りを入れてみることにする。 求めたいのは最大値だけなので、それまでの最大値以下であることさえ分かれば、二分探索は必要ない。 そこで最初にそれまでの最大値を投げ、それ以下であることが確定したらスキップすることにする。

しかしこれでも数列が単調増加の場合、全ての要素に対して二分探索することになってしまう。 もし入力がランダムなら 、単調増加列のような入力は滅多に現れないのだが……。

ここで本記事のメインである、「数列をランダムにシャッフルする」というアイデアが役に立つ。 入力を直接シャッフルすることはできないが、 要素を調べる順番をシャッフルする ことで、擬似的に入力をシャッフルできる¹。

クエリ数の評価

簡単のため、以降数列 $\{a_i\}$ に重複はないものとする。 また、どうせランダムな順番にアクセスするので、 $\{a_i\}$ は単調減少と仮定しても一般性を失わない。

$a_i$ に対して二分探索を行う、すなわち $a_i$ がこれまでアクセスした全要素より大きい確率を $p_i$ とする。 すると期待値の線形性より、二分探索が行われる回数の期待値は $\sum_{i = 1}^N p_i$ となる。

後は $p_i$ の値を求めればよい。先に述べた通り、これは「$a_i$ がこれまでアクセスした全要素より大きい確率」である。 さらに $\{a_i\}$ は単調減少なので、これは「$a_1, a_2, \dots, a_i$ の中で、 $a_i$ に最初にアクセスした確率」に等しい。 対称性より、 $a_1, a_2, \dots, a_i$ のどれに最初にアクセスするかは等確率である。したがって $p_i = \frac{1}{i}$ となる。

以上より、二分探索が行われる回数の期待値は、 $\sum_{i = 1}^N p_i = \sum_{i = 1}^N \frac{1}{i} \simeq \log_e N$ となる。 二分探索 1 回のクエリ数は $\log_2 D$ 回なので、総クエリ数の期待値は概ね $N + \log_2 D \cdot \log_e N$ となる。

$N = 10^5, D = 10^{18}$ にて、期待値は $101000$ 以下となる。 期待値だけではクエリ数が制約を超える確率は評価できないが、 $2000$ 回の余裕があるので、十分な確率で解けると思っていいだろう²。