Mister雑記

競プロやります。

AGC011-B 「Colorful Creatures」 (400)

beta.atcoder.jp

概要

 N匹の生き物がいて、色 iの生き物の大きさは A_iである。

各生き物は大きさが自分の2倍以下の生き物を吸収することができ、吸収後の色はそのままで大きさは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)となる。

上2つの解法は、本質的には「二分探索か尺取り法か?」という問題と同じ話である。後者の方が若干速いが、競プロではどっちでも大差ない。

実装例

#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;
}

感想

  • AGCの400だなぁという印象。
  • 小さい方から順に吸収するのも割と自然な発想だと思う。