B39のPython解答例はTLEする。

[6789-yc]

B39において、D<=2000では、O(DN)であるPythonの解答例はTLEとなります(部分点はもらえる)。同じアルゴリズムでもC++は間に合うのですが、Pythonでは間に合いません。まだ競プロ初心者である私は計算量改善が思いついていません。解答例か制約の修正をお願いしたいです。

[E869120]

大学の試験などの影響で返信が遅くなり申し訳ございません．

まず，問題 B39 は以下の 2 つの節で利用されている問題になっています．
　- 6.4 節：貪欲法によって O(DN) で解くことが目標．
　- 8.3 節：優先度付きキューを使って O(N log N) に改善することが目標．

そのため，6.4 節の解法で TLE となるのは想定通りですので，ご安心ください（逆に C++ が通ってしまうのが問題）．また，アルゴリズムを改善するためのヒントは，鉄則本の 8.3 節，および解説 PDF の 102 ページを参照してください．

[6789-yc]

お忙しい中、ご回答いただきありがとうございます。
そういうことでしたら、前から順番に進めようと思うと混乱してしまうと思うので、問題ページの部分点の欄などで、その旨を記載するとわかりやすいと思います。