同じ列にある つの式は、の元で同値です。
次の つの式が成立します。
同じ列にある つの式は、の元で同値です。
次の つの式が成立します。
逆元が必ずしもない状況で行列式を計算する方法を紹介します
n91lib_rs/division_free_determinant.rs at master · noshi91/n91lib_rs · GitHub
除算を使わない のシンプルなアルゴリズムが知られています。 除算無しでも になるらしいのですが、詳しく勉強してないので詳細は分かりません。
掃き出し法のアルゴリズムを少し変えるだけで高速に計算できます。 掃き出し法は「ある行を使って別の行の先頭要素を 0 にする」を繰り返すアルゴリズムなので、この部分を何とかできればいいです。 そこで、0 にしたい列の要素を一旦 ( ではなく) ただの数だと思って、ユークリッド互除法を行います。 ユークリッド互除法は定数倍と加減算なので、 でも問題なく計算できます。 これを繰り返せば のアルゴリズムが得られます。 を繰り返しとる操作は計算量が落ちるので、実際には になっています。
さらに計算量を落とすことも出来ます。 そもそもユークリッド互除法の部分は 2 要素間だけで計算できるので、最終的にどういう線形変換になったかだけを追って、最後に行ベクトル同士を足し引きすればよいです。 これにより となります。
ユークリッド互除法が行えるなら何でもいいので、多項式環などでも使うことが出来ます。
----------- 以下、yukicoder のネタバレを含みます ----------
yukicoder No.1303 Inconvenient Kingdom - ひとなので
この解法で掃き出し法が機能しているのは、元のグラフが連結なので行列式が 0 でない、などの性質を利用しています。 先ほども述べた通り多項式もユークリッド互除法が使えるので、それを用いれば ad-hoc な証明をしなくても AC を取ることが出来ます。
Poyashi で参加して 6 完 4 位でした
リハーサル参加のためかなり早めに来たが、模擬に参加してるのでほとんど練習の必要がないことに気付く。 ライブラリを書きながら開始を待つ。
記憶がかなり曖昧なので間違ってるかも。
A moyashi B pulmn C noshi で読む。 AB はすぐに解けるが C が普通に解けないので D を読んだら D も解けなくて困った。
moyashi pulmn に C を伝えるが解法が出ないため、ぶん回し覚悟で重いコードを書く。 サンプルですら異常な時間が掛かっており不安になるが、とりあえず裏で回しておくことにした。(後で通った)
D が分かったので実装する。この間に pulmn が F を解いていた(問題見てなかった)。
pulmn「E は 230」
noshi「100 時間くらいかかる計算」
pulmn「fibonacci になった」
noshi「215 になった」
moyashi「そうじゃん、割り算間違えてた」
3 人で E やってもしょうがないだろということで moyashi と pulmn が同時に E をコーディングして、どちらかで通ればいいですねをした。
その間に noshi が G を考えていた。
E が通ったが moyashi pulmn は G が苦手らしいので H をやってもらう。
こんなのは最小費用流の双対なんですねと言いながら双対を取ったら、解が一致しないので苦戦する。 実は weight と capacity を swap してしまっていたことが分かり、双対は正しく取れていた(は?)。 結局方針があってるのかもよく分からなかった。
終了
2019 予選, 2020 模擬で大敗していたので、良い感じの結果が出て満足した。 序盤の問題が通り終わったら自分は全ての問題に目を通すべきだったというのと、後半時間が余りまくったのでもう少し考察を速めたい。
長さ 同士の列を畳み込むのが でできるやつ
時間計算量 | 備考 | |||
---|---|---|---|---|
, 高速フーリエ変換 | ||||
環, Schönhage–Strassen | ||||
環, 高速ゼータ変換, メビウス変換 | ||||
環, 高速ゼータ変換, メビウス変換 | ||||
環, 2 で割れる, 高速アダマール変換 | ||||
環, subset convolution | ||||
環, 高速ゼータ変換, メビウス変換 | ||||
環, 高速ゼータ変換, メビウス変換 | ||||
は素数, , 高速フーリエ変換 | ||||
, ※ ただし , 高速フーリエ変換, 分割統治 | ||||
が下に凸 | ||||
が上に凸 | ||||
※ | , ※多変数畳み込み | |||
※ | 環, ※多変数畳み込み |
が集合の演算になっているものは、添え字を集合の整数表現と解釈して演算することを意味する。
実装など
n91lib_rs/subset_convolution.rs at master · noshi91/n91lib_rs · GitHub
n91lib_rs/max_min_convolution.rs at master · noshi91/n91lib_rs · GitHub
Range Mode Query - data-structures
これをもう少しだけ詳しめに解説します。 面白いので好きなアルゴリズムです。
まずは平方分割して、ブロックの境界を端点とする区間 ( 個ある) の全てについて最頻値とその頻度を計算します。 他にも前計算するものがありますが、説明が難しいのでクエリの処理方法を追いながらやっていきます。
区間 の最頻値を計算したいとします。 まずは前計算したものを使って、暫定的な最頻値と頻度 ( ) を取得します。 この暫定解が更新されるとすれば、それはブロックからはみ出た左右の端数の部分に含まれるいずれかの値によるものになります。 従って、端数の部分の全要素について、その要素が に出現する回数が を超えるか判定して、適切に更新する、というアルゴリズムがまず思い浮かびます。
クエリを にしたいので、それぞれの要素について で頻度を取得したくなりますが、 の空間計算量でこれは絶望的です。
そこで見る方向を変えて、「左側の端数部分に含まれる各要素 について、その 個後ろの の位置が より手前にあるか」という判定を考えます。 この判定自体は、全ての数についてその数だけ抜き出した index の列を持っておけば空間計算量 、時間計算量 で可能です。 これを用いた「 より手前にあったら が更新されるということなので、 を 1 増やして繰り返す」というアルゴリズムは、 の時間計算量になります。 なぜなら、ステップを 1 つ進めるたびに「 では更新されなくなったので、次の数に移る」「 が 1 増える」のいずれかが発生し、 は最初の暫定解から しか増え得ないからです。 右側の端数部分に含まれる数については逆に、 個手前の の index が より後ろにあるかを判定すれば全く同様です。
部分永続 Union Find のアルゴリズムの変種を考えました
注意: 実測では使い物にならない気がします
空間計算量
-
単一の要素からなる集合 個で初期化する
時間計算量
-
と が属する集合を併合する
時間計算量
-
回目に が呼ばれた直後に が属していた集合の代表元を取得する
時間計算量
-
回目に が呼ばれた直後に が属していた集合の要素数を取得する
時間計算量
通常の Union Find のアルゴリズムにおいて、weighted union rule は適用し、経路圧縮は行わないことで得られる木を考えます。 は、この木において の祖先で時刻 にまだ根だったものの中で最も深いものを発見すると表現できます。 もし が全て事前に与えられているならば、ダブリングを用いることで の時間計算量で に答えることが出来ます。 weighted union rule により木の高さが に抑えられることに注意してください。
よって、 を一旦忘れると、ダブリングのための情報(各頂点について、 個上の頂点)を の度に更新できれば良いです。 を の子にするとき、新たに情報を更新する必要があるのは の子孫で からの距離が二冪の頂点です。 各頂点 が : の子孫で からの距離が の頂点のリストを管理していれば、これは効率的に列挙可能です。 例えば、 から距離 の頂点は から距離 の頂点から更に距離 の頂点です。 ポテンシャルとして「計算されたダブリングのテーブルの要素数」を考えれば、テーブルの更新の時間計算量はならすことができます。
を処理するために、各頂点 は : 時刻 に を代表元とする集合の要素数が に更新された、という情報を管理します。 クエリは において要素数が の直前に更新されたときの対応するデータを報告すればよいです。 は を超えないため、これは Y-fast-trie を用いて で処理できます。 長さ のテーブルを持って適宜変換することにより、 が呼ばれた回数ではなく で実際に集合が併合された回数を時刻として利用できます。 これにより時刻は常に 未満になり、時間計算量は になります。
複雑すぎて間違えてそう、実装する気にもならない
多分もっとまともなアルゴリズムがある
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; };
struct add { int val; add operator+(add r) { return add(val + r.val); } add() : val(0) {} add(int x) : val(x) {} }; template <class T> struct segment_tree {};
D: メンバを実装したオブジェクトを持つ
struct add { using T = int; int op(int l, int r) { return l + r; } int id; }; template <class M> struct segment_tree { using T = typename M::T; M mo; };
E: 静的メンバを実装した型を受け取る
struct add { using T = int; static int op(int l, int r) { return l + r; } static inline int id; }; template <class M> struct segment_tree { using T = typename M::T; };
D, E については、id をメンバ変数ではなくメンバ関数として持つ実装もある。 その他、継承を利用する実装もあるようだが詳しくないので割愛。
著者は E を常用している。 実装例