割とすんなり解けたけど、本番で出てたらEasyのタイムロスで間に合わなかっただろうな。
https://community.topcoder.com/stat?c=problem_statement&pm=13890
問題
遊園地で左右に無限に続く1本道の上でN人の子供がカートに乗っている。
初期状態として、各子供のカートの位置pos[i]及び最初の向きdir[i]が与えられる。
各カートは、時間1あたり1のペースで向いている向きに移動する。
ただし途中他のカートとぶつかると、両カートは向きを反転する。
個々でQ個のクエリが与えられる。
各クエリは子供番号kid[j]と時刻time[j]からなる。
クエリで指定された子供kid[j]番のカートが、時刻time[j]にどの位置にいるかを求め、その座標の絶対値の総和を求めよ。
解法
まず各子供の初期位置をソートしよう。
この問題ではカートに乗った子供はすれ違えないので、初期状態で座標の小さい順でk番目にいる子供は、時間が経ってもk番目の位置にいる。
よって、各クエリに対しては、時刻time[j]の時点で座標の小さい順からk番目のカートを求めればよい。
カートは互いにぶつかるので、時間が経った後の場所は一見求めるが難しい…が、ここで蟻本の最初にある問題Antの考えが利用できる。
カートがぶつかると互いに向きを反転するとあるが、(乗っている子供を無視して)その後の2台のカートの位置を考えると、カートがすれ違うのと変わらない。
初期状態で左向きで走る車iは、(ぶつからずすれ違うと考えると)時刻time[j]にはpos[j]-iにいる。
また初期状態で右向きで走る車iは、時刻time[j]にはpos[j]+iにいる。
よって、「時刻time[j]の時点で左側にk台のカートがいるような最小の座標p」を二分探索で求めればよい。
座標pが決まっていると、左向きで走る車の座標の昇順配列と、左向きで走る車の座標の昇順配列をそれぞれlower_boundで二分探索すればpの左側にいるカートの台数が求められる。
ll M=1000000007; ll pos[202020]; int dir[202020]; pair<ll,int> P[202020]; set<int> S; int order[202020]; vector<ll> L,R; class FindingKids { public: long long getSum(int n, int q, int A, int B, int C) { int i; S.clear(); L.clear(); R.clear(); FOR(i,n) { A=(1LL*A*B+C)%M; int p=A%(M-n+i+1); if(S.count(p)) p=M-n+i; pos[i]=p; S.insert(p); P[i]={p,i}; if(p%2==0) R.push_back(p); else L.push_back(p); } sort(P,P+n); sort(L.begin(),L.end()); sort(R.begin(),R.end()); FOR(i,n) order[P[i].second]=i; ll ret=0; while(q--) { A=(1LL*A*B+C)%M; int id = order[A%n]; A=(1LL*A*B+C)%M; int tim=A; ll pos=1LL<<32; for(i=33;i>=0;i--) { int a=lower_bound(L.begin(),L.end(),pos-(1LL<<i)+tim+1)-L.begin(); int b=lower_bound(R.begin(),R.end(),pos-(1LL<<i)-tim+1)-R.begin(); if(a+b>=id+1) pos-=(1LL<<i); } ret += abs(pos); } return ret; } }
まとめ
左向きで走る車と、右向きで走る車を別々に考えるのがコツ。
