素朴なシミュレーションが通るものの、それを正確に実装するのも結構大変

問題へのリンク

問題概要

$N$ 種類のスライムがいる。 $i$ 種類目のスライムは、サイズが $S_{i}$ であり、 $C_{i}$ 体いる。

一般にサイズが $X$ であるスライムを 2 体合体させて、新たにサイズが $2X$ のスライムを 1 体作ることができる。

合体操作を好きな回数だけ繰り返したあとの、スライムの個体数の最小値を求めよ。

制約

$1 \le N \le 10^{5}$
$1 \le S_{i}, C_{i} \le 10^{9}$

考えたこと

サイズが小さい方からスライムを見ていって、端数を残してがむしゃらに合体を繰り返していく Greedy 法が最適でないかと直感が働く。実際それは正しい。

具体的に証明してみる。スライムのサイズ $X$ に対して $2$ で割れるだけ割った値を $f(X)$ と表すことにする。たとえば $f(120) = 15$ となる (2 で 3 回割れる)。このとき、 $f$ の値が異なるスライムが何かの機会に合体するようなことは決して起こらないので、 $f$ の値が等しいグループのみ考慮すればよい。

よって、 $f(X) = 1$ である場合のみ考えても一般性を失わないので、サイズが $1, 2, 4, 8, 16, \dots$ のスライムのみがいるような状況を考える。ここで、今回はスライムの合体をいくら繰り返したとしても、スライムのサイズの総和が変化しないことに注意しよう。この総和を $Y$ とする。 $Y$ を二進法で表したとき、1 が立っている桁の個数だけのスライムは絶対に必要であることに注意しよう。

たとえば、 $Y = 25$ のとき、これは二進法で表すと $11001$ なので、

$Y = 29 = 2^{4} + 2^{3} + 2^{0}$

と表せることがわかる。つまりサイズが $2^{4}, 2^{3}, 2^{0}$ であるスライムが 1 体ずついる状態が最小だということだ。そしてこの最小値は、冒頭で述べた「サイズが小さい順に端数を残して合体を繰り返していく方法」で達成できるのだ。

まとめると、次のように解ける。

スライムたちを「そのサイズを 2 で割れるだけ割ってできる値 $f$ 」が等しいグループに分ける
それぞれのグループについて、属する各スライムのサイズを $f$ で割ることで、スライムのサイズは $2^{k}$ の形のみとなる
その値の総和を $Y$ としたとき、二進法で表したときに値が 1 である桁数 (C++ なら __builtin_popcount(Y) で求められる) が求める最小値である。この値をグループごとに合算する

なお、 $Y$ の値は $2 \times 10^{18}$ を超えることはない。一般に $2^{0} + 2^{1} + \dots + 2^{K} = 2^{K+1} - 1$ であることから、2 冪を足しても最大の 2 冪の 2 倍程度にしかならないからだ。それを $C_{i}$ の最大値である $10^{9}$ 倍しても、どんなに大きくても $2 \times 10^{18}$ を超えることはない。よって、long long 型を用いれば十分だ。

計算量も $O(N (\log N + \log S + \log C))$ と評価できる。

コード

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

int main() {
    int N;
    cin >> N;
    map<long long, long long> ma;  // f の値で場合分け
    for (int i = 0; i < N; ++i) {
        long long S, C;
        cin >> S >> C;
        
        // S を 2 で割れるだけ割った値を求める
        int f = S;
        while (f % 2 == 0) f /= 2;
        ma[f] += (S / f) * C;
    }
    
    long long res = 0;
    for (auto [val, num] : ma) res += __builtin_popcountll(num);
    cout << res << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 323 D - Merge Slime (緑色, 425 点)

問題概要

制約

考えたこと

コード