最終更新: 2020-10-09T18:36+0900
精進ですよ。今日*こういうものを読んだ。
「【Python】平衡二分木が必要な時に代わりに何とかするテク【競プロ】 - Qiita
」
この前の日記(20200907p01)で散々 TLE に苦しめられた問題も、C++ なら変数 r を map に、変数 nmin を multiset にすることで、ある範囲のキーを二分探索で検索することも、小さい方からキーを取り出すことも、STL 任せで妥当な時間で行える。適当に速くて短い提出を選んだけどこんな感じ>「提出 #16578878」。トリックは必要ない。
Qiita の記事で題材にされているのが今日の E 問題 Roadwork で、記事をよく理解するためにまず解きたいと思った。
とってもくやしい。
最悪の場合に 200k 要素の配列に 200k 回書き込みを行うのが良くないのかなと思う。掛けて 40G×単位サイズの書き込み量。あ、これはやべーわ。
遅延更新と区間更新が可能なセグメントツリーがあればこのアホな書き込み量はなんとかなる気がするなあ。
ループの中でがっつり二分探索して配列のスプライシングをしても通るあたり、この前の F 問題(前掲)より易しい。
二分探索がしたい、線形よりましな時間で挿入がしたい、というときに平衡二分探索木が欲しくなるんだよね。
プライオリティキューを実装するときも、最大(最小)値を得るだけでなく、整列済みのキューにアクセスして操作したいときがある。でも内部構造がヒープだからできない。std::multiset とは違う。
２本目のキューに削除済みとマークした要素を入れておくの頭いい(Qiita の記事)。二分探索はできないけど、一度放り込んだ値を後から取り消したいときが、たしかに以前あった。
Ruby のバージョンが違うので一概に比較できないけど、他の AC はどれもヒープを使用していて 1000 ms 以上かかっているところが共通している。配列のスプライスよりヒープの方が賢いよね。
でもスクリプトで手の込んだことをするよりインタープリタに丸投げした方が速いこともある。Python は汎用スクリプト言語でありながらそういうバッチファイル的、グルー言語的なあり方も板についている。
たとえば、ダイクストラ法、ワーシャルフロイド法などのアルゴリズムが名前で利用できる。ヒープ構造もある。二分探索も、比較式をブロックで与えられる汎用性が Ruby にはあるが、それが遅さに繋がってしまう。実は lower_bound, upper_bound だけでほぼ足りる。オブジェクトの形が不定だとしても、key 配列と value 配列を持てば解決する。
Ruby に範囲を指定する Array#fill があるのを、しかも古くからあるのを知ったときは嬉しかったし、同時に自分の不明も明らかになった。Ruby は汎用スクリプト言語だからループやイテレータを使って Array#fill 相当の処理は自在に書ける。書いてきた。でも書かずに fill を１回だけ呼び出すのが賢い(が、実は Ruby で実装されています、という可能性もなくはない)。
* 日記を書いている今日は10日。