noshi91のメモ

データ構造のある風景

単純な最小カットで表現できる条件

アルゴリズム

変数 x , y への 0 , 1 の割り当てに対してコストが以下の図のようになるとします。

f:id:noshi91:20191220161354j:plain

コストを最小化するとき、 A + D \le B + C ならば最小カットで表現できます。

説明

最小カットで使えるプリミティブな操作を考えます

f:id:noshi91:20191220222121j:plain

また、解に直接値を加えることで全体に +c,-c することが出来ます。
量 A+D-B-C を考えると、 x \rightarrow y , y \rightarrow x の辺で減少し、それ以外では変化しません。 よってこれらの辺で表現できる必要条件 A + D \le B + C が得られます。 一方これが実際に構築可能であることもすぐに示せます。

変数の反転

一方の変数を反転することを考えると不等号が逆のものが表現できます。 よってそのままでは表現できなくても、変数をいくらか反転すると表現可能となる可能性があります。

  • A + D \lt B + C
    x , y の反転は一致する必要があります
  • A + D = B + C
    反転の有無に関係なく表現可能です
  • A + D \gt B + C
    x , y の反転が異なる必要があります

yukicoder 957 植林

行と列が変数です。その列/行一帯を植林することを 1 とします。 すると 2 変数が関わり合う部分のコストは以下のようになります。

f:id:noshi91:20191220184226j:plain

行か列のいずれかを植えることにしたらそのマスは費用を払う必要がある、という意味です。 これは A + D \le B + C を満たすことが G_{i,j} \geq 0 から分かり、表現可能です。

(計算量 k 倍) 上位 k 個を取得する Li Chao Tree

データ構造

概要

  • Li Chao Tree で小さいほうから k 個取得できる
  • ただし取り出した k 個の順番は保証されない
  • 空間計算量 \Theta ( k n )
  • 時間計算量 \Theta ( k \log ( n ) ) per query


アルゴリズム

全てのノードは高々 2 k - 1 個の直線を保持します。 元の Li Chao Tree と同様、クエリの点を覆うノードの直線だけでクエリが処理できる状態を維持します。

追加

ノードに直線を追加することを考えます。 元々入っていた直線が 2 k - 1 本未満なら、ただ追加して終わります。 そうでない場合、新しい直線と合わせて 2 k 本の直線があります。 これらのうち、ノードの中央の点での値が最も大きいものを l とします。
l と他の直線を比較すると、 l は左と右の少なくとも一方の区間では完全に大きいです。 l 以外に 2 k - 1 個の直線があるため、左と右のどちらかでは k 個以上の直線に対して l は大きくなります。 よってそちら側の区間で l は上位 k 個になり得ず、反対側の区間へ再帰的に l を追加すればよいです。

f:id:noshi91:20191211210528j:plain

取得

クエリの点を覆う全てのノードの直線を列挙した後、選択アルゴリズムで上位 k 個を取り出します。

木の平方分割、出来るもの出来ないもの

アルゴリズム

出来ない分割の例

  • 木に対して、頂点集合を V _ 0, V _ 1, \ldots V _ {k - 1} に分割する
    • V _ i がつながっている: V _ i 内の任意の頂点対のパスは V _ i に含まれる
    • | V _ i | が小さい: | V _ i | \in O ( \sqrt N )
    • k が小さい: k \in O ( \sqrt N )
    • 反例: スターグラフ


出来る分割の例

  • 根付き木に対して、頂点集合を V _ 0, V _ 1, \ldots V _ {k - 1} に分割する

    • V _ i がつながっている: V _ i 内の任意の頂点対のパスは V _ i に含まれる
    • | V _ i | が小さい: | V _ i | \in O ( \sqrt N )
    • 深さが小さい: 任意の頂点について根からのパスは O ( \sqrt N ) 個の V _ i によって被覆される

  • 木に対して、辺集合を E _ 0, E _ 1, \ldots E _ {k - 1} に分割する

    • E _ i がつながっている: E _ i の端点として現れる任意の頂点対のパスは E _ i に含まれる
    • | E _ i | が小さい: | E _ i | \in O ( \sqrt N )
    • k が小さい: k \in O ( \sqrt N )

  • 次数の最大値が d の木に対して、頂点集合を V _ 0, V _ 1, \ldots V _ {k - 1} に分割する

    • V _ i がつながっている: V _ i 内の任意の頂点対のパスは V _ i に含まれる
    • | V _ i | が小さい: | V _ i | \in O ( \sqrt {d N} )
    • k が小さい: k \in O ( \sqrt {d N} )
    • d が小さい木の例: 二分木 ( d \leq 3)


誤りの指摘や有用な例の追加を募集しています。

バグ記録

全般

  • オーバーフロー
  • 降順ループを昇順にする
  • 入力の縦横を間違える
  • 早期 return の return 忘れ
  • コピペの添え字間違い
  • 値の初期化忘れ
  • H と W を間違える
  • return を書き忘れる
  • 順列の逆写像を出力している

インタラクティブ

  • 要素数 2N を N と勘違いする
  • 0/1-indexed の変換忘れ

mod 逆元と拡張ユークリッド互除法

アルゴリズム

概要

本稿では整数の \bmod M での逆元について取り扱います。
文中の合同式は \bmod M です。

  • 拡張ユークリッド互除法で逆元を求める
  • 互除法の手順を高速化できるかもしれないという提案
  • 1 から N の逆元を \Theta ( N ) で計算する
  • N 個の数について全ての逆元を \Theta ( N + \log M ) で計算する (おまけ)


拡張ユークリッド互除法で逆元を求める

a の逆元を計算します。 以下の形の合同式を考えます。
s \equiv ta
もし s = 1 なら t が求める逆元となります。

ここで、明らかな合同式として以下の 2 つがあります。
M \equiv 0a
a \equiv 1a
この 2 式を足し引きすると、新たな合同式が得られます。 例えば
M - 2a \equiv (0 - 2)a
などです。 よって、 M と a でユークリッドの互除法を行い t も同時に管理すると、 s = 1 となり逆元が求まります。

例 : M = 7 , a = 5
7 \equiv 0 * 5 \qquad \cdots ①
5 \equiv 1 * 5 \qquad \cdots ②
2 \equiv 6 * 5 \qquad ( ① - ② ) \qquad \cdots ③
1 \equiv 3 * 5 \qquad (② - 2 * ③)
\therefore 5 ^{-1} \equiv 3


互除法のショートカット

s \equiv ta について、 s の逆元 s ^ {-1} が既に分かっていたとします。 すると両辺に s ^ {-1} を掛けることで 1 \equiv ( s ^ {-1} t ) a となり、 a の逆元が得られます。
普通は s = 1 となったときに互除法を停止しますが、例えば 1 から N までの逆元を前計算していた場合、 s \le N となった時点で終了できることになります。 s はおおまかに指数的に減少するため、 N = \lceil \sqrt M \rceil まで計算しておけば逆元が 2 倍速程度になることが見込めるかもしれません。


1 から N までの逆元を \Theta ( N ) で計算する

互除法を 1 手順だけ進めたときを考えてみます。
M \equiv 0a
a \equiv 1a
\displaystyle M \bmod a \equiv - \lfloor \frac M a \rfloor a
前述したように、もし ( M \bmod a ) ^ {-1} が計算済であれば \Theta ( 1 ) で逆元が得られます。 ここで M \bmod a \lt a であるため、 a の昇順に逆元を計算することでこれは達成できます。 よって全体で \Theta ( N ) の時間計算量となります。


N 個の数について全ての逆元を \Theta ( N + \log M ) で計算する

数列 a _ 0 \ldots a _ { N - 1 } のそれぞれについて逆元を計算します。
先頭からの累積積 p _ i := \prod _ { k \lt i } { a _ k } と末尾からの累積積 s _ i := \prod _ {i \lt k} {a _ k} を \Theta ( N ) で計算します。
次に、全要素の逆元の積 c := \prod {a _ i ^ {-1}} を p _ N ^ {-1} によって \Theta ( \log M ) で計算します。
すると、 a _ i ^ {-1} = c p _ i s _ i によって \Theta ( 1 ) でそれぞれの逆元を計算可能です。

スライド最小値を半群に一般化する

データ構造

概要

以前記事を書いたのですが消したので別の場所にもう一度書きました。 今度はある程度まともな実装付きです (その分遅いですが)。

Sliding Window Aggregation - data-structures



計算量解析

Queue の場合

ポテンシャル関数を \lbrace 末尾側の \ \rm stack \ の要素数 \rbrace で定義します。

Deque の場合

ポテンシャル関数を \rm abs ( \lbrace 先頭側の \ \rm stack \ の要素数 \rbrace - \lbrace 末尾側の \ \rm stack \ の要素数 \rbrace ) で定義します

計算量について、償却/期待/平均など

アルゴリズム

本記事は皆様からのご指摘を募集しております

誤った記述があるかもしれません

概要

競技プログラミングをやっていると {\rm average} \ \mathrm{O} ( N ) などの表記を見掛けることも多いでしょう *1。 {\rm best} , {\rm worst} , {\rm average} , {\rm expected} , {\rm amortized} それぞれについて、大雑把な意味をまとめました。 アルゴリズムの挙動の正確な把握は競技においても重要です。
以降、全て時間計算量に付いて議論します。

注: 本稿内で用いられる \mathrm{O} はほとんどが \Theta に置き換えられますが、 Big O notation と同時に説明すると混乱を招くと判断し、競技プログラミングにおいて常用されている \mathrm{O} を使用しています。


\rm best : 最良計算量

多くのアルゴリズムは、入力によって計算量が変化します *2。 例えば、ソートアルゴリズムには大まかに N! 通りの入力が存在します。 あり得る全ての入力のうちの計算量の最小値を最良計算量と呼び、 \rm best を付けて表記します。

  • 線形探索は {\rm best} \ \mathrm{O} ( 1 ) (最初に求める値が存在した場合)
  • マージソートは {\rm best} \ \mathrm{O} ( N \log N )
  • 挿入ソートは {\rm best} \ \mathrm{O} ( N ) (実装次第)

例えば、ほとんどのソートアルゴリズムは最初に列がソート済かを調べることで {\rm best} \ \mathrm{O} ( N ) に改善できるでしょう。 (そのような改善をして嬉しいかどうかは別の話ですが。)


\rm worst : 最悪計算量

最小値を取った最良計算量に対して、最大値を最悪計算量と呼び、 \rm worst を付けて表記します。

最悪計算量は強い保証であり、最悪計算量でアルゴリズムを見積もれば想定外に時間がかかることはありません。 競技プログラミングはどのようなテストケースがあるか分からないため、最悪計算量が重要となることが多いです。 特に何も書かない場合、暗黙に最悪計算量を指すことがあります。(文脈に依存します)


\rm average : 平均計算量

全ての入力に対しての平均を平均計算量と呼び、 \rm average を付けて表記します。

平均的に高速なアルゴリズムは、最悪計算量が悪くても実用的な場合があります。 競技プログラミングで平均計算量を信用することは必ずしも得策ではありませんが、「テストケースがランダムに生成されている」場合解法を平均計算量で評価することが可能です。 逆に writer に想定されていると、平均計算量のよいアルゴリズムも最悪計算量が悪いと落とされてしまいます。


\rm expected : 期待計算量

アルゴリズムの中には、実行時に乱数を生成し、乱数の出目次第で計算量が変化するアルゴリズムがあります。 このとき、計算量の期待値 (平均値) を期待計算量と呼び、 \rm expected を付けて表記します。 平均を取るという点で平均計算量と似ているように見えますが、異なる概念です。

平均計算量との違いは、平均を取る対象が入力全体か、乱数全体かという点です。 入力はしばしばランダムではないですが、乱数は常にそのランダム性が保証されています *4。 よって競技プログラミング的視点では「平均計算量は hack 可能」「期待計算量は hack 不可能 *5」という特徴があります。 ピボットをランダムに選ぶことで、クイックソートが期待計算量に改善されている点は興味深いと言えるでしょう。


\rm amortized : 償却計算量

償却計算量とはならし計算量とも呼び、データ構造のように複数の操作を繰り返し行う場合に操作一回を解析する概念です。
例として動的配列 *6 に要素の追加を繰り返し行った際の挙動を考えてみましょう。 容量が限界に達したら \mathrm{O} ( N ) 掛けて倍の大きさのメモリを確保し、全ての要素を移動させます。 拡張のタイミングの操作は当然 \mathrm{O} ( N ) の計算量が掛かります。 しかしこのような「重い」操作は滅多に起こらず、実際には一操作辺り平均して \mathrm{O} ( 1 ) の計算量しか掛かっていません。
この「平均すると速い」は平均計算量や期待計算量に近い性質ですが、どのような入力でも大丈夫ですし、運の良し悪しにも左右されません。 償却計算量はこのようなアルゴリズムを評価することに向いています。
(データ構造が空の状態から) N 回の操作を行った際の計算量が f( N ) であるとき、一操作辺りの償却計算量は {\rm amortized} \ \frac{f( N )}{N} となります。

  • 動的配列への要素の追加は {\rm amortized} \ \mathrm{O} ( 1 )
  • splay tree の各種操作は {\rm amortized} \ \mathrm{O} ( \log N )

償却計算量は期待計算量と同様、競プロで信頼できる計算量評価の一つです。 最悪計算量は悪いが償却計算量は良いようなデータ構造には、最悪計算量が同程度のものより簡潔、高速である場合があり注目に値します。

2021/12/19 追記

上記の定義は不完全で、不都合なことが多いと感じます。 償却計算量について厳密に定義した文献を見つけられていませんが、私の経験上以下のような定義だと多くのケースで整合すると思われるものを紹介します。

データ構造に対して、起こり得る操作全体を M とする。 操作の償却計算量が (A _ m) _ {m \in M} であるとは、任意の操作列 (m _ i) _ {i = 1} ^ {n} に対して

\begin{align} \text{操作列} (m _ i) _ {i = 1} ^ {n} \text{を実行する実際の計算量} \leq \sum _ {i = 1} ^ {n} A _ {m _ i} \end{align}

が成り立つことと定義する。 ここで、操作列 (m _ i) _ {i = 1} ^ {n} は「何もない」状態から始まるもののみを指す。 つまり、最初の操作 m _ 1 は「空の heap を作る」や「与えられた列から、segment tree を構築する」などになる。 (この条件が無いと、重い操作 1 つからなる列の計算量が壊れてしまう)

(2021/12/19 追記終わり)


余談

期待計算量や償却計算量は最良/最悪/平均計算量と同時に存在しうる概念だと思うのですが、厳密な定義や使用例が発見できなかったので詳しく書くことは控えました。 ご存知の方がいらっしゃいましたら教えて頂けると嬉しいです (記事の誤りなども)。

*1: \rm expected などの修飾を計算量の前と後のどちらに付けるかはどちらの例も見られよくわからなかったため、前で統一しています

*2: \mathrm{O} 記法を用いるのは「計算量のオーダー」であって、「計算量」は計算回数を指すことに注意してください

*3:一部のハッシュテーブルは \rm worst で保証する

*4:現実的には疑似乱数ですが、実用的には十分にランダムです

*5:乱数の seed を hack する場合は別

*6:C++ ならば std::vector