Codeforces Round #653 D - Zero Remainder Array

問題概要

要素の配列 と整数 が与えられる。
とある変数 (初期値0)を用いて1回のうちに以下の操作のどちらかを行う。

• の値を1増やす

• の値を のうちのいずれかの要素 に足して、 の値を 増やす

のすべての要素を の倍数にするためには何回の操作が必要か。 codeforces.com

解説

全てを の倍数にするためには全ての について 以上の の倍数 を足せばいいので、各 について を足せばいいことになります。

を 増やす間に の ~ をそれぞれ つずつ使うことが出来ます。

ただしこの の値が被ることがあるので、その場合はまた 増やす必要があります。

一番被りが多い値のものについて考えれば、その間にそれ以外の値は の倍数にすることが出来るので、この一番被りが多い値のものについてのみ考えればいいです。

被りの回数 増やすので、(被りの回数) を求めればいいのですが、最後の 回は必ずしも 増やすのではなく、この被りの一番多い値自体まで増やせばいいので、(被りの回数 - 1)+(被りの一番多いものの値)となります。

そして、 は最初は なので初めに 増やすことをふまえて先程の値に すればいいことになります。

実装

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int t;
    cin >> t;
    while(t--){
        long long n, k;
        cin >> n >> k;
        map<int, int> m;
        for(int i = 0; i < n; i++){
            int a;
            cin >> a;
            //kの倍数になるまでの足すべき値がそれぞれ何回出てくるかを数える
            //引き算なのでmodのとり方に注意
            if(a % k) m[((k - a) % k + k) % k]++;
        }
        //最頻値
        long long large = 0;
        //最頻値が何なのか
        long long tmp = 0;
        for(auto&& e : m){
            //それが最頻であったとき
            if(large <= e.second){
                large = e.second;
                //その値をメモする
                tmp = e.first;
            }
        }
        //最初から全てがkの倍数だった時は0
        if((int)m.size() == 0) cout << 0 << endl;
        //k * (最頻値 - 1) + 最頻値の足すべき値 + 1
        else cout << k * (large - 1) + tmp + 1 << endl;
    }
    return 0;
}

以上でこの問題を解くことが出来ました