yukicoder - No.33 アメーバがたくさん
アメーバの分裂。 分裂が衝突しちゃうものを考慮しないといけない。 こういう問題、コンテストとかで出されたらミスしまくりそう。
signed main() { ll N,D,T; cin>>N>>D>>T; vector<ll> X(N); for(int i=0;i<N;i++) cin>>X[i]; sort(X.begin(), X.end()); // 負の値があれば全て0以上に底上げしておく if (X[0] < 0) { ll x0 = -X[0]; for(int i=0;i<N;i++) X[i] += x0; } ll ret = 0; ret += N; for(int i=0;i<N;i++){ // 左をチェック bool found = false; for(int j=i-1;j>=0;j--) { ll diff = X[i] - X[j]; if (diff % D == 0) { // 左方向への分裂は、右方向へ分裂してくるものとの衝突を考慮する ll mx_count = diff / D - 1; if (mx_count > T){ ret += min(T, mx_count - T); } found = true; break; } } if (!found) ret += T; found = false; // 右をチェック for(int j=i + 1;j < N;j++) { ll diff = X[j] - X[i]; if (diff % D == 0) { // 右方向への分裂は、初期位置にいるものとの衝突のみ考慮する ll mx_count = diff / D - 1; ret += min(T, mx_count); found = true; break; } } if (!found) ret += T; } cout<<ret<<endl; return 0; }