[AtCoder] ABC 136 D – Gathering Children

問題

方針

子どもの移動の挙動

どのような文字列でも十分に移動を行うと、’RL’ または ‘LR’ という二つのマスを行き来することになります。また、’RL’ という文字列が与えれたとき、初めに ‘R’ にいた子どもは、偶数回の移動で ‘R’ にいることになるので、\( 10^{100} \) 回の移動では、’R’ にいることになります。

各マスの情報

各マスのどのような情報が知りたいかというと、マス \( i \) を含めて右側の最も近い ‘R’ の要素番号 \( i_r \) と左側の最も近い ‘L’ の要素番号 \( i_l \) です。

マス \( i \) が ‘R’ のとき、マス \( i_l \) まで右側に進む事になり、あとは ‘RL’ という文字を行き来するだけになります。したがって、\( i_l – i\) が偶数ならば、マス \( i_l \) にいることになり、奇数ならば \( i_l – 1 \) にいることになります。

一方で、’R’ のとき、マス \( i_r \) まで左側に進む事になり、あとは ‘LR’ という文字を行き来するだけになります。したがって、\( i – i_r \) が偶数ならば、マス \( i_r \) にいることになり、奇数ならば \( i_r + 1 \) にいることになります。

コード