#procon31 非公式競技部門に参加しました

はじめに

12/19に開催された第31回全国高等専門学校プログラミングコンテスト非公式競技部門に参加してきました。

ルール

  • 基本的には去年と同じルール
  • 囲んだ領域マスは消えない(囲みが消えても領域マスは保持される)
  • 領域は4近傍で囲まれている必要がある

方針

  • 各エージェント毎に多様性を持たせてビームサーチしてから、焼きなましで経路の組み合わせを検索
  • 評価関数は得点、領域、エージェント間の距離、経路のコンフリクト度合いなどに対して適当に係数をかけたりする
  • ハイパーパラメータはoptunaで最適化

実装

Rustで実装しました。GUIにはdruidを使って、APIJSON周りはserde-jsonreqwestを利用しています。
リポジトリこちらです。

できなかった事

  • 並列化
  • 情報の自動取得や自動送信
  • 特定の盤面に対する対応
  • 相手の領域を予測した除去
  • 相手の行動を考慮に入れた評価関数の設計

反省

  • 本番のコードに対するバグが多すぎた(当日になって解決するケースが多かった)
  • 準備期間が不足していた
  • ルールの誤読が複数あって、片方は当日朝、もう片方は本番で気づいた (エージェント配置でタイルが変わらない事、囲みが4近傍になっている事)
  • アルゴリズムがランダム配置のマップ前提の物になっていて、人工ケースで動かす時に問題が多かった

おわりに

ちゃんとルール理解していたり本番にバグがなければもう少しいい成績が取れていたと思うのでかなしい
骨組みを前もって作っておいたとはいえ、アルゴや通信部分等を3日で完成させられたのは良かったと思う

このような環境を用意して頂いた運営のみなさんに、感謝・・・

食事最適化入門 美味しい完全食

はじめに

健康的な人間になるためにはバランスの取れた食事が必要です。

しかし、食事には時間がかかり、かなり辛いです。
栄養を摂取するためだけの食事に長時間かけるのは、非本質の経路復元が実装時間の8割を占めるICPCの実装問ぐらい不毛です。(まぁICPCエアプなのでそんな感じの問題があるかどうか知らないんですけど)

そのため、手早く食べられて栄養満点な食事が必要とされています。


本題


これ、めっちゃうまい

f:id:shibh308:20201204231046j:plain
うまい!

basefood.co.jp

Suffix Treeで解ける有名っぽい問題

はじめに

Suffix Treeで解ける有名っぽい問題(Gusfield本に載ってるやつ)の中で競プロで使う事がありそうなものの解法をまとめる 記法とか定義とかがものすごくガバガバなのは許してください

定義

以下を適当に定義する

  • 文字について

    • $\$$ と $\$_i (1 \leq i)$ を区切り文字とし、入力で与えられていないような入力中のどの文字よりも辞書順で小さい文字とする
  • 文字列 $S$ について

    • $S[i, j]$ を $S$ の $i$ 文字目から $j$ 文字目までの文字列とする ($i > j$ なら $S[i, j]$ は空文字列)
  • Suffix Tree, Generalized Suffix Tree中のノード $v$ について

    • 根と $v$ のパスが表す文字列を ${\rm str} (v)$ とする

    • ${\rm depth} (v) = |{\rm str} (v)|$ とする

  • Suffix Arrayについて

    • ${\rm SA}_S$ を $S\$$ のSuffix Arrayとする(特に区別する必要がなければ ${\rm SA} _ S = {\rm SA }$ と省略して表記する)
  • Suffix Treeについて

    • ${\rm ST} (S)$ を $S\$$ を表現するSuffix Treeとする
  • Suffix Tree中のノード $v$ について

    • ${\rm str} (v) = S[i, i + {\rm depth} (v)]$ であるような適当な $i$ に対して、 ${\rm pos} (v) = i$ とする
  • Generalized Suffix Treeについて

    • ${\rm GST} (\mathcal{S})$ を $ S_1 \$_1 S_2 \$_2 \dots S_{|\mathcal{S}|} \$_{|\mathcal{S}|}$ を表現するGeneralized Suffix Treeとする
  • Generalized Suffix Tree中のノード $v$ について

    • ${\rm str} (v) = S_i[j, j + {\rm depth} (v)]$ であるような適当な $i, j$ に対して、 ${\rm label} (v) = i, {\rm pos} (v) = j$ とする

問題

Maximal repeats

定義

  • 文字列 $T$ と$1 \leq i \leq j \leq |S|$ に対し $T[i,j] = T[i',j'] ,\ T[i-1,j] \neq T[i'-1,j'] ,\ T[i,j+1] \neq T[i',j'+1], (i, j) \neq (i', j')$ を満たす $(i', j')$ が存在する場合、 $(i, j)$ を $T$ の maximal repeatと定義する

問題概要

  • 文字列 $S$ が与えられる

  • $S$ の全てのmaximal repeat $(i, j)$ についての $S[i, j]$ の集合 $\mathcal{S}$ を求める

  • 文字列を出力すると出力サイズが $ \Theta ( |S| ^ 2 )$ になる事があるため、 $S[l,r] \in \mathcal{S}$ であるような $(l, r)$ の集合の形で表す

解法

  • ${\rm ST} (S)$ の内部節点を全て見る

  • 内部節点 $v$ の子孫であり ${\rm pos} (u) = k$ であるような葉 $u$ について $S_{k - 1}$ を調べ、これが全て一致していなければ $(k, k + {\rm depth} (v))$ はmaximal repeatになる

  • 子孫となる葉の集合は $\rm SA$ 中の区間になるため、$V [i] = S_{{\rm SA} [i] -1}$ であるような配列 $V$ 中で種類数が$1$になる区間を前計算しておけば解ける

  • 列挙する際は全ての $v$ に対して適当な $u$ を選んで $(k, k + {\rm depth} (v))$ を報告すればよい

Supermaximal repeats

定義

  • $(i, j)$ が文字列 $T$ のmaximal repeatであり、 $(i, j) \neq (i', j')$ である任意の $T$ のmaximal repeat $(i', j')$ と非負整数 $l, r$ に対して $(i'+l, j'-r) \neq (i, j)$ が成り立つ時、$(i, j)$ を $T$ のsupermaximal repeatと定義する

問題概要

  • 文字列 $S$ が与えられる

  • $S$ の全てのsupermaximal repeat $(i, j)$ についての $S[i, j]$ の集合 $\mathcal{S}$ を求める

  • maximal repeat と同様、$( l, r )$ の集合の形で表す

解法

  • maximal repeatと同様に ${\rm ST} (S)$ を考える

  • 子が全て葉である内部節点 $v$ の子で ${\rm pos} (u) = k$ であるような葉 $u$ について $ S _ { k - 1 } $ が全て異なっているならば $(k, k + {\rm depth} (v))$ はsupermaximal repeatになるため、それを報告すればよい

  • $S_ { k - 1 } $ が全て異なるような区間はしゃくとり法で前計算できる

Longest common substring

定義

  • 文字列集合 $\mathcal{S} = \{ S_1, S_2, \dots S_m \}$ に対して、$S_i[l_i, r_i] = T$ であるような $(l_i, r_i) \ (1 \leq l_i \leq r_i \leq |S_i|)$ が存在するような $S_i$ の個数が $k$ 以上である時、文字列 $T$ を $\mathcal{S}$ の種類数 $k$ のlongest common substringと定義する

問題概要

  • 文字列集合 $\mathcal{S}$ が与えられる

  • $1 \leq k \leq |\mathcal{S}|$ を満たす全ての $k$ に対して種類数 $k$ のlongest common substringの最大の長さを求める

解法

  • ${\rm GST} (\mathcal{S})$ を構築する

  • 内部節点 $v$ の子孫であるようなノード $u$ についての ${\rm label} (u)$ の集合を求め、集合の要素数が $k$ 以上である時、${\rm str} (v)$ は種類数 $k$ のlongest common substringである

  • これはmaximal repeatと同様に区間種類数になって、解ける

All-pairs suffix-prefix matching

定義

  • 文字列の組 $(S, T)$ に対して $S[1, k] = T[|T| + 1 - k, |T|]$ を満たす最大の $k\ (0 \leq k \leq {\rm min} (|S|, |T|))$ をsuffix-prefix matchingと定義する

問題概要

  • $ M $ 個の文字列からなる文字列集合 $\mathcal{S}$ が与えられる

  • $1 \leq i , j \leq M $ を満たす全ての $(i, j)$ の組について、$(S_i, S_j)$ のsuffix-prefix matchingを求める

解法

  • ${\rm GST} (\mathcal{S})$ を構築する

  • ノード $v$ の子にラベル $\$_k$ の辺が存在する時、ノード $v$ をk-terminateと呼ぶ

  • ${\rm str} (v) = S_i[1, k]\ (1 \leq k \leq |S_i|)$ であるノード $v$ がj-terminateである時、$(S_i, S_j)$ のsuffix-prefix matchingは $k$ 以上になる

  • stackを $|\mathcal{S}|$ 個管理してDFSをする 今見ているノード $v$ がj-terminateである場合、 $j$ 個目のstackに ${\rm depth} (v)$ をpushする(探索終了時にpopする)

  • ${\rm label} = i, {\rm pos} = 1$ であるようなノードに到達した時に、$1 \leq j \leq |\mathcal{S}|$ を満たす全ての $j$ に対して $j$ 番目のstackのtopを確認すればいい

ライブラリ(ほぼ)全解説

はじめに

2020/09/14時点での僕の所持しているライブラリを(一部を除いて)解説していきます
各題目をクリックするとライブラリの該当ページに飛べるので、興味があればどうぞ(verify以上の動作保証はしません)

ライブラリ

avl

  • 遅延評価のないinsert/eraseベースのAVL
  • ノード管理はnewで行う
  • rotate関連をtemplateでやってる事ぐらいしか書くことがない

avl_map

  • std::mapと同じ役割を持つAVL
  • ノード管理は配列+index
  • メモリ使用量が少なく、軽い

binaryindexedtree

  • BIT
  • 特に言うことなし

binarylifting

  • 木のダブリング
  • LCAを返してくれるので、HLDを使うほどではない時に貼ったりする

bitvector

  • conpactなbitvector
  • access/rankのみ
  • waveletmatrixの内部で使う用

compression

  • 座標圧縮
  • 割と使うけど面倒でverifyしていない

convexhulltrick

  • CHT
  • 単調性などを問わず、だいたいの操作にlogNかける実装

dinic

  • 最大流
  • 特に書く事がない

disjointsparsetable

  • Disjoint Sparse Table
  • 脳死で累積和の代わりに貼る事がある

dynamicbitvector

  • 動的なビットベクトル
  • 葉にboolを32個ぐらい詰め込む典型テクをしているのでメモリに優しい
  • バグってる可能性あり

dynamiclazysegmenttree

  • 必要な時にノードを作る遅延セグ木
  • BBSTでいいので使わない

dynamicsegmenttree

  • 必要な時にノードを作るセグ木
  • BBSTでいいので使わない

dynamicwaveletmatrix

  • 動的WaveletMatrix
  • 計算量が重く、メモリも辛い
  • 実装でどこかバグってるらしい
  • 怖いので使いたくないし書き直したくない

eertree

  • eerTree
  • 回文関連がだいたいこれで殴れる

eulertour

  • 前処理を線形時間で行って部分木判定をするやつ
  • オイラーツアーって名前がかなり良くない
  • 使った記憶がない

hashmap

  • 自前ハッシュマップ
  • 速いので時々使う

heavylightdecomposition

  • HLD (heavy path decompositionと書いた方がいい?)
  • よく使う
  • vector<pair<int,int>>のペアで区間を返して、非可換クエリにも対応する

lazysegtree

  • 抽象化がされている遅延セグ木
  • よくある典型的な非再帰実装

lazyskiplist

  • 区間加算などが可能なスキップリスト
  • 挿入削除区間和等、だいたい平衡二分木と同じ操作が可能
  • 定数倍が重くてかなり使いづらい(BBSTの方がよい)

lineartimesparsetable

  • 線形時間構築のSparseTable
  • 線形時間だと言い張るためにこういうデータ構造をよく使う事がある

lowlink

  • 橋と関節点の列挙

matrix

  • 行列ライブラリ
  • あまり機能が多くない、行列累乗に使えるのでまぁこれでも十分

memorypool

  • メモリプール
  • ノード確保をstatic配列にしたりglobalに書いたりするのが嫌なので書いた
  • __buitin_clzでアクセスしてるのがアホでかなり遅い
  • 使う時毎回書き換えてる、いつか消したい負債

mo

  • Mo's algorithm
  • バグらせやすいのであると便利(後述するmo_queryと組み合わせる)

mo_query

  • クエリ情報を渡すとMo's algorithmを走らせてくれる
  • 全クエリ情報がまとめて手に入って便利
  • インターフェースが使いやすくかなり気に入ってる

modint

  • 普通のModInt
  • 逆元やべき乗は別ライブラリに投げてる

persistentdynamiclazysegmenttree

  • 永続動的遅延伝播セグメント木
  • だいたいの場合永続遅延伝播赤黒木でなんとかなるので使わない

persistentunionfind

  • 部分永続UF
  • あまり使わない

primaldual

  • 最小費用流
  • ときどき使う事がある

redblacktree

  • 普通の赤黒木
  • ノード管理はmemorypool(後述する赤黒系は全てそう)
  • merge/splitベース
  • ランダムアクセス、区間和等 よくあるクエリは捌ける

redblacktree_lazy

  • 遅延伝播赤黒木
  • 普通に使う(memorypoolのせいでちょっと遅いので使う時は適宜修正する)

redblacktree_persistent

  • 永続赤黒木
  • コピー&ペースト、PCK20予選10等 持っていて損はない
  • 人々が思ってるより実装が軽い おすすめ

redblacktree_persistent_lazy

  • 永続遅延伝播赤黒木
  • グラフではないを解くのに使える

redblacktree_sset

  • std::setの機能の赤黒木
  • ランダムアクセス付きsetとして使う

rerooting

  • 全方位木DP
  • 気づいたら使い方が分からなくなっていた

rollinghash

  • ロリハ
  • 109+7,109+9をmodにする事が多い
  • まだ実戦で落ちた経験はないのでこのまま使うと思う

scc

  • 強連結成分分解
  • PCKとかICPC系で使う印象

scc_dag

  • sccをしてからdagへの変換までやってくれる
  • 返ってくる構造体が親切で使いやすいと思ってる

segmentset

  • 区間をsetで管理するやつ
  • 使う頻度が低いので毎回使用方法を忘れる

segmenttree

  • セグ木
  • よくある非再帰実装 特に言うことなし

skiplist

  • スキップリスト
  • 実は平衡二分木にできる操作がだいたいできる(あまり知られてない?)
  • 定数倍が遅い

skiplist_sset

  • スキップリストでのset実装
  • あえて使う事はない

sparsetable

  • 普通のSparseTable
  • まぁ時々使う(LCPのテーブルとかに使う事が多い気がする)

splaytree_sset

  • splay tree
  • 速いしインターフェースも分かりやすいので割と使う

substrmatching

  • SA-ISと文字列マッチングの詰め合わせ
  • 時々使うかも

suffixtree

  • SuffixTree+SA+ISA+LCPのいつものやつ
  • これがあればだいたい事足りると思う

treap

  • 普通のTreap
  • merge/splitベース
  • 最近はあまり使わない

trie

  • 普通のtrie
  • インターフェースがカスなので多分今後一度も使わない
  • 結局直書きする事になりがち

twothreetree

  • 2-3木
  • 場合分けがとても多くて実装が辛かった
  • 絶対使わない

twoedgeconnectedcomponents_tree

  • 二重辺連結成分分解をして木にしてくれる
  • 実装で困る事が多いのであると嬉しい

unionfind

  • UF
  • だいたいの機能が網羅されてる
  • よく使う

vanemdeboastree

  • vEB木 いわゆる謎木
  • 実装がシンプルで実際に速い
  • 空間計算量の都合で220ぐらいまでしか使えない

vanemdeboastree2

  • 子をhashmapで管理するvEB木
  • 実測でもsetより速い
  • 値域制約がないのでかなり実用性がある

wavletmatrix

  • succinctではないWaveletMatrix
  • いろいろ使えるし応用もできて好き

xfasttrie

  • x-fast trie
  • 使わない

xfastrie_yft

  • yftの土台用のx-fast trie
  • y-fast trieの土台以上の価値はない

yfasttrie

  • 乱数でBBSTに挿入するかを決めるy-fast trie
  • vEBより遅いので使わない

yfasttrie2

  • 一定サイズでBBSTのmerge/splitをするy-fast trie
  • 前者よりは速い
  • vEBより遅いので使わない

zdd

  • ZDD
  • 競プロで使わない事に気づいて整備をやめた

おわりに

整備しても一生使わないデータ構造が大変を占めていて、かなしくなった

昼食

昼食

 最近はよくBASE BREADを食べています 学内で食べる時は必ずこれです(週に3回ぐらい食べてる)

f:id:shibh308:20200710231932p:plain
完全パン

完全食

 完全食を食べると人間に必要な栄養素がほぼ全部摂取できて、完全になれます

種類

粉とかグミとかパンとかパスタとかいろいろあります

粉のやつ

 時短目的なのにシェイカーで混ぜる手間がかかるの、つらそう(完全食初心者)

グミのやつ

  • 食べる手間がかからない
  • 食べても眠くならない気がする

のでよさそうなんですけど、

  • ちょっと高い
  • 必要な摂取量が多い
  • めっちゃ硬い
  • あまりおいしくない(個人の感想)

のでちょっと微妙そう

パスタのやつ

 完全食なのに食べる手間がめっちゃかかるの、大変そう(エアプ)

パンのやつ

 すぐ食べられるので手軽度がめっちゃ高くて、そこそこ安い(一食400円で完全になれる)
二種類の味があって、チョコはチョコ風味でうれしい(プレーンの方はほぼ無味で自分の唾液がうまく感じる)
基本的に密度の高い雑穀パンみたいな感じで、食感は湿ったダンボールに近かったです。

それ以外

 知りません・・・

感想

 正直あまり美味しくないんですが、「これ食ってれば完全だし・・・」みたいな感じで食べられてうれしいです 一食がパン2個だけで済むので食事にかかる時間が減ってよかった

おすすめリンク

basefood.co.jp

継続購入初回は20%オフでいつでも解約/配達日時変更可能!

insert/erase/lowerbound とかが速いデータ構造

はじめに

 順序付き集合を管理するデータ構造はたくさんあってすごい 今回は非負整数の集合を扱えるデータ構造を(知ってるものだけ)まとめていきます

何がしたいのか

 非負整数を扱う集合に対して、  \rm insert, erase, lowerboundとかの操作をしたい
 普通の集合を管理するだけならだいたいHashSetでいいんだけど、 x以上最小の要素とかが知りたくなるとこれらを処理するデータ構造がないといけない

問題設定

・要素数 Nの集合 Sに対して上に書いたような操作をする

・全てのクエリで与えられる値は  0 \le x \lt 2^{w}を満たす

・速ければ速いほどうれしい

今回紹介するデータ構造

・Binary trie

・X-fast trie

・Y-fast trie

・van Emde Boas trees

Binary trie

 割とよく見るデータ構造 普通のtrie木を二分木で実装しただけだと要素検索しかできない(  \rm lowerboundができない)ので、ちょっと機能を追加する

 子へのポインタをstruct Node{Node* c[2];} みたいな感じに持つと思うんだけど、右側もしくは左側の子が存在しない場合(c[0]もしくはc[1]がnullを指す場合)には以下のように情報を持たせる事にする

・該当ノードが葉の場合はc[0]にprevを、c[1]にnextを保持する

・葉でなくてc[0]が空の場合、そのノードの部分木の中で一番左側の葉へのポインタを持つ

・葉でなくてc[1]が空の場合、そのノードの部分木の中で一番右側の葉へのポインタを持つ

f:id:shibh308:20200413225852p:plain
 S = {1,2,4,12,15}の時のBinary trie

  \rm lowerboundをする際は上図の黒色の矢印に沿って探索していき、葉まで辿りついた時点で終了 進みたい方向に子がない場合は代わりにショートカットを使って進む c[0]を使った場合は進んだ先が答えで、c[1]を使った場合は進んだ先のnextが答え

 こんな感じに実装をすると \rm insert, erase, lowerbound \rm O( w),\  \rm next, prev \rm O(1)で答えられて、うれしい

X-fast trie

 Binary trieで \rm lowerbound をする時に、「一定の深さまで潜っていって該当ノードが存在しなくなったらショートカットする」操作をしていた事を考える

 ある深さに探しているノードへの経路に含まれるノードが存在するかどうかは単調性があるので、どの深さで経路がなくなるかを二分探索できる 各深さごとにHashMapを持つとノードの存在判定が \rm expected\ O(1)でできる (検索が \rm expected\ O(1)のハッシュテーブルを使った場合)

 深さ wのBinary trieを深さで二分探索するので、 \rm lowerboundの期待計算量は\rm O(log w)になる  \rm insert,eraseなどの計算量はBinary trieから変わらない

Y-fast trie

 Y-fast trieでは平衡二分木とX-fast trieを組み合わせて爆速クエリ回答をする すごい

 X-fast trieの葉ノードに平衡二分木(Treapとか)を持たせる事にする X-fast trieにはだいたい {N}\over{w}個の葉を持たせるようにして、 N個の要素をそれぞれX-fast trieの葉の平衡二分木に入れる

 X-fast trieで管理している要素を小さい方から x_1, x_2, ..., x_mとした場合、 k番目の葉の平衡二分木には (x_{k-1}, x_k ] を満たす値を入れるようにする (  x_0 -1として、 x_mは常に  2^{w}-1とする)

f:id:shibh308:20200414230343p:plain
 [0,127]を管理するY-fast trieの図

 X-fast trie側で \rm lowerboundを呼べば探しているノードが存在する可能性がある平衡二分木が \rm O(log w)で分かるので、その中を調べる事で要素検索ができる (平衡二分木の大きさが \rm O( w)だと仮定すると、検索操作全体の計算量は \rm O(log w)となる )

  \rm insert, eraseも、X-fast trieの中身を変更しない限り \rm lowerboundと同じ計算量で操作ができる

 ただ、操作を続けていると平衡二分木が管理する要素の個数がめっちゃ大きくなって困るので、平衡二分木の大きさが 2wになった時点で大きさ wの平衡二分木2つに分割して、新しくできたノードをX-fast trieに追加するようにする こうする事で平衡二分木の大きさを \rm O( w)に抑える事ができる
X-fast trieへの要素挿入は \rm O( w)かかって一見ヤバそうなんだけど、分割が発生するためには最低 w 回の要素追加が必要だから償却計算量がいい感じになってうれしい

 X-fast trieの要素数をだいたい {N}\over{w}に保つ事ができればX-fast trie側の空間計算量は \rm O( N)で済む 平衡二分木の空間計算量は要素数に対して線形なので、空間計算量は全体で \rm O( N)になる(X-fast trieに番兵を置かない場合)

 平衡二分木のサイズが 2wを超えたり 1\over{4} wより小さくなった時点で \rm merge \rm splitをする方法の他に、 \rm insert の際に  1 \over {w}の確率でX-fast trieにも挿入するようにする事で大きさの期待値を \rm O( w)にする方法があるらしい(みんなのデータ構造ではこっちを使ってた)

van Emde Boas Trees

 vEB木とか謎木とか呼ばれてる謎のデータ構造 英語版のWikipedia擬似コードが載ってる事で有名

 平方分割を深くした感じの見た目をしていて、 1段目は  \rm 1bit分の情報を持つ葉  k段目  (k \geq 2) 2^{2^{k-2}} 個の子を持っている(子の数は  2,4,16,256,65536,...となる)  k段のvEB木は  2^{k-1} \rm bit分の情報を管理できる (木の深さが \rm O(log w)になる)

 各ノードは子の他に \rm max \rm minを保持していて、それに加えて  \rm min以外の存在している要素のインデックス を保持したノードを持つ(Wikipedia擬似コードだとauxって名前がついてた) また、現在ノードの \rm minとなっている値は子に含めないようにする

f:id:shibh308:20200414211731p:plain
 S = {0,1,2,4,5,8,11,12,13,14,15}の時のvEB木

  \rm lowerboundの時はBinary trieの時と同じように潜っていって、キーが対象ノードの \rm min以下の場合には \rm minを返して終了
対象ノードが存在しない場合 / キーが対象ノードの \rm maxよりも大きい場合 にはその次の兄弟ノードの \rm minを返す 次の兄弟ノードのindexはauxを対象にして \rm lowerboundをする事で取得できる
最悪の場合木の深さ分だけ再帰が行われるので、計算量は \rm O(log w)になる

  \rm insertの際は \rm minが未定義なノードまで潜っていって、途中で \rm maxが更新できるなら更新する  \rm minが更新できる場合は更新する代わりにキーと \rm minをswapするようにする(新しく \rm minとなるノードは子ノードを作る必要がなく、その代わりに以前の \rm minの子ノードを作る必要があるため)
最悪ケースでは葉にたどり着くまでこれを繰り返すため、計算量は \rm O(log w)になる

  \rm eraseの際は \rm min \rm maxが一致するか \rm min \rm maxが未定義な所まで潜っていく  \rm minが一致する時は 2番目に小さい値で更新する必要があるので、auxの \rm minを使ってindexを取得してから置き換える  \rm maxが一致した時も同様にauxを使って更新する
これも各深さに対して1度しか呼ばれないため、計算量は \rm O(log w)

 普通の実装だとコンストラクタで 2^{w}個ぐらいのノードを生成する事になってかなり使いづらいんだけど、必要になる時までノードを生成しないようにするとメモリ使用量が抑えられる(HashMapを使う事になるので定数倍がちょっと重い)

おわりに

 全部速いけど微妙にバグる

shibh308.github.io

スキップリストで区間を管理するやつ

はじめに

 スキップリストで区間の管理をする方法が載ってそうな記事があまりなかったので書きました(雑記事です)

できること

スキップリストは

とかができます。あと永続化もできるっぽいんですが僕はやってません・・・

スキップリスト自体の概要

 Wikipediaに載ってます

ランダムアクセスの方法

 Wikipediaに載ってます

区間管理の方法

 下のようなスキップリストに区間minの情報を持たせる事を考えます。

f:id:shibh308:20200406135001p:plain
スキップリストの例
 このリストからノード部分だけを切り出すとこんな感じにかけて、
f:id:shibh308:20200406135012p:plain
ノード部分を切り出したやつ
 空いてる部分を横に伸ばすとこんな感じになります。
f:id:shibh308:20200406135008p:plain
区間を持たせたやつ
 各ノードごとに下の段の値の最小値を持たせると、こうなります。
f:id:shibh308:20200406135005p:plain
区間minを持たせたやつ

 こうするとなんかセグメント木っぽく見えて、実際セグ木っぽい感じで下図のように区間取得ができます。

f:id:shibh308:20200406140506p:plain
区間 \rm [2, 7]を取得する例

 もう書く事がないのでこの話はここでおわりです・・・

実装

 実装を、しました・・・

提出コード(一点更新+区間min)

提出コード(一点更新+一次関数の合成)

提出コード(区間加算+区間min)

ライブラリ(区間和)

ライブラリ(区間加算)

なぜ広まってないの??????

・見た目に対して実装がダルい

・遅延伝播とかいろいろやるとかなりバグりやすい

・スキップリストに興味持つ人間のうち95割はすでに平衡二分木を持ってそう

・そもそも色々できる事が知られていない

 とかが理由なんじゃない?(適当)

おわり

 区間加算ができる事に気づいた時は絶対流行ると思ったんだけど、予想より実装が楽じゃなかったので微妙な気持ちになった・・・