AGC011 B Colorful Creatures

AtCoder Grand Contest 011の B の Colorful Creatures を解いた。
解説と違ってたから、解説を書く。
2分探索を使って解いた。

問題はこれ
B - Colorful Creatures
解説はこれ
https://img.atcoder.jp/agc011/editorial.pdf

解説

全ての生き物の色が異なるので、大きさでソートすることで、
 A_1 \leq A_2 \leq \cdots
としても一般性を失わない。

最終的に、i 番目の生き物の色になるには、
 \{A_j\}_{j \neq i} を小さい方から順番に吸収していくことができればよい。
つまり、次のような条件を考えれば良い。
 \{b_j\}_{i \leq j \leq n} を次のように定める。
 b_i = \sum_{j=1}^i A_i
 b_{j+1} = b_j + A_{j+1}
b_i が上のように定まるのは、自分より小さい生き物は必ず吸収できるためです。
このとき、任意の  j \leq i に対して、
 A_{j+1} \leq b_j \times 2
を満たせば良い。これが条件。

これを全ての  i に関してやればよいが、それでは  O(N^2) になってしまう。

ところで、この条件はある  i に関して成立すれば、それ以降の添字でも成立する。
これは、実際は  \{b_j\} i に依存しない数列だからです。

というわけで、2分探索を実行できます。

解答

解答では、 \{b_j\}i に依存しないことを利用して少し短くしています。
別に、毎回計算しても間に合います。
というか、初めはこれで通しました。
コメントアウトに書いておきます。

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くらい変わる。

ちなみに、解説は  O(N) だけど、これは  O(N \log(N)) です。