AtCoder Grand Contest 013 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; } }
所感
精進ですでにこの問題を解いている水色・青が思ったより多くてびっくりした.これそんなに簡単な問題じゃないよね……?