AT274の技術だったりなかったり

あっとのTECH LOG

競プロのこととか技術のこととか。たまに日常を書きます。

AGC041 B - Voting Judges

問題原文

atcoder.jp

解法

とりあえず降順ソート。
ついでに 上位  P 番以内に入るために最低限必要なボーダーも求めておく。

x 番目が採用されるような時、  x - 1 番目も採用されるので、単調性があることがわかる。
つまり答えの境界を二分探索できる。

ここからは二分探索内部パート。
 x 番目ができるだけ採用されるように頑張ることを考える。

まず、  M 人全員はとりあえず  x 番目に投票すべき。これで  x 番目のスコアは  A_x + M になる。(これを  X とする) またこの時点でボーダーを達成していなければ明らかに達成不可能。

次に、残り  M × (V - 1) 票を  X を超えないように割り振り切ることを考える。
まず条件として、  M 票より多く割り振ることはできない。(1つの問題に投票できるのは1人1回なので)
つまり、ある  A_i に対して、 \min(M, X - A_i) 票まで割り振ることができる。
また、上位  P 番以内に入っていて ボーダーを超えているようなもの は、 A_x が採用されるのとは実質関係ないので  M 票入れてしまって良い。(ボーダーピッタリのやつまで対象にするとボーダーがこわれる)

実装

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