けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder AGC 013 C - Ants on a Circle (700 点)

蟻さんぐるぐるなのん

問題へのリンク

問題概要 (AGC 013 C)

長さ  L の円周上を  N 匹の蟻が動く。どの蟻も 1 秒間に 1 だけ動く。互いに反対方向に動いている 2 匹の蟻がぶつかったら、互いに向きを反転させて動く。

 N 匹の蟻は最初  X_{1}, X_{2}, \dots, X_{N} の地点にいた。どの蟻が最初にどちら周りに向かっているかも指定されている。

 T 秒後の各蟻の位置を求めよ。

制約

  •  1 \le N \le 10^{5}

考えたこと

蟻本のオマージュ!!!!!
でも、そういう風に考える問題と見せかけた罠かもしれないし、罠にはハマらんぞい。一応

  • 蟻 i を追跡する
  • 最初蟻 i だったやつがどの蟻とぶつかって入れ替わっていくかを追跡する (「Ants」の視点)

の 2 つの方向性がありうることを常に念頭に置いて考えてみる。一応「Ants」と言えば、2 匹の蟻がぶつかったとき、向きを入れ替えるのではなく互いにただすれ違っただけだが、互いに番号が入れ替わるものと思うことができる。番号 1 の蟻が番号 3 の蟻とぶつかったら、そのまま直進するわけだが、ぶつかった後は番号 3 の蟻として生きて行くことになる。

で、「Ants」の視点に立つと、 T 秒後に  N 匹の蟻がいる場所の集合は特定できる (ただしどの蟻がそこにいるかはわからない) 的な状態になる。

ここで、冷静にありのままの蟻の動きを見てみる。そうすると、各蟻は隣の蟻に阻まれて、いつまでたっても蟻 3 は蟻 2 と蟻 4 との間に挟まれていることがわかる。つまり、 N 匹の蟻の配置状態は不変である。よって、最後に原点から正の方向に一番近い蟻が誰なのかがわかれば OK である。

蟻の順序は不変であることから、原点にカウンターを用意することで解決する。原点を

  • 負の方向から正の方向へと通過: カウンターデクリメント
  • 正の方向から負の方向へと通過: カウンターインクリメント

という風にすればよい。計算量は  O(N\log{N})

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N; long long L, T;
vector<long long> X;
vector<int> W;

int main() {
    cin >> N >> L >> T;
    X.resize(N); W.resize(N); for (int i = 0; i < N; ++i) cin >> X[i] >> W[i];
    vector<long long> tmp(N);
    for (int i = 0; i < N; ++i) {
        if (W[i] == 1) tmp[i] = (X[i] + T) % L;
        else tmp[i] = ((X[i] - T) % L + L) % L;
    }
    sort(tmp.begin(), tmp.end());
    long long count = 0;
    for (int i = 0; i < N; ++i) {
        if (W[i] == 1) count -= (T - (L - X[i]) + L) / L;
        else count += (T - (X[i] + 1) + L) / L;
    }
    count = (count % N + N) % N;
    vector<long long> res(N);
    for (int i = 0; i < N; ++i) res[(i+count)%N] = tmp[i];
    for (int i = 0; i < N; ++i) cout << res[i] << endl;
}