問題解決の宝石箱

競技プログラミング/数学ネタ置き場

Educational Codeforces Round #10-F : Ants on a Circle

問題

Educational Codeforces Round #10-F : Ants on a Circle

【Educational Codeforces Round #10-F : Ants on a Circle】
\(N\) 匹の蟻が長さ \(M\) cm の円周上に乗っている。
蟻は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} $

f:id:hama_DU:20170107142435p:plain

蟻の最終位置は簡単にわかる

蟻を区別しない場合、ぶつかるときの処理を無視して単に通り抜けるだけ、としてよい。なので、各蟻が独立して与えられた向きに $T$ 秒間動き続けると考えると、蟻の最終位置が得られる。これをソートした列を $q$ とおいてあとで参照する。

問題は、これらがスタート地点でそれぞれどの蟻だったか、である。

蟻の順番は変化しない

蟻の初期位置をソート*1*2した列を $p$ とおく。また、ソート済での順番で数えて、左から $x$ 番目の蟻を $a_x$ とおく。

これが $T$ 秒後どこに行くか、を以下の図を描いて考えよう。

f:id:hama_DU:20170119222914p:plain

すると、例えば $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つずつズレていくことが分かる。

f:id:hama_DU:20170119224242p:plain

また、$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 $ と何回ぶつかるかを考える。

f:id:hama_DU:20170501211429p:plain

すると、ちょうど 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 でも出題された。 このとき出ておけばコピペで常勝だったのに

*1:円周上の位置でソートとは?という気持ちになるが、ここでは円上の 0cmの位置にハサミを入れ、伸ばした直線上の位置でのソートである

*2:問題では初期位置は 1以上m以下の整数で与えられるが、処理を簡単にするため m を 0 で読み替える。答えでは 0 の代わりに m を出力すれば良い。

*3:ただしそこにいるのは同じ蟻とは限らない

*4:a_0 が左向きの場合は、右向きの蟻 a_r を適当に探してくること。また、全体の位置を a_r だけ左にズラし、a_r の初期位置を 0 と考えると考察が楽かも。