問題
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;
}