Yukicoder033 アメーバがたくさん

問題概要

$N$匹のアメーバが1直線上にいます。 各アメーバには初期座標が与えられます。 $x$にいるアメーバは１秒後に$x-D,x,x+D$へ分裂します。 また、アメーバは同じ座標に2匹以上いると、 合体して1匹になります。 最初に$N$匹いたアメーバが$T$秒後には 何匹になっているか答えなさい。

$N\leqq10^2$、$D,T\leqq10^9$、$-10^9\leqq X[i]\leqq10^9$

yukicoder033

解法

重複する区間を最後にmergeする作業は区間スケジューリングでおなじみ。
重複しうるグループは$x\%D$の同値類のみ。
グループ分けした後にmergeすればよい。

計算量:$O(N^2logD)$

ソース

    #include <bits/stdc++.h>
    using namespace std;
    
    using VS = vector<string>;    using LL = long long;
    using VL = vector<LL>;        using VVL = vector<VL>;
    #define ALL(a)  begin((a)),end((a))
    #define SZ(a) int((a).size())
    #define SORT(c) sort(ALL((c)))
    #define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
    
    
    LL N, D, T;
    LL ans = 0LL;
    
    int main() {
        cin.tie(0);
        ios_base::sync_with_stdio(false);
    
        cin >> N >> D >> T;
        map<int, VL>Map;
        FOR(i, 0, N) {
            LL x; cin >> x;
            Map[(x%D + D) % D].push_back(x);
        }
        ans = 0;
        for (auto it = Map.begin(); it != Map.end(); it++) {
            VL a = it->second;
            SORT(a);
            LL L = a[0] - D * T;
            LL R = a[0] + D * T;
            FOR(i, 1, SZ(a)) {
                if (R >= a[i] - D * T) {
                    R = a[i] + D * T;
                }
                else {
                    ans += (R - L) / D + 1;
    
                    L = a[i] - D * T;
                    R = a[i] + D * T;
                }
    
            }
            // 末尾のやつ
            ans += (R - L) / D + 1;
        }
    
        cout << ans << "\n";
    
        return 0;
    }