問題解決の宝石箱

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

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} 秒間と、 {mod(T, m)} 秒間でぶつかる回数をそれぞれ  {A},  {B} とおけば、 {T} 秒間でぶつかる回数は  { A \lfloor T / m \rfloor + B} で与えられる。

特殊ケースの処理

全ての蟻の向きが一方向だけなら、ぶつかる回数は 0 なので  {q_x = mod(a_0 + T, m)}(右向きの場合)である。

m秒間にぶつかる数

以降、 {a_0} は右に進む蟻という体で説明する*4。また、左に進む蟻の集合を  { L } とおく。 {a_0} が一周する間に、左向きの蟻  {a_l \in L } と何回ぶつかるかを考える。

f:id:hama_DU:20170501211429p:plain

すると、ちょうど 2回ぶつかると分かる。この回数はどの左向きの蟻についても同じなので、 {A = 2|L| }

mod(T, m)秒間にぶつかる数

これは、各左向きの蟻について距離が 1 秒ごとに 2 ずつ減ると考えると、

  •  { |a_0 - a_l|  \lt 2 mod(T, m) } なら回数 += 1
  •  { |a_0 - a_l + m|  \lt 2 mod(T, m) } なら回数 += 1

を計上すればよい。ただし、 {mod(T, 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 と考えると考察が楽かも。