線形篩と呼ばれているアルゴリズム・データ構造があります。 「線形時間で前計算できる何々」を「線形何々」と呼ぶのは不適切ですか、もしかして？*1 ざっくり紹介 構築に関して 発展編 実装 練習問題 おわり $\gdef\lpf{\operatorname{lpf}}$ ざっくり紹介 …

「競プロライブラリにおける抽象化と言えばセグ木」みたいな風潮ができてから久しいですが、二分探索に関してそうした抽象化を意識している人はあまり多くない気がしています。 おきもち 整理・設計 実装 その他 実装に関して 中間値に関して お気持ちに関し…

C なんだけど、答えをベタ書きした Python のコードを gzip で圧縮して Base64 でエンコードしたやつを、復元して実行することで AC できる pic.twitter.com/xsPaFGoi0u— えびちゃん (@rsk0315_h4x) June 8, 2024 「埋め込みするにあたってもちゃんとしたコ…

rsk0315.hatenablog.com B-tree が書けたらまた自慢しに来ます。 書けました。一旦は append*1/split と添字でのアクセスと bisect*2 ができる列としての B-tree です。セグ木のような区間 fold 演算ができた方がいいのかもという気持ちもあります。 一応実…

導入 配列 $a = (a_0, a_1, \dots, a_{n-1})$ に対して適当な区間 $[l\lldot r)$ が与えられて、そこでの平均値 $f_a(l, r) = \tfrac1{r-l}\sum_{i=l}^{r-1} a_i$ を考えます。 たとえば $[l\lldot r)$ がたくさん与えられて平均値を求めるだけなら、累積和…

ポインタ系データ構造（未定義お気持ち用語）を書きましょう。 まえがき やりたいね 基礎パート ツールの紹介 練習パート 実践パート データ構造に関して補足 勉強パート あとがき おわり まえがき ここでポインタ系データ構造と呼んでいるのは、配列や二分…

これいる？ 背景 本題 ビット並列 サブルーチン メイン 実装 サイズに関して 実測 雑記 あとがき おわり 背景 定数時間 rank/select をできる簡潔データ構造を作るときの基本戦略として、表引き (table lookup) というのがあります。 小さいサイズ（たとえば…

お近づきになりたい人向けシリーズです。 いろいろなトピックを詰め込みましたが、「これら全部を知らないといけない」のようなつもりではなく、いろいろなことを知るきっかけになったらいいなという気持ちなので、あまり身構えずにちょっとずつ読んでもらえ…