蟻本練習問題埋め3-1(2)

蟻本

二分探索（平均最大化,k番目の値を検索）
二分探索における現在の区間の中央の値をxと表す。
それにしてもPOJは時間制限キツイなあ。

POJ 2976 - Dropping tests

蟻本通り

POJ 3111 - K Best

蟻本通り

POJ 3579 - Median

問題

長さNの数列Xiが与えれる。

Xi - Xj∣を全てのi,j(1 ≤ i ＜ j ≤ N)について考えたとき、そのメジアンを求めよ。
制約

Xi ≤ 1,000,000,000 3 ≤ N ≤ 1,00,000

解法

メジアンは、昇順にソートしたとき(N*(N-1)/2-1)/2番目の値である（0-origin)。
メジアン値で二分探索する。
このとき、[Xi-x, Xi+i]に含まれるXj(i!=j)の数を二分探索で求め、その和が(N*(N-1)/2-1)/2を超えるかどうかで分岐する。

POJ 3685

問題

N次正方行列Aは(i,j)成分が
i^2 + 100000 × i + j^2 - 100000 × j + i × j,
で定められる。
このとき、M番目に小さい要素の値を求めよ。

制約

1 ≤ N ≤ 50,000
1 ≤ M ≤ N × N

解法

答えで二分探索。
それぞれの反復で、x以下の要素の数を求めたい。
各成分の求め方を見るとiについては単調であることが分かるので、各jごとに値がx以下となるようなiの個数を二分探索で求めることが出来る。
O(log(R)*N*log(N))
ここでRは要素の値の幅で10^11くらいを考えればいい。