脳log[20220228]

2022年02月28日 (月) [AtCoder] 復習(精進と復習の違いは初めて AC したかすでに AC していたかということにしてる)。20220226に関連して ABC217-D「Cutting Woods」と ABC241-D「Sequence Query」の２問。■一切の猶予なしに左右のバランスを常にとる二分木を配列に詰め込んだものは二分探索のために予め並べ替えただけのソート済み配列なのではないか、性質はそれと同じか実装を頑張った分だけ遅いだろう、二分ヒープがテキトーにつっこんだ数列からソート列を効率良く取り出せるのは内部構造の制約がほどよく緩いからだろう、じゃあちょっとルーズにするとある程度幅を持った固定長のソート済み配列が入れ子になったものになるのかな、それって (a,b)-木って名前がついてるもののことかな、っていうのが 20200930p01 の内容。■Cutting Woods の提出 #29779137 (AC / 1551 Byte / 578 ms)。Sequence Query の提出 #29779230 (AC / 1523 Byte / 865 ms)。どちらも 30 から 60 の範囲に長さを制限したソート済み配列を入れ子にした構造を共通に利用していて、1.5 KB のほとんどがそれ。問題に固有の部分はどちらも 10 行前後。次はこれを貼り付けよう。でもまだ必要なかったから削除操作はないよ。■Sequence Query を Ruby で AC してる提出を見てみると色々ある。BIT/ST を使ったもの>#29681469、#29688407、#29763276。LazySort というどうして速くなるのかよくわかんないアイデアを使ったもの>#29722776。色々っていうか今のところ AC はこれだけ。BIT を使った解法はコンテスト中に一番に考えたんだよね。20220111の日記から PAST の「Deadnames」に提出したソースコードを探してきて貼り付けた。でも WA に TLE に RE と散々の結果だったので(#29703047)、見切りをつけて別の方向に行ったのだった。■(2,3)-木でやろうとしているお仲間がいた>#29773657 (WA/TLE)。図書カードにいつも見つける名前のように「アルゴリズムと数学　演習問題集」の提出欄に常に先んじて名前が残っている人だよね。完成させてほしい。□ていうか完成してるよね？ Cutting Woods のテストケースはすべて通った。Sequence Query のサンプルは que2 メソッドの (k-1).times を k.times にすると合うようになる(search メソッドの仕様が適切にコメントしてあるからすぐわかる)。あとは速度だけ。それも 2182 ms であって 22xx ms とは違うから 182 ms 削るだけ。■テストケースが利用できる Cutting Woods でソート済み配列の分割パラメータである A,B を 30,60 から何パターンか変えて実行してみると、ほとんど傾向は変わらないんだけどやっぱり 2,3 くらい極端だとちょっと遅い。Ruby で実装してるから動的配列でありオブジェクトであるノードを細かく分けると空間コストも操作コストも無駄に大きくなりがち。スクリプトはできるだけ多くの処理をインタープリタに任せる方が性能が出やすいと思う。もちろんインタープリタもアルゴリズムのオーダーには従うから構造を工夫しているところではあり、その範囲内でのことだけど(全部を１つの Array につっこむ無茶をインタープリタに任せるとは言わない)。■めでたい。提出 #29810599 (AC /「2-3木 (高速化した第2版。仕様も変わっているので注意)」)