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

蟻本

二分探索（k番目を最小化、その他）

POJ 2010 - Moo University - Financial Aid(AC)

なんか昔解いてた。
メジアンを決めて、その下からN/2匹、上からN/2匹をコストが最も少なくなるように選んだときF以下になってるかどうかを判定する。
priority_queueなりmultisetなりを使って前計算すれば、後はO(C)。
二分探索…？

POJ 3662 - Telephone Lines

問題

ノード数N、エッジ数Pの重み付きグラフが与えられる。
このグラフのうち、エッジをいくつか選んでノード１とノードNを連結にしたい。
ここで、選んだエッジの重みの最大値がコストになるが、K本のエッジについては重みを0と考えることが出来る。
このとき、コストの最小値を求めよ。

制約

1<=N<=1000
1<=P<=10000
0<=K

解法

エッジを重みでソートし、何番目のエッジまでを考えるか（それ以降のエッジは重みを0としたい）で二分探索する。
ここで、頂点1から頂点Nを連結にするときにそれ以降のエッジを使わなければいけない個数をダイクストラ等で求める。
この個数がK以下かどうかで分岐する。

POJ 1759 - Garland

問題

数列hiは、

  • h1=A
  • hn=B
  • hi=(h(i-1) + h(i+1)/2 (2<=i<=n-1)

を満たす。
Aとnが与えられるので、hi>=0(1<=i<=n)を満たすような最小のBを求めよ。

制約

3<=n<=1000

解法

Bで二分探索した。
条件式は行列で表すと幅3の帯行列なので高速にガウスの消去法ができる。
h2で二分探索したらもっと簡単だったけど帯行列にまた少し慣れることが出来たしいいや。

POJ 3484 - Showstopper

問題

要素数n個の数列X[i],Y[i],Z[i]が与えられる。
この数列のi番目の要素は、X[i], X[i]+Z[i], X[i]+2*Z[i], X[i]+3*Z[i], …, X[i]+K*Z[i], …((X[i]+K*Z[i])<=Y[i])を参照したことを意味する。
このとき、全ての値が偶数回参照されるか、１つだけ奇数回参照されるかのどちらかである。

  • すべての値が偶数回参照されるなら、no corruption
  • １つだけ奇数回参照されるなら、その値と、何回参照されたか

を出力せよ。

制約

X[i],Y[i],Z[i]は32bit整数（正）
nは不明

解法

ある値xまでを考えた時、x以下の値が参照された回数の合計はO(n)で求めることが出来る。
この合計が偶数なら、奇数回参照された値はxより大きく、奇数ならx以下であることがわかる。
この考え方を用いて二分探索する。
ケースごとに空行が１つ以上入るという入力でだるい。