SRM609 Div1 Medium "PackingBallsDiv1"

問題

TopCoder Statistics - Problem Statement

訳

K色のボールがある。色は0～K-1と番号が振られ、色iのボールの数はX[i]である。このボールをできる限り少ない袋に分けたい。袋には1～Kまでのボールを入れることができる。加えて全ての同じ色のノーマルセットか、全て違う色のバラエティセットにしなければならない。

あなたは整数 K, A, B, C, Dが与えられる。それぞれの色のボールの数Xは下記のようになる。

X[0] = A
for i = 1 to K-1:
    X[i] = (X[i-1] * B + C) % D + 1

ボールを上記のルールに従って袋に分けたときの、できる限り少ない袋の数を返せ。

制約

1 <= K <= 10^6
1 <= A, B, C, D <= 10^9

解法

まずK個のボールを含むノーマルセットをバンバン作る
↓
残りのボールでノーマルセットとバラエティセットをいくつずつ使うかで総当りする。

でいいらしい。なんで？

ソースコード

long long X[100050];

class PackingBallsDiv1 {

    public:

    int minPacks(int K, int A, int B, int C, int D) {

        // 入力
        X[0] = A;
        for (int i = 1; i < K; i++){
            X[i] = (X[i - 1] * B + C) % D + 1;
        }

        int res = 0;

        // ノーマルセット
        for (int i = 0; i < K; i++){
            res += X[i] / K;
            X[i] = X[i] % K;
        }

        // ノーマルセット＆バラエティセット
        sort(X, X + K);
        int p = 0;
        int cost = K;
        for (int h = 0; h < K; h++){
            while (X[p] <= h && p < K) p++;
            cost = min(cost, h + K - p);
        }

        return res + cost;
    }
};