AtCoder上にある問題のうち、AtCoder Problemsでdiff 800以上と判定されているものを順番に解いていく企画。
基本的な考え方は全てコード中のコメントに入れてあるので、参照のこと。
出典：
AtCoder Grand Contest 011 B – Colorful Creatures
より小さな生物の色が残るための条件とは……といったところから考察を始めると、考えやすいと思う。
# AtCoder Grand Contest 011 B - Colorful Creatures
# https://atcoder.jp/contests/agc011/tasks/agc011_b
# tag: 事前ソート 累積和 考察
# 小さいものから順番に、ひとつ上の大きなものを吸収させていき、
# 吸収できなくなれば一旦ストップ・次のものを最初にして
# 再スタート。どこかから最後まで行き着くことができれば、
# 最後に再スタートしたところ～最後のどの色にもなることが
# できる……みたいな。
# 例えば、
# 1, 2, 3, 100, 200, 300 という大きさの生物がいるとしたら、
# 1, 2, 3 は、どう頑張っても最後に残ることが出来ない。
# その条件は、(1 + 2 + 3) * 2 が 100 未満であること。
# 逆に、100, 200, 300 については
# 100←6, (100+6)←200, (100+6+200)←300
# と食べさせることで、100 を最後に残すことができるが、
# この場合 100 を 200 や 300 と入れ替えても同順の
# 捕食が可能なので、100, 200, 300 のどれでも最後に残せる。
# 吸収できるかどうかはそれまでに吸収したもの全ての大きさの
# 合計が関わってくるので、累積和を使用すると楽。
def main():
N = int(input())
A = list(map(int, input().split()))
# ソートして累積和を取る
A.sort()
csum = []
tmp = 0
for a in A:
tmp += a
csum.append(tmp)
start = 0
now = 1
while True:
if now == N:
break
# 一つ前までの合計で、今考慮している生物を吸収可能かどうか
if csum[now - 1] * 2 >= A[now]:
now += 1
else:
start = now
now += 1
print(N - start)
main()
関連
