Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2463-6a4a4e5f
この記事にトラックバックする(FC2ブログユーザー)

Timus 1990 - Podracing (この記事を編集する[管理者用])

Source

NEERC 2013 Eastern Subregional (2013-10-26)
Timus 1990

問題概要

レースのコースが与えられる.
車は $x$ 軸に平行な長さ $W$ の線分として,回転はできず自由に平行移動できる.
スタートからゴールできる最大の $W$ を求める問題.
コースは,左端を表す頂点数 $n$ 折れ線と右端を表す頂点数 $m$ の折れ線が与えられる.
それぞれの折れ線は,$y$ 座標方向に厳密に増え,互いに触れたり交わらない.
また,最初の点と最後の点の $y$ 座標の値は一致しており,そこがスタートライン,ゴールラインである.
スタートラインのどこからスタートしてもよく,ゴールラインのどこにゴールしても良い.
また, $q$ 個のカメラの位置が与えられる.カメラはコースの中か外とかはわからない.
車はカメラにあたってはいけない.
$2 \leq n,m \leq 10^5$
$0 \leq q \leq 10^5$
座標の絶対値は$10^9$以下

解法

折れ線の頂点,カメラのある位置の全ての $y$ 座標について,それを通過できる最大の車幅を求める.
それは,その $y$ 座標での障害物の $x$ 座標の位置をソートして最大の幅の場所を抜ければ良い.
コースの外のカメラは無視することを忘れないようにする.

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2463-6a4a4e5f
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。