ABC 419
Table of Contents
https://atcoder.jp/contests/abc419
A. AtCoder Language
https://atcoder.jp/contests/abc419/tasks/abc419_a
B. Get Min
https://atcoder.jp/contests/abc419/tasks/abc419_b
C. King’s Summit
https://atcoder.jp/contests/abc419/tasks/abc419_c
D. Substr Swap
https://atcoder.jp/contests/abc419/tasks/abc419_d
E. Subarray Sum Divisibility
https://atcoder.jp/contests/abc419/tasks/abc419_e
2026/1/22 あまりでまとめる系の問題だということを知った状態で自力 AC
https://kenkoooo.com/atcoder/#/contest/show/bd593eb7-d83c-479e-a99d-d6242eff88ea?activeTab=Problems
index は 0 始まりとする。
長さ $L$ の連続部分列の総和が $M$ の倍数であるから
\begin{align*} A_i + \cdots + A_{i+L-1} &\equiv A_{i+1} + \cdots + A_{i+L} \mod M \\ A_i &\equiv A_{i+L} \mod M \end{align*}
となる。
よって、$L$ 個間隔で同じ $\mod M$ の値に揃える必要がある。
$j \in [0, L)$ を固定して考えたとき $i \equiv j \mod L$ を満たす全ての $A_i$ の集合を $G_j$ とする。
- $G_0 = \{A_0, A_L, A_{2L}, \cdots \}$
- $G_1 = \{A_1, A_{L+1}, A_{2L+1}, \cdots \}$
- $\vdots$
- $G_{L-1} = \{A_{L-1}, A_{2L-1}, A_{3L-1}, \cdots \}$
$G_j$ 中のすべての要素を同じ $r \mod M$ に揃えるときのコストを $C_{j,r}$ とする。
こうすると問題は $C_{0,r_0} + C_{1, r_1} + \cdots + C_{L-1, r_{L-1}}$ を最小化するような $r_0, r_1, \cdots, r_{L-1}$ を求める問題に帰着される。ただし、$\sum_i r_i \equiv 0 \mod M$ である。
$dp(i,r)$ を $i$ まで決定して $\sum_{j=0}^{i} r_j \equiv r \mod M$ であるときの最小コストとすると
\begin{align*} dp(i, r) = \min_{m+x \equiv r \mod M} dp(i-1,x) + C_{i, m} \end{align*}
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll N, M, L;
cin >> N >> M >> L;
vll A(N);
rep(i, N) {
cin >> A[i];
A[i] %= M;
}
if (M <= 1) {
cout << 0 << endl;
return;
}
vvll cost(L, vll(M));
rep(i, L) {
rep(m, M) {
ll sum = 0;
for (ll j = i; j < N; j += L) {
if (A[j] <= m)
sum += m - A[j];
else
sum += M - A[j] + m;
}
cost[i][m] = sum;
}
}
vll dp = cost[0];
rep2(i, 1, L) {
vll dpn(M, INF);
rep(prm, M) {
rep(m, M) {
ll nm = (m + prm) % M;
chmin(dpn[nm], dp[prm] + cost[i][m]);
}
}
swap(dp, dpn);
}
cout << dp[0] << endl;
}
F. All Included
https://atcoder.jp/contests/abc419/tasks/abc419_f