Educational Codeforces Round 18 E: Colored Balls

問題概要

原文 → Problem - E - Codeforces

$N$ 色のボールがあり、 $i$ 番目の色で塗られたボールは $a_i$ 個ある。

これらのボールを以下の条件を全て満たすように箱に入れる。

それぞれの箱について、箱の中にあるボールの色は $1$ 種類のみ
空箱が存在しない
箱に入っているボールの個数の最大値と最小値の差は高々 $1$

必要な箱の個数の最小値を求めよ。

解説

$1$ 色目のボールを箱に入れることを考える。積を考えると、「箱の個数」または「箱に入れるボールの個数」のいずれかは $\sqrt{a_1}$ 以下であることが分かる。なのでそれぞれについて問題を解けばよい。

箱の個数が定まっているときに、それぞれの箱に入れるボールの個数がどうなるべきかは割り算をするとわかる。(剰余が $0$ のときに注意)

あとは「箱に入れるボールの個数が $x$ 個または $x+1$ であるときに、条件を満たす入れ方が可能か？また可能な時の箱の数の最小値がいくらか？」を解ければ良いことになる。

実は、各 $i$ について最適な箱の数は $\lceil \frac{ a_i }{ x+1 } \rceil$ であり、入れ方が可能かどうかの判定は $x \lceil \frac{ a_i }{ x+1 } \rceil \leq a_i$ を満たすかどうかで可能である。

上の条件を満たすと仮定すると $x \lceil \frac{ a_i }{ x+1 } \rceil \leq a_i \leq (x+1) \lceil \frac{ a_i }{ x+1 } \rceil$ が成立するが、これは「全ての箱に $x$ 個入れたと仮定した時の個数」と「全ての箱に $x+1$ 個入れたと仮定した時の個数」で $a_i$ を挟んでいることに相当している。

ソースコード

int main() {
    int N; scanf("%d", &N);
    vector<int> A(N);
    for(int i=0; i<N; i++) scanf("%d", &A[i]);

    ll ans = INF;
    {
        // 箱の個数について
        for(int x=1; x*x<=A[0]; x++) {
            int d = A[0] / x, m = A[0] % x;
            for(int k=d; k>=d-(m==0); k--) {
                int mi = k, ma = k+1;
                ll sum = 0;
                for(int i=0; i<N; i++) {
                    ll b = (A[i] + ma - 1) / ma;
                    if(mi * b <= A[i]) sum += b;
                    else sum = INF;
                }
                ans = min(ans, sum);
            }
        }
    }

    {
        // 箱に入れるボールの個数について (x か x+1)
        for(int x=1; x*x<=A[0]; x++) {
            int mi = x, ma = x+1;
            ll sum = 0;
            for(int i=0; i<N; i++) {
                ll b = (A[i] + ma - 1) / ma;
                if(mi * b <= A[i]) sum += b;
                else sum = INF;
            }
            ans = min(ans, sum);
        }
    }
    cout << ans << endl;
    return 0;
}