Submission #68573981

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, n) for (int i = n-1; i >=0; i--)
#define repsg(i, s, g) for (int i = s; i < (int)(g); i++)
using ll = long long;
using P = pair<int,int>;
using Graph = vector<vector<int>>;
using mint = modint1000000007;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  int N, M, L; cin >> N >> M >> L;
  vector<int> A(N); rep(i, N) cin >> A[i];

  // 入る値と抜ける値の余り（Mod M)が等しくないといけない
  // r0 : Ai ≡ Ai+L ≡ Ai+2L ..
  // r1 : Ai+1 ≡ Ai+1+L ≡ Ai+1+2L ..
  // ..

  // 位置を L で割った余りごとのクラス r に分割
  // そのクラス内の「値 ≡ d (mod M)」の個数 freq[r][d] を数える
  vector<vector<int>> freq(L, vector<int>(M, 0));
  repsg(k, 1, N+1){
    int r = (k-1)%L;
    int d = A[k-1]%M;
    freq[r][d]++;
  }

  // dp[m] : これまで処理したクラスの目標値和 ≡ m (mod M) にする最小増加回数
  ll INF = (1LL<<62);
  vector<ll> dp(M, INF);
  dp[0] = 0;

  //// 各クラス r について最適な「そろえ先 x (mod M)」を選ぶ ////
  rep(r, L){
    int n = 0;
    rep(d, M) n += freq[r][d];
    if (n == 0) continue;

    // sum = Σ d * freq[r][d]
    ll sum = 0;
    rep(d, M) sum += d * freq[r][d];

    // cle[x] = Σ {d=0..x} freq[r][d]（累積個数）
    vector<int> cle(M, 0);
    int s = 0;
    rep(d, M) {
      s += freq[r][d];
      cle[d] = s;
    }

    // クラス r の全要素を x(mod M) へ増やして揃えるためのコスト(全体) 
    // H[x] = cost_r(x) = Σ d freq[d] * ((x-d) mod M) 

    // 全要素数 n 
    // sum = Σ d * freq[r][d]

    // H[x] = Σ freq[d]*(x-d) (d≤x) + Σ freq[d]*(x-d+M) (d>x)
    // H[x] = n*x - sum + M*(n-cle[x])
    vector<ll> H(M, 0);
    rep(x, M) H[x] = 1LL*n*x - sum + 1LL*M*(n-cle[x]);
    
    //// クラスごとのコスト H[x] を組み合わせて、全体の剰余制約を満たすように選んでいく
    // dp 遷移 / dp[0]が「合計 ≡ 0 (mod M)」になるように揃えたときの最小コスト
    // これまでの和 ≡ m に、次クラスの目標 x を足して 新しい和 (m+x) mod M のコストを更新
    vector<ll> ndp(M, INF);
    rep(m, M) if (dp[m] < INF) {
      rep(x, M) {
        int idx = (m+x) % M;
        ll cand = dp[m] + H[x];
        if (cand < ndp[idx]) ndp[idx] = cand;
      }
    }
    dp.swap(ndp);
  }

  ll ans = dp[0];
  cout << ans << endl;

  return 0;
}

Submission Info

Judge Result