[CSA] Round #3 Moving Segments

Moving Segments

区間に対するクエリを処理する問題だと思いますが、解説の平面走査法が理解できませんでした。ですが、三分探索でも解くことができました。平面走査法を学んだら、この記事を更新しようと思います。

考え方

三分探索

二分探索でも解けると思いますが、三分探索の方がやりやすいと思ったので採用しました。三分探索については、

http://naoyat.hatenablog.jp/entry/2012/01/04/231801

が分かりやすいと思います。

\( x \) を三分探索によって見つけます。 \( x \) が 区間 \( [ l_i, r_i ] \) に含まれるときはコストはかかりません。そうでないときは、

\[ \min (|l_i – x|, ||r_i – x)\]

のコストがかかります。あとはコストの最小値を取る \( x \) を出力します。整数の三分探索は無限ループに陥る可能性があるので、回数を決めてループを抜けるようにしています。回数制限を設けないとすると、三分探索において同じ区間を複数回探索している場合にループを抜けるように記述することが考えられます。

ソースコード

感想

三分探索で解いても得られるものはあまりないので、平面走査法を学びたいと思います。螺旋本に平面走査法が載っているので読みます。この問題で平面走査法で解くことができたら追記します。

シェアする

  • このエントリーをはてなブックマークに追加

フォローする