roiti46's blog

主に競プロ問題の解説を載せてます

Google Code Jam 2015 Qualification Round: A. Standing Ovation

GCJのQualに参加。全問提出したがD-largeは落ちてしまい74点で予選通過。R1は突破したい。

問題はこちら

問題

オペラの観客が何人かいる。観客にはそれぞれ内気度があり、内気度iの人はi人がすでに立ち上がっていないと立ち上がらない(内気度0の人ははじめに立ち上がる)。あなたは内気度0の友達を任意の数、観客として呼ぶことができる。観客の中の最大の内気度と内気度別の観客数を与えられるので、全員がスタンディングオベーションするのに誘う必要のある友達の人数の最小値を答えよ。

解法

内気度の小さい方から観客の数を足し合わせていく。そのあと内気度の小さい方から見ていき、内気度iの人たちが立ち上がるのに観客が足りないときには必要な数だけ友達を足せばいい。これを最大の内気度まで計算すれば、必要な友達の最小値が得られる。O(N)。

T = int(raw_input())
for loop in xrange(T):
    Sm,S = raw_input().split()
    Sm = int(Sm)

    histo = [0]*(Sm+1)

    for i in xrange(Sm+1):
        histo[i] = int(S[i])

    for i in xrange(1,Sm+1):
        histo[i] += histo[i-1]

    ans = 0
    for i in xrange(1,Sm+1):
        if histo[i-1]+ans < i:
            ans += i-(histo[i-1]+ans)
    print "Case #%d: %d"%(loop+1, ans)

まとめ

ABCのBかCでありそうな問題だ