AtCoder Grand Contest 011の B の Colorful Creatures を解いた。
解説と違ってたから、解説を書く。
2分探索を使って解いた。
問題はこれ
B - Colorful Creatures。
解説はこれ
https://img.atcoder.jp/agc011/editorial.pdf。
解説
全ての生き物の色が異なるので、大きさでソートすることで、
としても一般性を失わない。
最終的に、 番目の生き物の色になるには、
を小さい方から順番に吸収していくことができればよい。
つまり、次のような条件を考えれば良い。
を次のように定める。
、
。
が上のように定まるのは、自分より小さい生き物は必ず吸収できるためです。
このとき、任意の に対して、
を満たせば良い。これが条件。
これを全ての に関してやればよいが、それでは になってしまう。
ところで、この条件はある に関して成立すれば、それ以降の添字でも成立する。
これは、実際は が に依存しない数列だからです。
というわけで、2分探索を実行できます。
解答
解答では、 が に依存しないことを利用して少し短くしています。
別に、毎回計算しても間に合います。
というか、初めはこれで通しました。
コメントアウトに書いておきます。
from itertools import accumulate N = int( input()) A = list( map( int, input().split())) A.sort() l = -1 r = N-1 B = list( accumulate(A)) while r - l > 1: m = (l+r)//2 check = 1 #now = sum(A[:m+1]) for i in range(m+1,N): if A[i] <= B[i-1]*2: pass # if A[i] <= now*2: # now += A[i] else: check = 0 break if check == 1: r = m else: l = m print(N-r)
おまけ
100msくらい変わる。
ちなみに、解説は だけど、これは です。