問題
https://codeforces.com/contest/1374/problem/D (新しいタブで開く)
問題文
長さ の数列 が与えられる。以下の操作を何回か行って、すべての について にしたい。最小の回数は?
で初期化する。
操作は以下のどちらか。
- を 1 つ選ぶ。 を にして、 を する。ただし、同じ を 2 回以上選ぶことはできない。
- を する。
制約
- の総和は を超えない。
サンプル
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
考察
まず、 それぞれについて を求めておき、値ごとに の個数を数えておく。
つまり、「 となる の個数」を計算しておく。
を とすると、 回ぐるぐるする必要がある。そのために必要な操作回数は 。
ただ、最後の 周目は最後まで回さなくていいので、 回増やしておいて、 すればいい。
よって、必要回数は
コード
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; }