yukicoder : No.33 アメーバがたくさん

分裂アメーバと聞くととあるゲームの３面を思い出す。
http://yukicoder.me/problems/6

問題

１次元の数直線上にN匹のアメーバがおり、初期状態では座標X[i]にいる。
１秒ごとに、各アメーバは元いた位置に加え、+Dの位置と-Dの位置にも分裂する。
同じ位置に複数のアメーバが来た場合、それらは合体して１匹になる。

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;
	
}

まとめ

アメーバが分裂時にすれ違っても、そこは合体しないんだね。