AtCoderBeginnerContest329 F問題500点 「Colored Ball」
https://gyazo.com/83df7a2ec990e4b4f64f261c77fc730d
問題概要
制約
気持ち
解法
解法を考えてみると、実際に「箱 a のボールをすべて箱 b に動かして何種類のボールがあるかを答える」必要がありそうです。
では、上記を行ううえで、 TLE せずに解ける方法があるかを考えます。
直感的に、ボールが少ない箱 $ xから、ボールが多い箱 $ yに向かってボールを移したほうが良いことがわかります。
https://gyazo.com/f3df4da892a1c183d599f09777615bbf
よって、以降の「箱に入っているボールを移動させる」処理は、ボールの種類が少ない箱から、ボールの種類が多い箱に向かって移動させるように行います。
このとき、それぞれのボールを移動させる回数は最大何回になるのでしょうか。
あるボール $ zについて、このボールを移動させる回数について考えてみます。
ボール $ zが存在する箱 $ xの色の種類数を $ s(x), 移動先の箱$ yの色の種類数を $ s(y)とします。
このとき、先程の移動方針を考えると $ s(x) < s(y)です。
ボール $ zごと、箱 $ yに移動させると、箱 $ yの種類数は $ s(y) \leftarrow s(y) + s(x)になります。
(種類数なので、正確には同じ色が重複する場合があります)
このとき、箱 $ yの種類数は、箱 $ xの種類数の約 2 倍になります。
よって、ボール $ zを移動させる場合、移動先の箱のボールの種類数が毎回 $ 2倍になっていきます。
そのため、あるボール $ zを移動させる最大の移動回数は $ \log_2N回になります。
全部のボールについて考えると、全体の移動回数は $ N \log_2N程度に収まることがわかります。
よって、計算時間は思った以上に高速で行なえます。
計算量
$ O(N \log N)
新たな学び
集合をマージする場合、より大きな集合にマージする
反省点
コード
code: cpp
int main() {
int N, Q;
cin >> N >> Q;
vector<set<int>> st(N);
for (int i = 0; i < N; i++) {
int x;
cin >> x;
x--;
}
for (int q = 0; q < Q; q++) {
int a, b;
cin >> a >> b;
a--, b--;
if (sta.size() > stb.size()) { for (auto x : stb) sta.insert(x); } else {
for (auto x : sta) stb.insert(x); }
cout << stb.size() << endl; }
}