NoiminのNoise

競技プログラミング (多め) とWeb (たまに) ,自然言語処理 (ブログではまだ)。数式の書き方を一気に KaTeX に変えようとして記事を全削除してインポートし直すなどしたので,過去にブックマークされた記事は URL が変わってしまっている可能性があります…….

AtCoder Grand Contest 013 C - Ants on a Circle

C - Ants on a Circle

問題概要

長さL円周上を,N個の点が速さ1でT秒間移動する.それぞれの点は0秒の地点で円周上の座標X[i]におり,W[i]の方向 (1: 時計回り, 2: 反時計回り) に動く.ただし2つの点が衝突したとき,2つの点は速さを変えず反対方向に動き出す (完全弾性衝突) .

解法概要

与えられたN個の点を点0,点1,…,点(N-1)とする.

まず,完全弾性衝突なので,点と点の間の順序関係を気にしなければT秒後の座標の「集合」は簡単に求められる. (ソースコード中の配列y[n]).

それに加えて,点と点の間の順序関係も衝突の前後で変わらないので.どれか1つの点のT秒後の座標がわかればすべての点のT秒後の座標がわかることになる.

ここからは私が考えやすかった考え方になるので,解説の解法とは少々異なる.

点と点の間の順序を求めるには,座標0の点を基準に考えるとよい.N個の点が座標0の点を越えて移動する回数を数えることで,「もっとも小さな座標を持つ点は点0〜点(N-1)のどれか? (ソースコード中の i0) 」を求めることができる.他の点が座標0の点を時計回りに越えるときには i0 の値はその回数だけ減り,反時計回りに越えるときには i0 の値はその回数だけ増える.

i0を求めたら,点(i0+i)%nのT秒後の座標は配列yの中でi番目に小さい値として求められる.i0は負の値になりうるのでi0にする前に正の値に直しておくこと.

ソースコード

#include<iostream>
#include<algorithm>

using namespace std;

typedef long long ll;

int main() {
    ll n,l,t;
    cin >> n >> l >> t;
    ll x[n], y[n];
    int w[n];
    for(int i=0;i<n;i++){
        cin >> x[i] >> w[i];
        if(w[i] == 1){
            y[i] = (x[i] + t) % l;
        }else{
            y[i] = (((x[i] - t) % l) + l) % l;
        }
    }

    ll i0 = 0LL;
    for(int i=0;i<n;i++){
        if(w[i] == 1){
            if(l-x[i] > t) continue;
            i0 -= (t-(l-x[i])+l-1)/l;
        }else{
            if(x[i] > t) continue;
            i0 += (t-x[i]+l-1)/l;
        }
    }

    i0 = (i0 % n) + n;
    ll ans[n];
    sort(y, y+n);
    for(int i=0;i<n;i++){
        ans[(i0+i)%n] = y[i];
    }
    for(int i=0;i<n;i++){
        cout << ans[i] << endl;
    }
}

所感

精進ですでにこの問題を解いている水色・青が思ったより多くてびっくりした.これそんなに簡単な問題じゃないよね……?