Document

Robots Crash
問題作成:荒木
解答作成:荒木、牟田
英訳:荒木
解説:荒木
問題
• 二次元平面上に半径r
の円形のロボットがn台
(2<=n<=100000)ある。
ロボットはそれぞれvま
たは-vの速度で等速直
線運動する。最初にロ
ボットが衝突する時刻
を求めよ。ロボットが衝
突しない場合はSAFE
と出力せよ。
解法①
• ナイーブにロボットのペアすべてを列挙して、
その衝突時刻の最小値をとると当然TLE
(Time Limit Exceeded)。
• また、昨年の夏合宿でチームkitsune-が行っ
た「原点からの距離でソートして、三角不等式
を使ってロボット間の距離の下限を求め、そ
れで枝狩り」も、原点からの距離が同じくらい
のところにロボットが多数あるとまずい。
• ロボットの集合をうまく分割する必要がある。
解法②
• まず、速度vがx軸と平行になるように、原点
を中心に回転する。
• それから「y座標の距離が2r未満のもののう
ち、速度の向きが逆で、x座標が近いもの上
位3個のペアの衝突時間を調べる。」という操
作を行い、その衝突時間の最小値を求める。
• 理由は次ページのスライドから。
解法③
• y座標の距離が2r未満
の物のみ調べる理由…
右のような状況に対処
するため。
解法④
• 速度が逆向きの物のみ調べる理由…下のような状
況に対応するため
解法⑤
• x座標が近いもののみ調べる理由…以下のような状
況に対応するため。
解法⑥
• x座標が近いもの上位3
個を調べる理由…右の
上図のような状況(右に
ある二つの円のうち、
下のほうが遠いが、先
に衝突する)に対応する
ため。なお、右の下図
より、4個以上調べる必
要は無いことがわかる。
実装例(擬似コード)①
• まずY座標でソートしておく。
• set<Robot> s1, s_1;
• ↓ループ↓
– set<Robot> new_inserted;
– ↓ループ↓
• 現在調べているロボット集団の一番下のものから、Y
座標の差が2*r以内のものを追加していく。
• ただし、右向きだったらs1に、左向きだったらs_1に。
• また、new_insertedにも追加する。
実装例(擬似コード)②
– ↓new_insertedの各要素iterに対してループ↓
• Iterが右向きなら、s_1にiterをinsert.
• findしてinsertされた位置を見つける。
• その位置から右に三個分だけs_1の要素を取り出して、衝突時間
を調べて最小値をとる。
• s_1からiterをerase
• Iterが左向きなら、s1にiterをinsert
• findしてinsertされた位置を見つける。
• その位置から左に三個分だけs1の要素を取り出して、衝突時間
を調べて最小値をとる。
• s1からiterをerase
実装例(擬似コード)③
– 今調べた集合の最も上のロボットの一つ上のロ
ボットからのY座標の差が2rを超えるのものを
s1,s_1からerase
結果
• Submit:9
• Accept: 0

Download Report