pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Codeforces Wunder Fund Round 2016 E. Robot Arm

蟻本に載ってる問題とほとんど同じ。

codeforces.com

解法

左図のアームの先端に右図のアームをくっつけることを考える。

f:id:pekempey:20160203170223p:plain:w260 f:id:pekempey:20160203170225p:plain:w260

こんな感じ。

f:id:pekempey:20160203170702p:plain

アームのマージが容易なのでセグメント木が使える。


複素数を使うと回転がさくっと書ける。

Codeforces Wunder Fund Round 2016 E. Robot Arm

蟻本のセグ木の例題として取り上げられている問題をちょっと変えただけの問題。 蟻本のあの例題はセグ木を知ってすぐの人には少し難しいと思うけどどうなんだろう。