はまやんはまやんはまやん

hamayanhamayan's blog

Russian Dolls [CSAcademy #71 D]

https://csacademy.com/contest/round-71/task/russian-dolls/

N個の人形がある。
i番目の人形のサイズはA[i]である。
サイズが大きい人形は小さい人形を入れることができる。
同じサイズで他の人形に入っているものと入っていないものが無いようにしたい。
もしそれが不可能なら、1つの人形を選んで、それを消してサイズが1小さい人形を2つ追加するという操作ができる。
条件を満たすには最小何回の操作が必要か

解法

まずは条件を見直して考えてみよう。
条件を見直すと「最大サイズの人形の個数がどのサイズの人形の個数以上である」ことが満たされればいい。
なので、操作では2種類の目的で分かれる。
1. 最大サイズの人形を全てサイズを小さくすることでサイズ毎の個数の上限を引き上げる
2. 最大サイズの人形の個数以下にするために最大サイズ以外を操作する
 
最大サイズの上限を引き上げることを全探索することを考える。
最大サイズの上限を引き上げる回数は実は20回ぐらいで大丈夫。
これは操作を行う度に個数が2倍2倍となるので、20回ぐらいで10^5を越える。
そのため、全探索するが上限は20回くらいである。
これでAの上限を変えながら、部分問題を解こう。
 
「solve := 最大サイズ以外を操作して、最大サイズの人形個数以下にするための最小回数」を解いていこう。
数が大きい順から貪欲に小さくしていくシミュレーションをする。
最大サイズの人形の個数をcntとすると、cntよりも個数が多くなったら操作をする。
差をdとする。
もしcnt≦dであれば、操作をしたあともcntとの差がd以上になってしまうので、無限に小さくしてしまう。
なので、この場合は不可能ということでinfを返す。
そうでないなら、小さくしていこう。
 
実装が大変だが、きちんと実装するとAC

int N;
map<int, ll> A;
//---------------------------------------------------------------------------------------------------
ll solve(map<int, ll> v) {
    auto ite = v.end();
    ite--;

    int ma = ite->first;
    ll cnt = ite->second;

    vector<pair<int, ll>> w;
    fore(p, v) if (p.first != ma) w.push_back(p);
    sort(all(w), greater<pair<int, ll>>());

    ll res = 0;
    int n = w.size();
    rep(i, 0, n) {
        if (w[i].second <= cnt) continue;

        ll x = w[i].first;
        ll c = w[i].second;

        while (cnt < c) {
            ll d = c - cnt;
            if (cnt <= d) return infl;
            res += d;

            if (i + 1 < n) {
                if (x - 1 == w[i + 1].first) {
                    w[i + 1].second += d * 2;
                    break;
                } else {
                    x--;
                    c = d * 2;
                }
            } else {
                if (x - 1 == 0) return infl;
                x--;
                c = d * 2;
            }
        }
    }

    return res;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) {
        int x; cin >> x;
        A[x]++;
    }

    ll ans = infl, sm = 0;
    rep(i, 0, 25) {
        ll a = solve(A) + sm;
        chmin(ans, a);

        if (A.size() == 1) break;

        auto ite = A.end();
        ite--;

        int x = ite->first;
        ll y = ite->second;
        A.erase(ite);

        sm += y;
        A[x - 1] += y * 2;
    }
    cout << ans << endl;
}