phyllo’s algorithm note

レッドコーダーへの道のりは遠い。休んでる場合じゃない!

AGC013 C. Ants on a Circle

問題

周の長さがLの円上にN匹の蟻がいる。
それぞれの蟻は番号がついていて、座標X_iと向きW_iが与えられ、毎秒1単位距離の速度で動く。
各蟻は衝突するとそれぞれ進む向きを変える。
T秒後にそれぞれの蟻がいる位置を求めよ。

制約

1 <= N <= 10^5
1 <= L,T <= 10^9
0 <= X_1 < X_2 < ... < X_N <= L-1
W_i = {1,2}

解説

いくつか気づかないといけないことがある。

  • 1. 番号を無視したときのT秒後の蟻の位置

番号を無視したT秒後の蟻の位置座標の集合は、蟻本で紹介されている通り、素通りするように考えると求められる。
各蟻について、求めた座標をソートすると、番号はわからないが、答えの座標になっている。

  • 2. 衝突で跳ね返る場合、T秒後の番号の並びは1,2,3,...をずらしたものとなる

衝突で蟻は跳ね返るので番号の大小関係は変わらない。
なので、ある蟻の番号と位置がわかればそこから他の蟻の番号が一意に決まる。

  • 3. 最初、番号1だった蟻のT秒後の座標と番号は衝突回数から求められる

最初番号1だった蟻が時計回りだった場合を考える。
座標は1の方法で求められる。
番号については、衝突がx回だった場合、+xになる。

衝突回数は、進行方向が異なる蟻に対して、
1回目は、(2匹の蟻の距離の半分)秒
2回目は、(2匹の蟻の距離の半分+L*1/2)秒
3回目は、(2匹の蟻の距離の半分+L*2/2)秒
...
となっているので、以下のような感じで衝突回数がO(1)で求められるので、すべての進行方向が異なる蟻について求めるとO(N)。

ll calc_count(ll x, ll y, ll L, ll T){
  if(T*2 < abs(x-y)) return 0;
  ll remain = T*2 - abs(x-y);
  return 1+remain/L;
}

反時計回りだった場合は、衝突回数がx回だった場合、-xになる。
2つの蟻の距離も「最初の蟻の座標+L」との距離を求めればよい。

1で求めた座標の中からこの座標を持つ座標を見つければ、それが求めた番号であることがわかる。
なので、2の事実によって求められる。

  • 4. 同じ座標になる場合

3で求めてたT秒後の座標が同じ座標になる場合がある。(入力例2)
ただし、同じ座標になるのは、最初の座標がすべて異なり、同じ速度で動いているため2匹しかありえない。
このような場合、衝突直後なので、進行方向に対して後ろ側になる。


これらを事実を合わせてれば答えが得られる。
計算量は、ソートする部分が一番重く、O(NlogN)。

反省

  • 負の数のmoduloには気を付ける
    • 型にも気を付ける
int a = -5;
int b1 = 3;
unsigned int b2 = 3;

cout << (a%b1) << endl; //-2
cout << (a%b2) << endl; //2