2020/5/6

CODE THANKS FESTIVAL 2017 H

並列二分探索

同じ集合である時間とそうでない時間の境界がある→二分探索

各クエリごとに二分探索をしていると間に合わない→並列二分探索

 

簡単のため、二分探索の走査範囲を[0,N]とする

二分探索で必要となる情報は、ある値midに対して条件を満たすかどうか(求めたい”境界の値”はmidの左側と右側のどちらの区間に含まれるのか)

midを一段階進めるごとに、境界の値が含まれる区間の長さが半分になっていく(最初の区間を細かくしていく)

 

Q回の二分探索で見るmidの個数はは高々QlogN

条件を満たすかどうかの判定に、mid一つ当たりX回の計算が必要な場合、最終的にQXlogN回の計算が必要になってしまう

二分探索ごとにX回計算しているのを、一度X回計算した結果を毎回の二分探索に流用することで、計算量をO((Q+X)logN)にしようという話

 

この問題の場合、条件を満たすかどうかの判定にM回の集合をmergeする操作が必要

愚直に二分探索をすると、M回の計算をしてmidを一つ進めることができる

並列二分探索は、Q個のmidを同時に管理して、M回の計算で各midを同時に一つ進めている

 

結局並列二分探索が適用できるのは、二分探索ごとに条件判定のための処理が同じとき(条件判定の処理を使い回せるとき)

 

 

2017-2018 ACM-ICPC Latin American Regional Programming Contest I

最小値

クエリ(a,b)に対して、MSTのコスト+辺(a,b)のコスト-MSTのa-bパス上の最重辺のコストを答える

クラスカル法でMSTを作る際に、頂点aとbが何回目の辺追加の際につながったかを並列二分探索で求める

MSTのa-bパス上の最重辺のコスト=クラスカル法ではじめてa-bがつながった時に追加した辺の重み

 

二分探索の上界を雑に取りすぎるとmidに入らずに大変なことになる、注意

 

 

Codeforces 1344 B

盤面構築+最小値

一行ごとに考えると、W...(B...)W....の形になっている必要があることが分かる

→各行、列について判定

どの行、列にもSが必要

→Bが存在しない行(列)だけが存在する場合は不可能