AtCoder Grand Contest 011 B - Colorful Creatures

問題

 N匹の生き物がそれぞれ大きさA_iを持っており、自分の2倍以下であるような他の生き物を吸収できるとする。吸収したとき生き物の大きさは吸収元と吸収先の大きさの和となる。吸収を繰り返して最終的に1匹になるとするとき、残った生き物としてあり得る種類の数を求めよ。

解法

 解説PDFとほぼ同じ。

 大きさでソートして大きい方から考える。自分より小さいものは吸収できるので一番大きいものは残りうる。二番目に大きいものは、自分より小さいものを全て吸収しきった大きさが、一番大きい生き物の大きさの\frac{1}{2}以上ならば残りうる。二番目に大きいものが残りえないとき、三番目以下が生き残ることはない。

 これを一般化していき、iを(0-originとして)N - 2から0まで動かしていき、0からiまでの累積和の2倍がA_{i + 1}以上ならOK、未満だったらそこまでOKだった数を返せばいい。

#include"bits/stdc++.h"
using namespace std;
using ll = long long;

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

    sort(A.begin(), A.end());

    //累積和
    vector<ll> sum(N, 0);
    sum[0] = A[0];
    for (ll i = 1; i < N; i++) {
        sum[i] = sum[i - 1] + A[i];
    }

    for (ll i = N - 2; i >= 0; i--) {
        if (sum[i] * 2 < A[i + 1]) {
            //ダメだった
            cout << N - 1 - i << endl;
            return 0;
        }
    }

    cout << N << endl;
}

反省

 約17分でAC。大きさでソートするところが見えてからはわりとすぐだったが、最初は二分探索でどこまで超えられるかなどの無駄な思考をしていた。次の1個が超えられるかが大事なので二分探索などする必要はない。

 色と大きさという二つの要素が与えられるが、色にはほとんど意味がなくて大きさでソートしてしまえるというところに気づくところが一番重要なところだと感じる。これはどうやって思いつくかというと、ある種の慣れだったりするんだろうか。