AtCoder Regular Contest 118 B – Village of M People をPython3で解く

Share

AtCoder上にある問題のうち、AtCoder Problemsでdiff 800以上と判定されているものを順番に解いていく企画。
基本的な考え方は全てコード中のコメントに入れてあるので、参照のこと。

出典:
AtCoder Regular Contest 118 B – Village of M People

そういや一時期「世界がもし100人の村だったら」って流行ったよね~ということを思い出す問題。え……あの本出てからもう20年経ってるの……?

# AtCoder Regular Contest 118 B - Village of M People
# https://atcoder.jp/contests/arc118/tasks/arc118_b
# tag: 整数 分割 差分最少 ARC国

# max(sum(|B/M - A/N|)) を最少にしたい。

# とりあえず、各レーティングに対して、 A * M // N 人を
# 振り分ける(厳密値の切り捨てにあたる)。
# 若干振り分ける人数が足りなくなるが、その残りを
# どのように振り分けるか。

# 上記振り分け後の厳密値(誤差 0 になる有理数人数)に対する誤差は、
# -1 より大きく 0 以下 に収まっている。
# 収まっている。つまり、余っている人数は K 人未満。

# 各レーティングごとの |B/M - A/N| (あるいは |N*B - M*A|)が
# 大きいものから順に、一人ずつ割り振ってやればいい。

def main():
K, N, M = map(int, input().split())
ratings = list(map(int, input().split()))

# 暫定振り分け
result = [M * a // N for a in ratings]

# 残り人数
rem = M - sum(result)

# 各レーティングごとの誤差をチェックし、ソート
diff = [(abs(N * result[i] - M * ratings[i]), i) for i in range(K)]
diff.sort(reverse=True)

# 誤差が大きいところ(厳密値に対して人数がより足りないところ)に
# 1 ずつ加えてやる
for _, idx in diff[:rem]:
result[idx] += 1

# 回答を出力
print(*result)

main()
Share

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です