AtCoder Grand Contest 013 C - Ants on a Circle - アルゴリズマーの備忘録

1番ゼッケンの蟻の動きを追い続ければ絶対AC出来ると思っていましたが、無理でした。

問題概要

N匹の蟻がLの長さの円周上にいる。彼らは1秒に1だけ進み、他の蟻と衝突するとその場で進行方向を逆にする。それぞれの座標と移動方向が与えられるので、それぞれT秒後にどこにいるか求めよ。

解説

時計回りに蟻の番号を付けると、終了時の蟻の位置も時計回りになっています。なので、頑張って1番蟻の位置を求めたら終わり。

と思ってました。無限にWAしました。原因は分かりません。多分直感で「L秒周期になっている」という強い仮定をしていたので、それが正しくないと死んでます。

仕方なく、解説の方法に則ります。
1匹の蟻の動きを追うのではなく、衝突→通過に変換したとき、移動後の蟻の番号はいくつに変更されているかということを考えます。時計回りに回っているなら、衝突時にその番号は+1されるので、T秒間に他の蟻と何回衝突するか求めればその蟻の番号が分かります。具体的には、蟻の間の距離をdxとすると、
t≧(dx + (衝突回数-1)×L)/2（t=dx/2でも1回衝突するので注意！）
衝突回数≦(2t-dx+l)/l
という風になるので、これを利用します。

ある蟻の最終的な番号が分かったら、全部の蟻の最終的な位置を算出してソート、何番目かを求めておくと、後はそれっぽく当てはめるだけです。

https://beta.atcoder.jp/contests/agc013/submissions/2304927

int main() {
    int n; ll l, t;    cin >> n >> l >> t;
    l <<= 1; t <<= 1;
    vector<ll> ccw, cw;
    vector<pair<ll, int>> dat(n);
    rep(i, n) {
        ll x, w;    cin >> x >> w;  x <<= 1;
        if (w == 1)  cw.push_back(x);
        else  ccw.push_back(x);
        dat[i] = mp(x, w);
    }
    int num = 0;
    if (dat[0].second == 1) {
        rep(i, ccw.size()) {
            // t >= (dist+collision*l)/2
            // collision-1 < (2*t - dist)/l <= collision
            int dist = ccw[i] - dat[0].first;
            int collision = (2 * t - dist + l) / l;
            num = (num + collision) % n;
        }
    }
    else {
        rep(i, cw.size()) {
            int dist = l - (cw[i] - dat[0].first);
            int collision = (2 * t - dist + l) / l;
            num = (((num - collision) % n) + n) % n;
        }
    }
    vector<ll> after(n);
    rep(i, n)   after[i] = (((dat[i].first + (dat[i].second == 1 ? 1 : -1)*t) % l) + l) % l;
    ll afterpos = after[0];
    sort(all(after));
    int pos = 0;
    if (dat[0].second == 1) {
        rrep(i, n) {
            if (after[i] == afterpos) {
                pos = i;
                break;
            }
        }
    }
    else {
        rep(i, n) {
            if (after[i] == afterpos) {
                pos = i;
                break;
            }
        }
    }
    vector<ll> ret(n);
    rep(i, n) {
        ret[num] = after[pos];
        num = (num + 1) % n;
        pos = (pos + 1) % n;
    }
    rep(i, n)   cout << (ret[i] >> 1) << endl;
    return 0;
}

感想

つらい。本当につらかった。ところで、このwriteupを探していたら、AGCより前に全く同じ名前、同じ内容っぽい問題がこどふぉで出ていたらしいのですが…