yukicoder contest 218 E - ヘビの日光浴

E問題の解説です。

問題

問題文、説明が難しいのでこっち読んでね。

さて、ヘビの移動について実際にシミュレーションしていきましょう。
各ヘビについて、正面のヘビとぶつかるか？は簡単に求められるかと思います。
同じ座標のヘビについて簡単に判定できれば良いので、座圧しておけばインデックスと対応します。
次に、左右のヘビとぶつかるかを考えます。
これは、左右のヘビそれぞれについて、自分とぶつかる長さ以上のヘビのうち最も近い位置のヘビがぶつかる位置ならぶつかります。
これはセグメント木上の二分探索を行うとで判定することができます。
よってアルゴリズムとしては解くことができます。
実装に関しては、セグメント木4本を左右それぞれ二分探索する必要があるなどかなり重い実装を要求するので注意してください。

感想

実装が面倒な典型問題ですね。
セグメント木の二分探索における典型問題なので、verifyなどにお使いください。
正直writerは間違えた、これ難しい！()
とはいえ元は典型なので★3かなぁとかやっていましたが、本番で全然解かれなかったら★5に一瞬なりました。
えー……流石にそんな難易度は無いよね？
これICPCの時期に作問したからかなり重実装なのですが、正直これくらいは実装できないとICPCでは苦戦すると思うのですよ……。