ニブタンのよくある使い方 -- solve関数とセットで使う【競技プログラミング】

はじめに

• ニブタン（二分探索）については、過去2回ほど投稿（一致検索、近似検索･lowerbound）したけど、もっと一般的な使い方を書いてないよなぁ、と思ったので、今回は、競技プログラミングで多く使われる場面（solve関数とセットで使用）をswiftで書いてみる。

基本的な形

• よくある利用パターンは、こんな感じ。

func solve(_ n:Int) -> Bool {
    let ans = 77
    if n >= ans {
        return true
    } else { 
        return false 
    }
}

let min = 0 // 検索範囲の最小値
let max = 100 // 検索範囲の最大値

var ng = min - 1 // 解が存在しない側(左側)の開始位置 -- ループ毎に「同位置」or「中間値」へ移動
var ok = max + 1 // 解が存在する側（右側）の開始位置 -- ループ毎に「同位置」or「中間値」へ移動

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

print("解答：",ok) // 出力を参照

/// 出力
50 101 -1 false
75 101 50 false
88 101 75 true
81 88 75 true
78 81 75 true
76 78 75 false
77 78 76 true
解答： 77

• solve関数は、ある数値ans(上記では77)未満ではfalse、以上ではtrueとなるような関数であり、ニブタンでは検索範囲(上記では0〜100)の中でsolve関数を満たす最小の値を出力する。
• 上記のニブタン計算の手法では、正解値ans未満(左側)の変数をngとし、正解値ans以上(右側)の変数をokとして、ngとokを徐々に近づけてゆき、okとngが隣同士(ok-ng=1)となったときにループを抜ける。よって、変数ngの開始位置は「検索範囲の最小値(min) - 1」とする必要がある。
• もし、solve関数のans=0のとき、ngの開始位置をminとしてしまうと、print(ok)では、ok=1となってしまい、ans=0と一致しない。
• また、ans=200のとき、okの開始位置をmaxとしてしまうと、print(ok)では、ok=100となってしまい、ans=200と一致しない。とはいえ、okの開始位置が元々の「max + 1」のままでも、print(ok)では、ok=101となりans=200と一致しないが、少なくとも、ok=101の結果から、検索範囲0〜100の間にansが含まれないことは確認できる。

実際の問題での利用

• AtCoderの競プロ典型90問の栄えある第1問で利用する。
  
• 入力例はこんな感じ

# 入力形式
N L
K
A[1] A[2] A[3] ... A[N]

----------

# 入力例 1
7 45
2
7 11 16 20 28 34 38

# 出力例 1
12

• ニブタンを利用するのは､理解したとして、そのためにはsolveをどう書けば良いかがキモとなる。
• 今回は、ヨウカンの「一番小さい一切れ」を「可能な限り長くしろ」という問題。よって、solve関数については、「特定の長さ」以上になったとき、「切り分けられない」をtrueとすれば、「特定の長さ − 1」が求める解となる。
• もしくは、ニブタンのアルゴリズムの方を「特定の値以下(左側)」をtrue、変数をokとし、「特定の値超(右側)」をfalse、変数をngとして、solve関数を「特定の長さ」以下の場合に「切り分けられる」をtrueとすれば、「特定の長さ」が求める解となる。
• ニブタンを利用しても、どのように解くかは、人それぞれだと思うけど、個人的には、ニブタンのアルゴリズムはあまり動かしたくないので、前者の方法で解こうかと思う．．．って思うじゃん？
• でも、前者の方法は駄目なのよね。何故なら、切り分ける長さは、1刻みじゃ無いんだよね。数列Aにより、1番小さい一切れの長さは、1刻みでは無く、飛び飛びの値となる。よって、後者の方法で解くこととする。

let (N,L) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0],$0[1])}[0]
let K = Int(readLine()!)!
let As = readLine()!.split(separator:" ").map{Int($0)!}


// ヨウカン一切れの長さをnとして、切り分け可能なときをtrueとする
func solve(_ n:Int) -> Bool {
    var l = L // 切断後の長さをlとする
    var k = 0 // 切断回数（切った回数がkの場合、ヨウカンの個数はk+1)
    var i = 0 // 切断可能位置A(i)のindex
    var oldA = 0 //前回の切断位置
    while true {
        let temp = As[i] - oldA // 前回切り取り位置からの長さ
        if temp >= n { // カット可能な長さ
            k += 1
            l -= temp
            if l < n {return false} // ループ終了（切り取れなかった）
            if k == K {return true} // ループ終了（切り取れた）
            oldA = As[i] // 前回位置を更新
        }
        i += 1
        if i == N {return false} // ループ終了（切り取れなかった）
    }
}

let min = 1 // 検索範囲の最小値
let max = L/(K+1) + 1 // 検索範囲の最大値

var ok = min - 1 // 解が存在しない側(左側)の開始位置 -- ループ毎に「同位置」or「中間値」へ移動
var ng = max + 1 // 解が存在する側（右側）の開始位置 -- ループ毎に「同位置」or「中間値」へ移動

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

print("解答：",ok) // 出力を参照

• 上記について説明すると、solve関数は、まぁ見れば分かるよね。ニブタンの方は、若干修正した。
• まず、変数ok,ngについて、okを左側領域、ngを右側領域としている。また、これに併せて、whileの条件をabs(ok - ng)として、okが左側領域、右側領域のどちらでも使えるようにしている。

おわりに

• 今回のニブタンのsolve関数とセットで利用する方法はかなり使うので、短い時間ですぐに思い浮かべるようにしたいね。

おまけ

• 整数以外でもニブタン使えるので、サンプルを置いておく

///実数版

func solve(_ r:Double) -> Bool {
    let ans = 77.0 // 小数リテラルはDoubleで認識される
    if r >= ans {
        return true
    } else { 
        return false 
    }
}

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

var ng = min // 解が存在しない側(左側)の開始位置 -- ループ毎に「同位置」or「中間値」へ移動
var ok = max // 解が存在する側（右側）の開始位置 -- ループ毎に「同位置」or「中間値」へ移動

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

print("解答：",ok) // 出力を参照

• 上記のキモは、whileループのtrue条件「ok-ng > 0.1」が求める答えの精度を決めている点。
• 上記コードでは、solve関数の答えが77点だと予め分かっているが、どのような経過で答えが確定するだろうか？
• 出力を見ると下記のとおりであり、解答77.050..は、当然、77.0以上のsolveのtrueゾーンにいるが、77.0丁度ではなく､77.0から0.1の範囲内に収まっている。

50.0 100.0 0.0 false
75.0 100.0 50.0 false
87.5 100.0 75.0 true
81.25 87.5 75.0 true
78.125 81.25 75.0 true
76.5625 78.125 75.0 false
77.34375 78.125 76.5625 true
76.953125 77.34375 76.5625 false
77.1484375 77.34375 76.953125 true
77.05078125 77.1484375 76.953125 true
解答： 77.05078125

• 小数でのニブタンを利用する投稿も別途しているので､参考にして欲しい。