久保 勉強会

利点

Nサイズの配列の探索がO(logN)でできる！

実装が楽

どんな時に使うのか

数値の組み合わせ（特にソートした方が良い場合）

～を満たす最大 (最小) の値を求めよ系の問題

解 x を仮定して可能かを判定する問題に置き換えて

解 x が可能となるような最大 (最小) の x を求める

今回の問題 (数値の組み合わせ)

https://scrapbox.io/files/6117a04798b22a001d2c6759.png

関数の部分を覚えれば、コピペで使える！！

code:swift

let N = Int(readLine()!)!

var A = readLine()!.split(separator: " ").map{Int($0)!}

var B = readLine()!.split(separator: " ").map{Int($0)!}

var C = readLine()!.split(separator: " ").map{Int($0)!}

A = A.sorted() //ソート

B = B.sorted() //ソート

C = C.sorted()　//ソート

func upper_bound(key:Int) -> Int{ //Cの祭壇の候補を調べる二分探索

//ここからはテンプレ

var left = -1

var right = N

while(right - left > 1){

let mid = left + (right - left) / 2

right = mid

}else{

left = mid

}

}

//ここまでテンプレ

return (N - 1) - right + 1

}

func lower_bound(key:Int) -> Int{ //Aの祭壇の候補を調べる二分探索

var left = -1

var right = N

while(right - left > 1){

let mid = left + (right - left) / 2

//基本的にはこの条件が変わる

left = mid

}else{

right = mid

}

}

return left + 1

}

var ans = 0

for i in B{ //B一つ一つについて、AとCの候補を調べる！

let up = upper_bound(key: i)

let low = lower_bound(key: i)

ans += up * low

}

print(ans)

時間があれば、、、

～を満たす最大 (最小) の値を求めよ系の問題

参考サイト