F - Fishing Editorial by toam
Python で通す方法想定計算量が \(O(N^2 \log N)\) の問題で \(N=2000\) は Python にとって非常に厳しいです.定数倍を頑張って高速化するテクニックの一つを共有します.
この問題のボトルネックは,時刻と差分をペアにしてソートする部分です.以下のように時刻と差分のペアをタプルにしてリストに突っ込み,このリストを(時刻を key にして)ソートしようとすると,この問題では到底間に合わないと思います.タプルのソートは key を指定したとはいえ非常に重いです.
event=[(時刻 1,差分 1), (時刻 2,差分 2), ...]
event.sort(key=lambda x:x[0])
そこで,タプルのソートを回避します.event の時刻を key にする連想配列を以下のように作り,時刻の昇順に連想配列の情報をなめるようにします.
dic=defaultdict(int)
for 時刻, 差分 in event:
dic[時刻]+=差分
tmp=0
for i in sorted(dic.keys()):
tmp+=dic[i]
このようにすることで,筆者はこの問題においては体感 \(2\) 倍程度の定数倍を改善することができました.
また,小数を扱う代わりに,実数 \(x\) を \(\lfloor 10^9x \rfloor\) のように整数に変換して扱うことでも定数倍改善をすることができました.
(追記) タプルのソートの高速化の一般的な手段として,タプルの情報を整数に変換するというものが挙げられますが,今回の問題においても上記で述べたように時刻の情報を整数に変換したうえで event の情報を整数として持つことにより,高速化することが可能なようです.
posted:
last update: