Skip to content →

二分探索


\(f : \mathbb{N} \to \mathrm{Bool}\) なる関数について、\(f(L) \neq f(R)\) ならば、

  • \(f(R)=f(r)\)
  • \(f(L)=f(l)\)
  • \(r=l+1\)
  • \(L \leq l \leq r \leq R\)

となる \(l, r\) のペアが一つ以上存在し、ある一つが次のアルゴリズムで必ず取れる。計算量は \(O(\log(n))\)。

l = L
r = R
while (r - l > 1):
    m = (r + l) // 2
    if f(m) == f(L):
        l = m
    else:
        r = m

特に、インタラクティブ問題で鍵になることが多い。
長さ2N(Nは奇数)の+1/-1の列aが与えられる。+1/-1はN個ずつある。f(l) は区間 [l,l+N) の和が負なら True, 正ならば False を返す。[l, l+N-1)の和が0, a[l] != a[r] となるような l を求めよ。

a[0..i)の値の種類数をO(1)で得られる。a[0]以外が分かっている。a[0]と等しい箇所が他に必ず存在する。a[0]を特定せよ。


\(f : \mathbb{N} \to \mathrm{Bool}\) なる関数について、\(f(L) \neq f(R)\) ならば、

  • \(f(R)=f(r)\)
  • \(f(L)=f(l)\)
  • \(r=l+1\)
  • \(L \leq l \leq r \leq R\)

となる \(l, r\) のペアが一つ以上存在し、ある一つが次のアルゴリズムで必ず取れる。計算量は \(O(\log(n))\)。

l = L
r = R
while (r - l > 1):
    m = (r + l) // 2
    if f(m) == f(L):
        l = m
    else:
        r = m

特に、インタラクティブ問題で鍵になることが多い。

  • 長さ2N(Nは奇数)の+1/-1の列aが与えられる。+1/-1はN個ずつある。f(l) は区間 [l,l+N) の和が負なら True, 正ならば False を返す。[l, l+N-1)の和が0, a[l] \neq a[r] となるような l を求めよ(ddcc2020_qual_e)。
  • a[0..i)の値の種類数をO(1)で得られる。a[0]以外が分かっている。a[0]と等しい箇所が他に必ず存在する。a[0]を特定せよ。

\(f\) を \(\mathrm{Bool}\) への関数ではなく \(\mathbb{Z}/\mathbb{2Z}\) への関数だと思うと \(f(R) \neq f(L)\) は
\begin{align}
&f(L) \neq f(R) \bmod 2 \\
\Leftrightarrow &f(R) \pm f(L) = 1 \bmod 2
\end{align}
となる。例えば、\(f(i)=g(i)+i\) とすると、\(g(R)-g(L)+(R-L) = 1 \bmod 2\)となるがこれは次のような問題に使える。

  • \(L, R\) に座っている2人が異性かつ \(L-R\) が偶数
  • \(L, R\) に座っている2人が同性かつ \(L-R\) が奇数

のとき、区間 \([L, R)\) に空席があることが分かっている。空席を一つ見つけよ。長さ奇数の円環上に椅子が並んでいるときに空席を一つ見つけよ(APC001C)

Published in データ構造

Comments

コメントを残す

メールアドレスが公開されることはありません。

CAPTCHA