競技プログラミング

ABC153C Fennec vs Monster

問題

https://atcoder.jp/contests/abc153/tasks/abc153_c

方針

体力の多いモンスターに対して、優先的に必殺技を使う

ポイント

  • 組み込み関数sortを用いるとよい
    • 昇順にソートが行われる
  • ソート済みのリストに対してスライスをし、合計を計算すれば良い
    • 小さい順（先頭から）にスライスを行う
      • N(モンスターの数)からK(必殺技を使える回数)を引いた数がスライスの位置（攻撃で倒す必要があるモンスターの数）となる
    • モンスターの数以上に必殺技を使える場合(N<=K)に注意する
      • 組み込み関数maxを用いることで、スライスの位置が0以上になることを保証できる

コード

1
2
3
4
5
N, K = map(int, input().split())
H = list(map(int, input().split()))
H.sort()
idx = max(N-K,0)
print (sum(H[:idx]))

メモ

組み込み関数sortedを用いた場合、ソートされたリストが返却される。

一方、メソッドsortをコールした場合、元のリストがソートされる。

このような上書きされる処理をインプレースな処理と呼ぶ。返却値はない(None)であることに注意する。

1
2
3
4
5
6
>>> ls = [1, 4, 5, 3, 2]
>>> sorted(ls) # ソートされたリストが返却される
[1, 2, 3, 4, 5]
>>> ls.sort() # インプレースに変更する。この場合は値の返却はない
>>> ls
[1, 2, 3, 4, 5]

発展

PythonのソートアルゴリズムにはTimsortが用いられている。平均計算量、最悪計算量ともにO(nlogn)である。