問題
Educational Codeforces Round #10-F : Ants on a Circle
蟻は1秒に付き1cm、円周上を一定の向きに動き続ける。
蟻が円周上でぶつかると、お互いに向きを変えて反対方向に動き出す。
各アリの初期位置 \( s_{i} \) と向き \( d_{i} \) が与えられるので、\(T\) 秒後の蟻の位置を答えよ。
- $1 \leq n \leq 3 \times 10^5 $
- $1 \leq m \leq 10^9 $
- $0 \leq T \leq 10^{18} $
蟻の最終位置は簡単にわかる
蟻を区別しない場合、ぶつかるときの処理を無視して単に通り抜けるだけ、としてよい。なので、各蟻が独立して与えられた向きに $T$ 秒間動き続けると考えると、蟻の最終位置が得られる。これをソートした列を $q$ とおいてあとで参照する。
問題は、これらがスタート地点でそれぞれどの蟻だったか、である。
蟻の順番は変化しない
蟻の初期位置をソート*1*2した列を $p$ とおく。また、ソート済での順番で数えて、左から $x$ 番目の蟻を $a_x$ とおく。
これが $T$ 秒後どこに行くか、を以下の図を描いて考えよう。
すると、例えば $a_0$ (青い線) を基準に考えると、$a_0$ の一つ右は $a_1$ (赤い線) だし、一つ左は $a_3$ (オレンジの線) である。他の蟻についても同じことが成り立っている。つまり、蟻の相対的な位置は変化しない。 このことは、特定の蟻に着目して、シミュレーション中にぶつかる可能性のある蟻について考えると分かる。
したがって、$a_0$ が最後に来る位置 $q_x$ が分かれば、他の蟻 $a_i$ の位置は $ q_{x+i} $ で与えられる。
蟻が何匹追い越すか？
$a_0$ が $T$ 秒後にどの位置にいるかを考えたいが、シミュレーションするのは制約上厳しい。そこで、$a_0$ がぶつからずに進んだ$T$秒後の位置を $q_x$ とおき、$ q_x $ に存在するべき蟻はどこから来たか、を考える。
以下の図を見ると、$a_0$ が右向きなら、蟻とぶつかるたびに右に1つ、左向きなら左に1つずつズレていくことが分かる。
また、$m$ 秒間で蟻は元の位置に戻る*3 ので、$m$ 秒間と、$T \bmod m$ 秒間でぶつかる回数をそれぞれ $A$, $B$ とおけば、$T$ 秒間でぶつかる回数は $ A \lfloor T / m \rfloor + B$ で与えられる。
特殊ケースの処理
全ての蟻の向きが一方向だけなら、ぶつかる回数は 0 なので $q_x = (a_0 + T) \bmod m$（右向きの場合）である。
m秒間にぶつかる数
以降、$a_0$ は右に進む蟻という体で説明する*4。また、左に進む蟻の集合を $ L $ とおく。$a_0$ が一周する間に、左向きの蟻 $a_l \in L $ と何回ぶつかるかを考える。
すると、ちょうど 2回ぶつかると分かる。この回数はどの左向きの蟻についても同じなので、$A = 2|L| $。
T mod m 秒間にぶつかる数
これは、各左向きの蟻について距離が 1 秒ごとに 2 ずつ減ると考えると、
- $ |a_0 - a_l| \lt 2 T \bmod m $ なら回数 + 1
- $ |a_0 - a_l + m| \lt 2 T \bmod m $ なら回数 + 1
を計上すればよい。ただし、$T \bmod m$ 秒ちょうどの扱い（上の不等式にイコールを含めるか否か）に注意。仮に含めないとすると、蟻の最終位置 $q$ をソートするときに、座標が同じ場合 右向き を 左向きの前にもってくる ようにする。
解答コード
Educational Codeforces Round #10-F : Ants on a Circle
ちなみに
全く同じ問題（名前も同じ）が AtCoder でも出題された。 このとき出ておけばコピペで常勝だったのに
