B - Colorful Creatures

概要

$N$ 体のスライムがいる。 $i$ 番目のスライムの色は $i$ で、大きさは $A_i$ である。

スライムは大きさが自分の 2 倍以下の他のスライムを吸収することができる。 色 $i$ のスライムが色 $j$ のスライム吸収すると、色 $i$ で大きさが $A_i + A_j$ のスライムになる。

$N$ 匹のスライムたちの間で吸収が何度か行われ、最終的に 1 匹のスライムが残った。この残ったスライムの色として考えられるものの数を答えよ。

概要

• $2 \leq N \leq 10^5$
• $1 \leq A_i \leq 10^9$

解説

以降 $\{A_i\}$ は単調増加とする。

$i$ 番目のスライムが最後まで残れるかどうか判定する方法を考える。

まず自分より小さいスライムは明らかに吸収できる。大きくて損することはないので、これらは最初に全部吸収してよい。 もしこの状態で $i + 1$ 番目のスライムを吸収できなかったら、どう足掻いてもこれより大きいスライムを吸収できないため、答えは NO となる。 吸収できるなら、これを吸収して $i + 2$ 番目のスライムを吸収できるか調べる。 これを繰り返して、最終的に $N$ 番目のスライムを吸収できたら OK となる。

しかしこの判定を各スライムに対して実行すると、計算量が $O(N^2)$ で TLE となってしまう。

実は「スライムが最後まで残れるか否か」は、スライムの大きさについて単調性が成り立つ。つまりあるスライムが残れるなら、それ以上に大きいスライムは全て残れることになる。 したがって「最後まで残れる中で最小のスライム」を二分探索で求めることで、計算量を $O(N \log N)$ まで落とすことができる。

これでも普通に良いのだが、私が実際に実装したのはちょっと違った。 以下の実装例は「小さいスライムから順に吸収していって、吸収できなくなったらカウントをリセットする」というもの。このとき最終的なカウントが答えとなり、計算量は $O(N)$ となる。

実装例

提出 #34713000 - AtCoder Grand Contest 011

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#include <algorithm>
#include <iostream>
using namespace std;
using ll = long long;

int main() {
    ll N;
    cin >> N;
    ll A[N];
    for (ll i = 0; i < N; ++i) {
        cin >> A[i];
    }
    sort(A, A + N);

    ll ans = 0, sum = 0;
    // sum = i匹目までの大きさの総和

    for (ll i = 0; i < N; ++i) {
        // i匹目まで全部くっついたやつはi+1匹目を吸収できるか?
        if (sum * 2 < A[i]) {
            // 吸収できないのでカウントリセット
            ans = 0;
        }
        sum += A[i];
        ++ans;
    }

    cout << ans << endl;
    return 0;
}