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