AGC041 B - Voting Judges
問題原文
解法
とりあえず降順ソート。
ついでに 上位 番以内に入るために最低限必要なボーダーも求めておく。
番目が採用されるような時、 番目も採用されるので、単調性があることがわかる。
つまり答えの境界を二分探索できる。
ここからは二分探索内部パート。
番目ができるだけ採用されるように頑張ることを考える。
まず、 人全員はとりあえず 番目に投票すべき。これで 番目のスコアは になる。(これを とする) またこの時点でボーダーを達成していなければ明らかに達成不可能。
次に、残り 票を を超えないように割り振り切ることを考える。
まず条件として、 票より多く割り振ることはできない。(1つの問題に投票できるのは1人1回なので)
つまり、ある に対して、 票まで割り振ることができる。
また、上位 番以内に入っていて ボーダーを超えているようなもの は、 が採用されるのとは実質関係ないので 票入れてしまって良い。(ボーダーピッタリのやつまで対象にするとボーダーがこわれる)
実装
N, M, V, P = map(int, input().split()) A = sorted(list(map(int, input().split())), reverse=True) BORDER = A[P - 1] # にぶたん: x番目の問題が採用される可能性があるか? ok, ng = 0, N while abs(ok - ng) > 1: x = (ok + ng) // 2 x_score = A[x] + M remain_vote = M * (V - 1) if x_score < BORDER: ng = x continue for i, a in enumerate(A): if i == x: continue elif i < P and A[i] > BORDER: remain_vote -= M else: remain_vote -= min(M, x_score - a) if remain_vote <= 0: ok = x else: ng = x print(ok + 1)
感想
なんか一回間違って3週間ぐらい放置してたら解けた!w