AtCoder Beginner Contest 136：D - Gathering Children

問題
解法
解答

問題

https://atcoder.jp/contests/abc136/tasks/abc136_d

解法

操作の回数が十分に大きいので，子供たちは "RL" となっているような 2 つの連続するマスを行き来するようになる．子供のいるマスが R であるとき，そのマスより右にある最も近い L のマスとの距離，また，子供のいるマスが L であるとき，そのマスより左にある最も近い R のマスとの距離の偶奇によって子供の最終的にいる位置は決まる．最も近い X のマスは，L と R のマスがある位置をソートしておくことで二分探索で求まる．O(|S|log|S|)．