ニブタンは整数だけじゃない【競技プログラミング】

# はじめに
- 二分探索（ニブタン）について、整数だけ使える手法と勘違いしてたので、反省を込めて投稿する。
- 整数だけじゃない、というのは、つまり､実数で使えると言うこと

# 実数でニブタンする例
- 最も分かり易い例は、下記入力例のような、「価格　重さ」のペアの配列（サイズn）があって、そのうち、m個を選択して、価格合計÷重さ合計を最大にさせるような問題となる。
```
3 2 // 3個から2個を選ぶ
50 10 //ペア① 価格50 重さ10
400 100 //ペア②
3 1 //ペア③
```
- 上記入力例を見て、ペア①の比率(価格/重さ)が5、ペア②が4、ペア③が3だから、比率の高い順に選べばいいだけじゃん！楽勝！と思っちゃった？残念！
- まあ、僕は素直なよい子だから、最初はそう思っちゃったけど、高い順に①②（450/110⇒4.09）を選択するより、①③（53/11⇒4.8）を選択した方が高いよ。
    - ペア①とペア②の組み合わせだと、ペア②の方が圧倒的に重いから、比率の平均はペア②の4に近くなる
    - ペア①とペア③の組み合わせだと、ペア①の方が圧倒的に重いから、比率の平均はペア①と5に近くなる
- じゃあ、どうやって、答えを出せば良いの？というと、当然、ニブタンを使うわけだけど、考え方は、以前投稿した、[ニブタンのよくある使い方 -- solve関数とセットで使う](https://qiita.com/kei_tnk/items/85d14f6c835b83f1ed07)で説明したsolve関数とセットで解く。
- solve関数をどうやって設定するかだけど、引数を一つだけ持ち、その引数がある閾値以上（以下）のときにtrue、ある閾値より小さい（大きい）ときにfalseになるように設定する。
- 今回、solve関数をどのように設定すれば良いだろうか？
- 素直に考えると、引数r(整数ではなく実数)に対し、ペアの組み合わせにより実現可能な「価格合計÷重さ合計」が存在するかどうか(true/false)という関数にすれば良い。--(※)
- r=0のときは、全ての組み合わせでokだからtrueとなり、rが非常に大きければ、全ての組み合わせでngなのでfalseとなる。そして、rが0から上昇していく間のどこかでtrueからfalseになり、その後trueに戻ることはないので、上記のsolveの条件(※)を満たす。
- それでは、solve関数を作ってみよう。
- 全てのペアn個中、m個を選ぶ場合、計算量は、${}_nC_m = \frac{n!}{(n-m)!m!}$だから、n=1000,m=3で$10^8$を超えてしまい、TLEとなる。よって、ペアの組み合わせを全探査するのではく、ペアをsortして、先頭のm個だけ使うようにしたい。
- とはいえ、何を指標としてsortすれば良いだろうか？「価格÷重さ」の順ではないことは既に分かってる。実は、「価格 - r×重さ」の大きい順のm個のペアを選択すれば良い。
    - そもそも、欲しい答えをr_ansとし、その時のペアの組み合わせでの価格、重さ合計を、価格合計_ans、重さ合計_ansすれば、「r_ans = 価格合計_ans÷重さ合計_ans」なので、これを組み替えると、「価格合計_ans - r_ans×重さ合計_ans = 0」であることから、「価格 - r×重さ」の大きい順のm個を選べば良い､っていうのは感覚として分かるかな？
    - solve関数についても、「価格 - r×重さ」の大きい順のm個の合計値が0以上であればtrueを返す関数とすれば良い。
- 結局、元の配列vws:[(v:Double,w:Double)]とした場合、与えられたrを用いて新たに配列vws_r:[Double]=vws.map{\\$0.0 - r * \\$0.1}をつくり、それをsortして、先頭のm個を使用することとなる。
- 上記の考えの元にsolve関数を作ると、次のとおり。
```swift
let (n,m) = (3,2) // ペア3個のうち、2個を選ぶ例
let vws:[(v:Double,w:Double)] = [(50,10),(400,100),(3,1)] // (v:価格、w:重さ) -- 前述のペア①②③の例

func solve(_ r:Double)->Bool{
    var vws_r = vws.map{$0.v - r * $0.w}
    vws_r.sort(by:>) // 降順でソート
    
    if vws_r[0..<m].reduce(0,+) > 0 {return true} else {return false}
    
}
```
- このsolve関数を利用するニブタンを実装すると、以下の通り
```swift
var ok:Double = 0
var ng:Double = 10

while ng - ok > 0.001 { // --　ここが重要！！！
    let mid = (ok + ng) / 2
    print(mid,ok,ng,solve(mid)) // 出力を参照
    if solve(mid){
        ok = mid
    } else {
        ng = mid
    }    
}

print(ok)
```
- ニブタンのコードで整数の場合と違う重要な点は、「ここが重要！！！」と書いているとおり、答えの精度をどうするかの設定となる。上記コードでは、最大0.001のズレを許容している。また、okとngの初期値は､適当に0と10としたが、これは、もともと答えが3〜5の範囲と分かっていたからであり、実際の問題を解く際は、適切に設定すること。
- 上記を実行したときの出力は以下の通り。
```
5.0 0.0 10.0 false
2.5 0.0 5.0 true
3.75 2.5 5.0 true
4.375 3.75 5.0 true
4.6875 4.375 5.0 true
4.84375 4.6875 5.0 false
4.765625 4.6875 4.84375 true
4.8046875 4.765625 4.84375 true
4.82421875 4.8046875 4.84375 false
4.814453125 4.8046875 4.82421875 true
4.8193359375 4.814453125 4.82421875 false
4.81689453125 4.814453125 4.8193359375 true
4.818115234375 4.81689453125 4.8193359375 true
4.8187255859375 4.818115234375 4.8193359375 false
4.818115234375
```
- 上記のループを抜けた段階で、ng=4.8187..、ok=4.8181..となり、okとngの差は0.001未満となっている。

# 実際のコンテスト問題
- [第一回 アルゴリズム実技検定 過去問の問題m](https://atcoder.jp/contests/past201912-open/tasks/past201912_m)が、まさに、前述の「実数でニブタンする例」を使って解ける問題となる。
- 解説は省略するけど、下記のコードでAC出来ました。
```swift
import Foundation

//タプル格納 整数
let (N,M) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0],$0[1])}[0]

//タプル配列
var abs:[(Double,Double)] = []
for _ in 0..<N {
    let (a,b) = [readLine()!.split(separator:" ").map{Double($0)!}].map{($0[0],$0[1])}[0]
    abs.append((a,b))
}

//タプル配列
var cds:[(Double,Double)] = []
for _ in 0..<M {
    let (c,d) = [readLine()!.split(separator:" ").map{Double($0)!}].map{($0[0],$0[1])}[0]
    cds.append((c,d))
}

func solve(_ f:Double)->Bool{
    var abs_f = abs.map{$0.1 - $0.0*f}
    var cds_f = cds.map{$0.1 - $0.0*f}    
    abs_f.sort(by:>)
    cds_f.sort(by:>)
    
    let sum0 = abs_f[0..<5].reduce(0,+)
    let sum1 = abs_f[0..<4].reduce(0,+) + cds_f[0]
    
    if sum0 > 0 || sum1 > 0 {return true} else {return false}
}

let min:Double = 0.0 // 検索範囲の最小値
let max:Double = 100000.0 // 検索範囲の最大値

var ok = min // 実数のため、-1不要
var ng = max // 実数のため、+1不要

while ng - ok > 0.0000001 {
    let mid = (ok + ng) / 2
    // print(mid,ok,ng,solve(mid)) // 出力を参照
    if solve(mid){
        ok = mid
    } else {
        ng = mid
    }
}

print(ok)
```

# おわりに
- 平均値の最大化に、ニブタンを使うとか、自分の発想にはなかった。
- やっぱり、競技プログラミングもある程度は、解法パターンを記憶するしかないのよね。