Arantium Maestum

プログラミング、囲碁、読書の話題

蟻本初級編攻略 - 2-2 硬貨と区間

ようやく全探索章を終え、貪欲法の章に進む。

貪欲法に関して蟻本で出てくる最初の2問はあまり適当なAtCoderの問題がないようだ。とりあえず蟻本の問題を解いていく。

硬貨の問題

1円から500円までの硬貨を特定の数ずつ持っているとして、ある金額に合計する最小の硬貨の組み合わせを見つける問題。

*coins, total = [int(x) for x in input().split()]
values = [1, 5, 10, 50, 100, 500]

res = 0 
for max_count, value in zip(coins[::-1], values[::-1]):
    count = min(total // value, max_count)
    res += count
    total -= count * value

print(res)

大きい硬貨からはじめる貪欲法で、割り切れるだけの数とその硬貨を持っている数のminの分金額をどんどん差し引いていく。

区間スケジューリング

始まりと終わりの時間が指定されている複数のタスクがあり、時間がまったくかぶらないという条件でこなせるタスクの最大数を求める問題。

タスク終了時がもっとも早いものを貪欲法でとっていく。

この問題は三ヶ月前にも解いていた:

zehnpaard.hatenablog.com

今だったらどう書くかな、と気になったので試しに1から解いてみた:

_ = int(input())
s = [int(x) for x in input().split()]
t = [int(x) for x in input().split()]

solution = [(None, -1)]
xs = sorted(zip(s, t), key=lambda x:x[1])
for task in xs:
    if task[0] > solution[-1][1]:
        solution.append(task)

print(len(solution)-1)

ほとんど変わっていない。変数や行数が減っているがその分少しだけロジックがややこしくなっているか?