(o_o)

ブログ。

KUPC2015 K SOULBLOCK

問題:
K: SOULBLOCK - 京都大学プログラミングコンテスト2015 | AtCoder


解法:
オブジェクト i がくっつくための射出角度の範囲を d_i (⊆ [0, 2pi)) とし,
オブジェクト i がオブジェクト j に (A, B の他にオブジェクトが無かったとして) 衝突する射出角度の範囲を c_ij としたとき,
各 d_i は以下の更新を繰り返すことで得ることができる.

d_j <- d_j ∪ (d_i ∩ c_ij)

しかし,これでは計算量が間に合わないため,適切な更新順序で DP する必要がある.

実は,原点からの接線の長さの順でソートすると,ほとんど適切な更新順序になる.
つまり,ほとんどの場合,接線の短いオブジェクトから長いオブジェクトへの更新しか起こらない.
一部,接線の長いオブジェクト i から短いオブジェクト j への更新が起こるが,このとき,任意のオブジェクト k に対し,

d_k ∪ (d_j ∩ c_jk) ⊆ d_k ∪ (d_i ∩ c_ik)

が満たされる (証明略) ため,それ以降の短いオブジェクトからの更新は行わなくてよい.
したがって,O(N^2) で解ける.

ちなみに,更新式が負コストの辺を含むグラフの単一始点最短経路長を求める更新式と似ていることから,SPFA などで高速化して通すこともできる.

gist.github.com