Asa's Website

D - Zero Remainder Array

cpcodeforcesdiv3math

最終更新日

Table of Contents

Loading...

問題

https://codeforces.com/contest/1374/problem/D

問題文

長さ nn の数列 aa が与えられる。以下の操作を何回か行って、すべての ii について aimodk=0a_i \bmod k = 0 にしたい。最小の回数は?

x=0x = 0 で初期化する。
操作は以下のどちらか。

  • ii を 1 つ選ぶ。aia_iai+xa_i + x にして、 xxx+1x + 1 する。ただし、同じ ii を 2 回以上選ぶことはできない。
  • xxx+1x + 1 する。

制約

サンプル

5 4 3 1 2 1 3 10 6 8 7 1 8 3 7 5 10 8 9 5 10 20 100 50 20 100500 10 25 24 24 24 24 24 24 24 24 24 24 8 8 1 2 3 4 5 6 7 8
6 18 0 227 8

考察

まず、ii それぞれについて (kai)modk(k - a_i) \bmod k を求めておき、値ごとに ii の個数を数えておく。
つまり、「 cntj=((kai)modk=j)\mathrm{cnt}_j = \left( (k - a_i) \bmod k = j \right) となる ii の個数」を計算しておく。

maxcntj\max \mathrm{cnt}_jmm とすると、mm 回ぐるぐるする必要がある。そのために必要な操作回数は m×km \times k
ただ、最後の mm 周目は最後まで回さなくていいので、jj 回増やしておいて、 ai:=ai+xa_i := a_i + x すればいい。

よって、必要回数は m(k1)+j+1=mk(kj)+1m (k - 1) + j + 1 = m k - (k - j) + 1

コード

https://codeforces.com/contest/1374/submission/126809140

void solve() { ll n, k; cin >> n >> k; map<ll, ll> rem; ll maxim = 0, maximI = 0; rep(i, n) { ll a; cin >> a; ll remain = (k - (a % k)) % k; rem[remain]++; if (maxim <= rem[remain] && remain != 0) { if (maxim == rem[remain]) { maximI = max(maximI, remain); } else { maximI = remain; } maxim = rem[remain]; } } if (rem[0] == n) { cout << 0 << endl; return; } ll ans = (maxim * k) - (k - maximI) + 1; cout << ans << endl; return; }