noshi91のメモ
概要 要素の集合を つに分割することを 回行って、どの 要素もどこかで分離されているようにすることができる。 向きの付いた分割についても同様の問題を考え、それぞれの構成法と最適性を示す。 向きの無い分割 問題例 無向グラフ があり、各辺には正の重みが付いているとする。 が与えられるので、 の条件下で 間の距離の最小値を求めよ。 解法 この問題は Dijkstra 法に少し手を加えると で解くことができるが、ここではその解法は思い浮かばなかったことにする。 を始点とする Dijkstra 法を行うと、どの に対しても への距離は となってしまうため上手く行かない。 そこで を取り、 を始点とし を終点とする距離を求める。 もし最適な が によって分離されているなら、すなわち を満たすなら、これで最適値が得られる。 を一様ランダムにとれば の確率でこれは達成されるが、決定性アルゴリズムを得たい
代数的構造を乗せるデータ構造の設計について - noshi91のメモ
概要 SegmentTree などのように、代数的構造 (特にモノイド) を乗せるデータ構造は多い。 この部分の設計は様々だが、「静的メンバを実装した型を受け取る」設計を他の設計と比較する。 設計のバリエーション A: std::function で関数オブジェクトを持つ template <class T> class segment_tree { std::function<T(T, T)> op; T id; }; B: 関数オブジェクトをそのまま持つ template <class T, class F> class segment_tree { F op; T id; }; C: 演算子がオーバーロードされた型を受け取る struct add { int val; add operator+(add r) { return add(val + r.val); } add() :
計算量について、償却/期待/平均など - noshi91のメモ
本記事は皆様からのご指摘を募集しております 誤った記述があるかもしれません 概要 競技プログラミングをやっていると などの表記を見掛けることも多いでしょう *1。 それぞれについて、大雑把な意味をまとめました。 アルゴリズムの挙動の正確な把握は競技においても重要です。 以降、全て時間計算量に付いて議論します。 注: 本稿内で用いられる はほとんどが に置き換えられますが、 Big O notation と同時に説明すると混乱を招くと判断し、競技プログラミングにおいて常用されている を使用しています。 最良計算量 多くのアルゴリズムは、入力によって計算量が変化します *2。 例えば、ソートアルゴリズムには大まかに 通りの入力が存在します。 あり得る全ての入力のうちの計算量の最小値を最良計算量と呼び、 を付けて表記します。 線形探索は (最初に求める値が存在した場合) マージソートは 挿入ソー
競プロで使うビットベクトル - noshi91のメモ
はじめに JOIの春合宿で簡潔データ構造の講義があり、競プロ界隈でも簡潔データ構造の機運が高まっているため(本当か？)、競プロで便利なビットベクトルの実装について書きます。 本記事で紹介する実装では、以下の性能を実現します。 bit列の長さをNとしたとき 空間 ：6*N bit 構築 ：O(N) access：O(1) rank ：O(loglogN) select ：O(loglogN) 簡潔(N+o(N)bit)を諦めた理由として以下が挙げられます。 １．実装が重くなる ２．空間の定数倍がきついので、10^5程度だと言うほど省メモリでない ３．時間の定数倍が重い この記事ではcompactで効率の良い構造を目指します。 selectについて実用レベルな定数時間の実装が難しかったためO(loglogN)で妥協しましたが、上手い実装を知っている方がいらっしゃったら教えて
k 値数列の転倒数 - noshi91のメモ
2019/04/20 実装の誤りなどを修正しました。 2021/02/18 説明を大幅に変更しました。 概要 qiita.com こちらの記事を読んで 値だけでなく一般の 値について拡張できそうだと思ったので、それを書きます。 値転倒数が伴う群 \begin{align} G &= \mathbb{Z}^k \times \mathbb{Z} \\ (s_l, t_l) \cdot (s_r, t_r) &= (s, t) \\ s_i &= (s_l)_i + (s_r)_i \\ t &= t_l + t_r + \sum_{i > j} (s_l)_i (s_r)_j \end{align} このように定義すると、 は群になります。 \begin{align} S &= \lbrace 0, 1, \cdots, k - 1 \rbrace \end{align} とすると、自由モノ
WaveletMatrix で快適な整数列ライフを送ろう - noshi91のメモ
この記事は内容に様々な問題があったので、削除されました。 Wavelet Matrix については下記のページを参照してください。 Wavelet Matrix - data-structures
Splay Tree で三分探索木を組む - noshi91のメモ
はじめに 最近競技プログラマーの間で Splay Tree のブームが来ているらしいので、それに乗っかり記事を書くことにしました。 Splay Tree は直近にアクセスした値への再アクセスが高速であったり、自己組織化する動的木にも使用されていたりと大変興味深い平衡二分探索木です。 本記事では三分探索木を Splay Tree を用いて実装します。 以下、与えられるキーの文字の種類を σ、文字列長を M、要素数を N とし、各文字は定数時間で大小比較が可能とします。 三分探索木とは Trie において、次の文字を二分探索木で管理したものです。 これにより各ノードは二分探索木の左子/右子と Trie としての次の文字を指す子を持つことになり、三分探索木と呼ばれる所以となっています。 クエリの時間計算量はどうなるでしょうか？ 各二分木を平衡二分木のように平衡させれば、O(Mlog(min(σ,
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
