# 二分探索

## 解を仮定し可能か判定（答えで二分探索）
いわずとしれたこの問題
https://atcoder.jp/contests/abc023/tasks/abc023_d

## 最小値の最大化（最大値の最小化)
単調性があり、あるところで可能不可能がわかれるので二分探索がつかえる

# 分数を探索する系

## 平均最大化
やってないとむりな気がする。

> 問題文
> 重さと価値がそれぞれw_i,v_i,であるようなn個の品物があります。この中からちょうどk個選んだときの単位重さあたりの価値の最大値を求めなさい。
>
> $1 \leq k \leq n \leq 10^4$
$1\leq w_i,v_i \leq 10^6$

解法

> 判定問題
> $C(x):=$単位重さあたりの価値がｘ以上となるように選ぶことができる
>
で、xを二分探索する。
単位重さあたりの価値がｘ以上となるとき

$x\leq\frac{\sum_{i\in S}v_i}{\sum_{i\in S}w_i}$
$\Leftrightarrow x\sum_{i\in S}w_i\leq\sum_{i\in S}v_i$
$\Leftrightarrow\sum_{i\in S}xw_i\leq\sum_{i\in S}v_i$
$\Leftrightarrow0\leq\sum_{i\in S}(v_i-xw_i)$

つまり、$v_i-xw_i$が大きい順に貪欲にiを選ぶことで判定問題が解ける。
ソートがボトルネックで判定問題は$O(N\log N)$

$x\leq \max_{i\in S}(v_i)$
より
$O(\max_{1\leq i\leq n}(v_i)N\log N)$

いろいろあります最近だとこれ
https://atcoder.jp/contests/abc294/tasks/abc294_f

#### K番目
・Kがでかいとき
→二分探索
上のやつとか

→ダブリング

→周期性

・Kが小さいとき
→K番目までもっておく。
https://atcoder.jp/contests/abc297/tasks/abc297_e
（これはNが小さいのが効いてるけど）

## 連分数展開・Stern–Brocot tree
わかりませんでした下に書いてあることは間違ってないけど証明が抜けまくっておりおしまい

Stern–Brocot treeはノードに有理数を当てた二分探索木で、以下のうれしい性質を満たします。
* すべての既約分数がちょうど一度ずつ現れる
* 扱う既約分数は単調増加である
* より深い既約分数は、分子または分母の値がより大きい

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1208


まず、以下の数列を導入する。

### ファレイ数列

> 自然数 n に対して、n に対応する（または、属する）ファレイ数列 (Farey sequence of order n) Fn とは、分母が n 以下で、 0 以上 1 以下の全ての既約分数を小さい順から並べてできる有限数列である。 ただし、整数 0, 1 はそれぞれ分数0/1, 1/1として扱われる。
> from wikipedia


木っぽく表現


### Stern–Brocot tree

次のように定義される2分木のこと．

* 頂点は区間
* 根は区間(0/1, 1/0) つまり(0, ∞)
* 頂点(x/y, z/w)の子は，( x/y, (z+x)/(y+w) )，( (z+x)/(y+w), (z/w) )

ちょっと違うけどイメージ↓

https://satashun.hatenablog.com/entry/2018/12/13/163524


$p=\frac{a}{b},q=\frac{c}{d}$
の間に
$\frac{a+c}{b+d}$
を書く
> 例えば$\frac{1}{4},\frac{2}{5}$の間には
> $\frac{3}{9}=\frac{1}{3}$
> をかく

> ここで$\frac{a}{b}\leq \frac{a+c}{b+d}\leq \frac{c}{d}$である。

$\frac{a}{b}\leq \frac{c}{d}$の下で、$ad\leq cb$であるから
$ab+ad-ab-cb = ad-cb\leq 0$
つまり
$\frac{a}{b}\leq \frac{a+c}{b+d}$
よって
$\frac{a}{b}\leq \frac{a+c}{b+d}\leq \frac{c}{d}$
（右側の不等式も同様に示せる）

これにより、単調増加な有理数列が生成される。

単調増加→かぶりない

## 並列二分探索
https://atcoder.jp/contests/code-thanks-festival-2017-open/tasks/code_thanks_festival_2017_h

https://betrue12.hateblo.jp/entry/2019/08/14/152227

並列二分探索は以下のような形式の問題を解くことができるテクニックです。

> M個の操作からなる操作列があり、何らかの対象（数列や集合など）に対して順番に操作される。
> 以下のような形式の質問が Q個あり、これら全てに答える必要がある。
>
> 「対象がある条件 qiを初めて満たすのは、操作列の中の何番目が操作された後か？」
>
> 単調性がある。ある時点での操作の後に条件を満たすならば、それ以降はずっと条件が満たされている

今回なら、各クエリごとに二分探索を行うけど、l,r,midはそれぞれ持っておく、で、判定問題は、前からunionfindでシミュレートとして、i = midのタイミングで判定する（だいたい$O(n+m\alpha(n)+Q\alpha(n))$ ) （ｍ回マージするので）

全体$O(\log m(n+m\alpha(n)+Q\alpha(n)))$
これもそう
https://atcoder.jp/contests/agc002/tasks/agc002_d

# テクニック

## しゃくとり

## 反転
* 1問目
これはimos法的に区間の反転を表現しているといえる

* 2問目
lights outまんま

https://ja.wikipedia.org/wiki/%E3%83%A9%E3%82%A4%E3%83%84%E3%82%A2%E3%82%A6%E3%83%88

解の存在性は、連立方程式の議論に帰着される。

## 弾性衝突
Antsと同じ
衝突をすりぬけさせる

## 半分全列挙
半分全列挙とは、いくつかのパーツを半分ずつのグループに分け、全探索（全列挙）を高速化するテクニックのことを指します。

個人的に面白い問題。
[e8さんの記事](https://qiita.com/e869120/items/72cc1370cbc0da1be9ef#9-15-%E3%83%91%E3%82%BA%E3%83%AB%E3%81%A7%E5%BD%B9%E7%AB%8B%E3%81%A4%E5%8D%8A%E5%88%86%E5%85%A8%E5%88%97%E6%8C%99%E3%81%A8%E6%9E%9D%E5%88%88%E3%82%8A%E6%8E%A2%E7%B4%A2)

* 愚直

* 半分全列挙
「ちょうど30 手でゴールできるか」を考えましょう。

* 最初の盤面から
15手動かしたときのあり得る状態$U_i$は$4^{15}$通り
* 目標の盤面から
15手動かしたときのあり得る状態$V_i$は$4^{15}$通り

このとき、$U_i=V_j$となるようなi,j の組が存在すれば、よく、これはソートした後、二分探索をすれば高速に判定できます。

$O(4^{n/2}\log(4^{n/2}))$

## 巨大ナップサック
ナップサックのwとvが$10^{15}$。
いつものナップサック$O(nw)$では無理。
$n\leq 40$
に注目して、半分全列挙を考える。
nを半分に分けるこれは高々20。$2^{20}$くらいなら全列挙できる。
ある選び方で、重さの総和が$w_1$,価値の総和が$v_1$になったとすると、もう半分の方では、重さ$w_2\leq W-w_1$なる$v_2$の最大を選べばよい。

重さが重いが価値が薄いようなものは考えなくてよいつまり、

$w_2[i]\leq w_2[j] かつv_2[j]\leq v_2[i]$

上記のようなi,jのペアがあるとき、jは考えなくてよい。
これは$(w_2[i],v_2[j])$でソートして、$w_2$が小さい順にみていく。各$w_2$の値について最大の$v_2$の値を見て、これまでの最大の$v_2$の値よりでかければ、採用。更新。

答えになり得る$w_2[i],v_2[j]$のペアだけをこのアルゴリズムで取り出すと、

$w_2[i]\leq w_2[j] \Leftrightarrow v_2[i]\leq v_2[j]$

であるから、$w_2$を二分探索すれば、各$w_1,v_1$のペアごとに、$v_1+v_2$を最大にする$v_2$を$O(\log 2^{n/2})$で求められる。

よって、$O(2^{\frac{n}{2}}\log 2^{n/2})$