分裂アメーバと聞くととあるゲームの3面を思い出す。
http://yukicoder.me/problems/6
問題
1次元の数直線上にN匹のアメーバがおり、初期状態では座標X[i]にいる。
1秒ごとに、各アメーバは元いた位置に加え、+Dの位置と-Dの位置にも分裂する。
同じ位置に複数のアメーバが来た場合、それらは合体して1匹になる。
T秒後のアメーバ数を答えよ。
解法
各アメーバは、T秒後には[X[i]-T*D, X[i]+T*D]の閉区間にD毎の間隔で存在することになる。
よってアメーバをX[i] mod Dの値でグループ分け、同一グループのアメーバ同士で区間が重なる場合連結していけば良い。
ll N,D,T; ll X[150]; map<ll,vector<pair<ll,ll> > > M; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>D>>T; FOR(i,N) { cin>>X[i]; M[(D+X[i]%D)%D].push_back(make_pair(X[i]-D*T,X[i]+D*T)); } ll ret=0; ITR(it,M) { vector<pair<ll,ll> > V=it->second; ll mi=-1LL<<60,ma=-(1LL<<60)-D; sort(V.begin(),V.end()); FOR(i,V.size()) { if(V[i].first>ma) { ret+=(ma-mi)/D+1; mi=V[i].first; } ma=V[i].second; } ret+=(ma-mi)/D+1; } cout<<ret<<endl; }
まとめ
アメーバが分裂時にすれ違っても、そこは合体しないんだね。