Mister雑記

競プロやります。

数列をシャッフルすることでランダム性を持たせるテク

codeforces.com

Educational Codeforces Round 58-FEditorialに「Radewooshさんのブログのテクを使っても解けるよ」とあり、そっちを読んでみたら中々興味深いものだったので日本語でまとめることにした。タイトルは自分で考えたので、的外れだったら申し訳ない。

ちなみに以下の問題を解ける場所は現時点で存在しないとのことなので悪しからず。yukicoderとかで作れないかな。

問題

各要素が分からない長さ Nの数列 \{a_i\}がある。

このとき以下のクエリを 103000回以内行うことで、数列 aの最大要素を求めよ。

  • 整数 x, y ( 1 \leq x \leq N,  1 \leq y \leq 10^{18})を投げる。
  •  a_x \geq yかどうかが返ってくる。

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

制約

  •  1 \leq a_i \leq 10^{18}
  •  1 \leq N \leq 10^5

解法

愚直な二分探索

まずそれなりに競プロ慣れしている人なら、「各要素に対して二分探索を行う」方法が真っ先に思いつくだろう。

しかしこの解法では平均して N \log d回(ここで d = 10^{18})のクエリが必要であり、とてもじゃないが間に合わない。

小さい要素を切り捨てる

最大でない要素の値を求める必要はないことから、「境界値より小さい要素を切り捨てつつ、全体で一気に二分探索をする」という方法も考えられる。

具体的には「全要素に対して \frac{d}{2}を投げる」→「それより小さいものは全部切り捨てる」→「残ったものに対して \frac{3d}{4}を投げる」→...といった具合である。

しかしこの方法では、都合よく毎回半分ふるい落とされると仮定しても 2N1のクエリが必要となり、大半のケースでは間に合いそうにない。全ての値が dであるようなケースなら尚更間に合わない。

必要なときだけ二分探索

ここで注目すべきは、クエリ回数の上限が Nの上限にとても近いことである。ここから、上手くやれば大半の要素は1回のクエリでパスできる2ことが推測される。

そこで、以下のような解法が浮かんでくる。

まず、最初の解法と同様に「全要素に対して二分探索を行う」ことにする。ただし最初の解法と違う点として、二分探索前に「これまで見た中での最大要素」でクエリを投げ、これ以下であるようなら二分探索をせずパスすることにする。

もちろん数列が単調増加である場合など、偏ったケースでは N回二分探索をすることになってしまう。そこで本記事の核となるアイデアが出てくる。「数列にランダムな順番でアクセスすれば良いのでは?

つまり「 1 \sim Nをランダムに並び替えた順列を用意し、その順番通りに数列の値を求めていく」、ということである。これは数列をランダムにシャッフルすることに等しい。

クエリ回数の期待値

これでどれだけクエリ回数を削減できるのだろうか。そこでシャッフル後の数列にて最大値がどこにいるかを考えてみる。これはランダム性から、真ん中になるだろうと期待される。この最大値より右側の区間は調べる必要がないので、左側の区間について再帰的に考えればよい。

上の考察にて、最大値によって区間を分割する毎に区間長は半減すると期待される。ここから分かる通り、クエリ回数の期待値は O(\log N)程度になる。従って全体のクエリ回数は N + O(\log N \cdot \log d)まで抑えられる!

ちなみにクエリの猶予が 3,000であるのに対し、 \lg (10^5) \cdot \lg (10^{18}) \simeq 1,000であることから高確率で制限回数内に解が求まると予想される3

感想

  • 正直今の実力では応用できる幅が少ないテクだが、考え方はとても面白い。
  • 乱択は使いようだなぁという印象。

追記

以下のスライドに上のテクニックを含む、乱択に関する諸々のテクニックが載っているので参考までに。

www.slideshare.net


  1.  N + \frac{N}{2} + \frac{N}{4} + \cdots = 2N

  2. 各要素について最低1回はクエリを行わなければならないことに注意されたい。

  3. このスレッドによると、制限回数内で解が求まらない確率は 2.8 \cdot 10^{-18}程度だという。