AtcoderでTLEとなる原因について【ABC問題】

Question

Atcoderの問題についてです．
TLEになってしまい，その原因がわかりません．
簡単なサンプル入力に対しては，きちんと時間内に正解して，testcaseでも一部は正解になります．
複雑な処理ではないはずなので，間違いがあるのかと思うのですが…

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
list = [int(i) for i in input().split()]
for i in range(m):
  list[list.index(max(list))] = max(list)//2
print(sum(list))

Answer 1

TLEになってしまい，その原因がわかりません．

ループ1回毎にlist.index(max(list))と最大値を走査していますので、O(NM)だけの時間がかかってしまいます（しかも、maxとindexでlistを2周する必要が出てきます）。

リストの全探索が必要ないように、保管するデータ構造を工夫する必要があるかもしれません。

---

複雑な処理ではないはずなので，間違いがあるのかと思うのですが…

データ量が多くなると、「シンプルな処理では遅くて使い物にならない」という例が出てきます。

Comments

[kiyushi]

超初心者なので，実装速度を気にしてコードを書いたことがなく，「シンプルな処理では遅くて使い物にならない」ことがあるということが頭にありませんでした．
早い回答ありがとうございました．

Answer 2

AtCoder実行時間制限に収めるには O(１０**7) 程度の計算量でおさめないといけないといわれています。

ABCのC問題以上では 10**5 個程度の要素を扱う問題が多く、愚直な2重ループなど行うと O(10**10) の計算量となり間に合いません。
そのため2重以上のループは極力避けないといけません。

list のsizeが 10**5 であると仮定します。

for i in range(m):
  list[list.index(max(list))] = max(list)

私はPythonの max 関数の内部実装は知りませんが (O(配列の要素個数)) 相当のループ処理をしていると思います。
こちらを見ると O(n) の計算量とあるので多分そうですね。

そのため実質2重ループになっており O(10**10) の計算量になっているのではないでしょうか。

C問題以上は素直な全探索ループではTLEしてしまうように作られているので計算量を削減するよう工夫しなければなりません。

そしてこの問題の模範解答としてはPriorityQueueというデータ構造を活用すると計算が間に合います。

Comments

[kiyushi]

C問題以上は素直な全探索ループではTLEしてしまうように作られているのですね！知りませんでした．
早い回答に感謝します．ありがとうございます．

Answer 3

ヒープ木を組めば最大値の更新が高速になるように思います。

---

コメントで指摘を受けているとおり、次の回答は誤りです。
ソートして、先頭のm個を半額で／残りの要素を定額で計上すれば良いのでは。

Comments

[maisumakun]

一品に複数枚使うこともできますので、それでは最適な解が得られません。

「100円と10円の商品券に割引券2枚」という場合、100円のものに2枚使う、というのが正解です。

[LouiS0616]

『品物を買う際に割引券を好きな枚数使うことができます。』
ご指摘のとおりです。見落としていました。