mini notes

競技プログラミングの解法メモを残していきます。

ICPC夏合宿2010:day2B 友だちの誘い方

問題:http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2331&lang=jp

解答:AIZU ONLINE JUDGE: Code Review

解法:x人が参加するとした場合に、参加できる人の数を数え、それがx-1人(「私」を除くため)以上でる最も大きなxが答え。

xが与えられたときに毎回参加できる人数を数えるとTLEなので、参加可能人数をいもす法のように管理する。すなわち、ai ≦ x ≦ biなら参加可能の場合、v[ai-1]--, v[bi]++とし、後ろから累積和をとると、与えられたxに対し何人参加可能かがO(1)で分かる。