決め打ち二分探索【競技プログラミング】

# はじめに
- AtCoderの[ABC374のe問題](https://atcoder.jp/contests/abc374/tasks/abc374_e)の解法で、「決め打ち二分探索」というものが出てきたから、解説したい。なんか、名前が格好いいしね。
- 「決め打ち二分探索」が活躍するのは、「（或る条件下の）最大値を最小化」若しくは「最小値を最大化」するとき...と言っても、これだけじゃ何が何だか分からないよね。

# 問題例
- 長さNの数列が与えられ、K個の要素の数値を変更可能とする。このとき、同じ数字が連続する個数の最大値を最小化したとき、その最大値を求めよ。
- 例えば、長さ10の数列として、[3 3 3 3 4 4 4 4 4 4]が与えられ、Kが2なら、数列を[0 3 3 3 4 4 0 4 4 4]に変更し、答えは3になる。

# 考え方
- 問題例を考えたとき、連続している数値の最も長い部分列の真ん中の数値を変更して、長さを半減することを続けていけばいい気もするけど、そのやり方だと、8個の数列[1 1 1 1 1 1 1 1]の2箇所を入れ替えるときの最適解[1 1 0 1 1 0 1 1]（2個）は得られない。
- そこで考え方を変えることとする。
    - 普通の考え方
        - 与えられた数列Aに対し、変更可能個数Kの場合、解（最小化した最大値）はいくつとなるか？
    - 発想の転換
        - 与えられた数列Aに対し、変更可能個数Kの場合、<font color="green">←ここまで同じ</font>
            - Xは解となるか？　(X in 1...) →最初に解となったXが問題の答え。
- なるほど！これなら、解けそうですね...え？ちょっと待って？ニブタンは？
    - そうよね、ニブタン忘れてたよ。修正します
        - Xは解となるか？__（Xはニブタンで求める）__
- もちろん、計算量に余裕があれば(X in 1...)でも求められるけどね。

# 問題例の解
- 過去の投稿「[ニブタンのよくある使い方 -- solve関数とセットで使う](https://qiita.com/kei_tnk/items/85d14f6c835b83f1ed07)」の考え方で解ける。
```swift
let (N,K) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0],$0[1])}[0]
let A = readLine()!.split(separator:" ").map{Int($0)!}

// Aに含まれる連続数値の長さを配列化（Sに格納）します。
var S:[Int] = []
var len = 0
var old = A[0]
for i in 0..<N {
    if A[i] == old {
        len += 1
    } else {
        S.append(len)
        len = 1
        old = A[i]
    }
}
S.append(len)


// ニブタンのsolve関数を作ります。
// 配列A内の連続数値の長さsをxにするために必要な変換要素数kについて、初期値Kから減算していって、最後にマイナスにならなければ、xは解となる。 
func solve(_ x:Int)->Bool{
    var k = K
    for s in S { 
        k -= s / (x+1)
        if k < 0 {return false} // マイナスになったからアウト！
    }
    return true
}

// solve関数を使ったニブタンです
var ng = 0 // okの下限は1なので、それより1少ない0をngの初期値とする。
var ok = N / K + 1 // okの上限は数列のサイズNをK分割した長さだけど、割り切れない場合を考慮して+1している。
while ok - ng > 1 {
    let mid = (ng + ok) / 2
    if solve(mid) {ok = mid} else {ng = mid}
}

print(ok)
```
- うむ！考え方さえ分かれば、簡単ね。
- ......
- あれ？ちょっと待って？
- これって、普通に「solve関数を使ったニブタン」だよね？
- なんと！気づかないうちに、決め打ち二分探索をマスターしていたとは！
- でも、「solve関数を使ったニブタン」より、「決め打ち二分探索」の方が、言葉の響きがカッコイイ！これって、重要。

# [ABC374のe問題](https://atcoder.jp/contests/abc374/tasks/abc374_e)
- じゃあ、同じように解けるかな？
- 問題
![スクリーンショット 2024-10-09 21.33.10.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2733720/a9f586d9-0e2f-fbfe-39d3-40e2984db4bb.jpeg)
- これも、「決め打ち二分探索」を前提に考えれば、解法はパッと分かるね。
- 製造能力Wをsolve関数の引数として、solve関数は、予算X内で実現できればtrueを返し、予算Xを超過するならfalseを返せば良い。
```swift
let (N,X) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0],$0[1])}[0]

var apbqs:[(Int,Int,Int,Int)] = []
for _ in 0..<N {
    let v = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0],$0[1],$0[2],$0[3])}[0]
    apbqs.append(v)
}

func solve(_ w:Int)->Bool{
    var x = X
    for apbq in apbqs {
        x -= cost(apbq,w)
        if x < 0 {return false}
    }
    return true
}

func cost(_ apbq:(Int,Int,Int,Int),_ w:Int)->Int{
    let (a,p,b,q) = apbq

    // 機械Sを買う場合の費用
    let costS = (w / a + (w % a == 0 ? 0 : 1)) * p

    // 機械Tを買う場合の費用
    let costT = (w / b + (w % b == 0 ? 0 : 1)) * q
    
    return min(costA,costB)
}

var ok = 0
var ng = X * 100 + 1

while ng - ok > 1 {
    let mid = (ng + ok) / 2
    if solve(mid) {ok = mid} else {ng = mid}
}

print(ok)
```
- よし、出来た！楽勝だね！だって、そもそも単なる「solve関数を使ったニブタン」だしね！
- って、思うじゃん？
- まあ、「solve関数を使ったニブタン」としては、上記のコードであってるけど、この問題は、別のところに伏兵がいました...
- cost関数を見てほしいんだけど、行程iについて、機械SiもしくはTiのどちらかのみを選択可能なら、このcost関数で良いのよ。でもね、機械SiとTiを組み合わせ可能なのよね。つまりSiを2台とTiを4台みたいに購入可能。「決め打ち二分探索」とは別次元のところで、トラップが仕掛けられていたよ。

# 製造能力の異なる機械を効率よく買う考え方
- これって、プログラミングの話じゃなく、数学というかトンチの世界。
- 先に答えを見てほしい。
```swift
func cost(_ apbq:(Int,Int,Int,Int),_ w:Int)->Int{
    let (a,p,b,q) = apbq
    var ans = Int.max // 初期値は目一杯大きくしました 
    
    // 機械S（生産力A）の台数をi台とする
    for i in 0..<b {
        let costS = i * p
        let rem = w - i * a
        let costT = (rem / b + (rem % b == 0 ? 0 : 1)) * (rem < 0 ? 0 : q)
        ans = min(ans,costS + costT)
    }
    
    // 機械T（生産力B）の台数をi台とする
    for i in 0..<a {
        let costT = i * q
        let rem = w - i * b
        let costS = (rem / a + (rem % a == 0 ? 0 : 1)) * (rem < 0 ? 0 : p)
        ans = min(ans,costS + costT)
    }

    return ans
}
```
- 全探索で、無理くり求めています。
- でも、全探索と言っても、機械Sの台数が0..<b台、または、機械Tの台数が0..<a台に限定されています。ここで、aは機械Sの製造能力(個数)、bは機械Tの製造能力(個数)です。
- え？どうして、「機械Sの台数がb台以上」かつ「機械Tの台数がa台以上」となることがないのかって？
- ここがトンチ的な考えなんだけど、まず、「製品をa×b個」作るためには、「機械Sをb台」もしくは「機械Tをa台」で実現可能ですよね。ここまでは良いかな？
- で、どちらでも実現可能なら、当然、安い方を選ぶよね。
- つまり、製造したい個数wが「a×b」の倍数の時、機械Sもしくは機械Tのみを購入することとなるじゃん。
- よって、残りの「w % (a×b)」個の製造時のみ、機械Sと機械Tを組み合わせて製造することとなるってこと。
- ・・・その先は言う必要ないですよね。自分で考えてみてください。（トンボ風投げっぱなしジャーマン）
- ちなみに、cost関数をこっちに入れ替えて提出したら、5msでACでした。

# おわりに
- 決め打ち二分探索って言葉にワクテカしながら解いてみたら、たんなるsolve関数を使ったニブタンだったけど、まぁ良かったです。
- 「決め打ち二分探索」ってカッコイイ言葉を知っただけで満足。