roiti46's blog

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

Codeforces #301 Div2 B: School Marks

不用意にLockしたら撃墜されて再提出できなかった・・・。

問題はこちら

問題

ある生徒はn個のテストを受けなければならない。1つのテストの点数の範囲は1点からp点までである。生徒は目立ちたくないのでテストの合計点をx点以下に抑えたい。同時に母親にあまり悪い成績を見せられないので、すべてのテスト結果を点数のいい順に並べたとき、(n+1)/2番目の点数がy点以上になるようにしたい。現在k個までのテストを受けて点数がわかっている。この生徒はこれらの条件を満たすように残りのテストの点数を調節できるかどうか、できるなら具体例を1つ答えよ。

解答

y点以上のテストが(n+1)/2個以上欲しい。またテストの点数はできるだけ低く抑えたい。
したがって、のこりn-k個のテストでは、y点以上のテストが合計(n+1)/2個になるまでy点の点数を取っていき、(n+1)/2個を超えてからは1点を取ればいい。
最後にテストの合計がx点以下であることと、y点以上のテストが合計(n+1)/2個以上になっているかを確認する。

n, k, p, x, y = map(int, raw_input().split())
a = map(int, raw_input().split())
cnt = 0
for i in xrange(k):
    if a[i] >= y: cnt += 1

m = (n + 1) / 2
ans = []
while len(ans) < n - k:
    if cnt < m:
        ans.append(y)
    else:
        ans.append(1)
    cnt += 1
    
if sum(a) + sum(ans) <= x and cnt >= m:
    print " ".join(map(str, ans))
else:
    print -1

まとめ

撃墜されたコードは自分でも変な実装だと思っていたのでせめて自分が理解できるふうに書かないと。