Codeforces #325 Div1 A(Div2 C): Gennady the Dentist

CF#325 Div2に参加。D問題のpretestに問題があったらしく、コンテスト終了後にpretestを通ったはずのDの回答がpretest落ちになってしまい、ABCの3完。CでWAを連発したのが響いて、1748 → 1739 (-9)。

問題はこちら。

問題

歯科医の前にN(<=4000)人の子供たちが行列を作っていて各子供には1から順番に数字がふられている。子供iには、治療の際の泣き声の大きさv[i]、逃げ出すときの泣き声の大きさd[i]、自信p[i]の3つの値が設定されている。
i番目の子供は治療されるときに大きさv[i]の声で泣く。泣き声は行列の先頭からの距離に対して減衰していく。ある大きさの泣き声を聞いた子供はその分だけ自信を減らす。
自信が0を下回った子供jは大きさd[j]の声で泣きながら、出口へと走り去っていく。このとき、子供jより後ろにいたすべての子供の自信はd[j]だけ減る。逃げ出す子供がいなくなるまでこれが繰り返される。なお行列が詰められるのは逃げ出す子供がいなくなってからとする。
このような条件下で歯科医は何人の子供を治療できるか。その人数と治療できる子供の番号を答えよ。

解法

単純にループを回して愚直にシミュレーションするだけで解ける。ある子供は治療されるか逃げ出すかのどちらかなので、各治療の際に逃げ出す子供をすべてシミュレーションしてもO(N²)となる。以下の解法はpythonだがpypyで投げないと間に合わないので注意。

n = int(raw_input())
v, d, p = [], [], []
for loop in xrange(n):
    vi, di, pi = map(int, raw_input().split())
    v.append(vi); d.append(di); p.append(pi)

run = [False] * n
for i in xrange(n):
    if run[i]: continue
    cnt = 0
    for j in xrange(i + 1, n):
        if run[j]: continue
        p[j] -= v[i] - cnt
        cnt += 1
        if cnt == v[i]: break
    for j in xrange(i + 1, n):
        if run[j]: continue
        if p[j] < 0:
            run[j] = True
            for k in xrange(j + 1, n):
                if run[k]: continue
                p[k] -= d[j]

ans = []
for i in xrange(n):
    if not run[i]:
        ans.append(i + 1)
print len(ans)
print " ".join(map(str, ans))