No.33

$X_i$ を $D$ で割った余りが異なるアメーバ同士は互いに干渉しない.

したがって, $X_i$ を $D$ で割った余りでグループ分けして, グループごとに計算する.

グループ分けされた $X_i$ は $D$ で割って座標圧縮しておく.

そうすると $X_k$ の位置にいたアメーバは $T$ 秒後に $X_k-T \dots X_k+T$ の範囲に広がる.

$X_i$ ごとにこれを計算し, 重なっている範囲を除けばいい.

このとき, $X_i$ を昇順にソートしておくと, 重なりのチェックは $X_{i-1}$ のアメーバだけを対象にすればいい.