noshi91のメモ

データ構造のある風景

アルゴリズム

定数倍が最適な Mo's Algorithm

概要 端の移動回数が 以下の Mo's Algorithm を思いついたので紹介する。 通常の Mo's Algorithm Mo's Algorithm の問題設定は以下のように言い換えられる。 を満たす格子点 が 個与えられる。 から始めて全ての点を通る経路を構成せよ。 経路の長さはマンハ…

(雑) 転置原理について考えたこと

転置原理の競プロでの使い方について考えたことを雑に並べた。 普段なら Twitter に書いているような内容だが、長かったので。 転置原理 非常に雑に言うと、以下のような定理である。 を 行列とする。「任意の 次元ベクトル を入力とし、 を計算する」ことが…

Universal Cup. Stage 10: Zhejiang. A Atcoder Problem

公式解説と違う方法で解いたのだが、その時に使った式変形が面白かったので紹介。 いくらかの計算をすると、次の問題に帰着される。 個の非負整数組 が与えられる。 これらは全て を満たす。 の先頭 項を で計算せよ。 追記 もっと簡単な方法が紹介されてい…

メモ: Bostan-Mori 法で計算できるものまとめ

\begin{align} \frac{P(x)}{Q(x)} &= \frac{P(x) Q(-x)}{Q(x) Q(-x)} \cr &= \frac{E(x ^ 2) + x O(x ^ 2)}{V(x ^ 2)} \end{align} であるから、 \begin{align} \left \lbrack x ^ k \right \rbrack \frac{P(x)}{Q(x)} &= \begin{cases} \displaystyle \left…

JOI 2022/2023 春季トレーニング 警備員 (Security Guard)

解法の説明は公式解説に任せるとして、いくつかの事実についての証明を書きます。 公式解説を見れてないのでどこが証明されてどこが証明されてないか分からない (もしかすると方針自体違うかも)。 治安が低いほど が大きいのが混乱の元なので、治安という言…

Universal Cup. Stage 5: Osijek. D Distinct Subsequences

概要 問題の解法と、巧妙な (当社比) 定数倍高速化の方法を書く。 この高速化の方法は、heno239 さんに教えてもらった方法を式変形で導出しようとしていたら思いついた。 heno239 さんの手法は理解できていないので説明できないが、恐らく最終的に得られる式…

部分列 DP メモ

を長さ の文字列とする。 の部分列が何種類あるか数え上げる。 DP 定義 の部分列であって で終わるものの種類数 の部分列の種類数 (空列含む) DP 遷移 \begin{align} \text{dp} \lbrack i + 1 \rbrack \lbrack c \rbrack &= \begin{cases} \text{sum} \lbrac…

簡易版 LARSCH Algorithm

概要 LARSCH Algorithm の簡易版を思いついたので説明する。 時間計算量 だが実装や仕組みが単純で、コスト関数が sliding window でしか計算できない場合にも有用。 2024/03/13 追記: もっと簡単なアルゴリズムがあったのでこの記事はコストがスライドでし…

和を積に変換するテクニック

右辺は で計算できるので、時間計算量は問題にならないことが多いです。 使う場面 この式を使って和の和を積の和に言い換えると、分配法則が使えてやりやすくなることがあります。 ただし和の和も和の順序の交換などの良い性質を持つので、どちらが良いかは…

アフィン部分空間の共通部分の計算

2022/05/02 記事中の記号の使い方やその他の軽微な修正をしました。 概要 のアフィン部分空間が の形で与えられるとき、 つのアフィン部分空間の共通部分を時間計算量 で計算する。 アフィン部分空間 ベクトル空間 の部分集合 は、部分空間 と によって と表…

Xorshift を用いた Zobrist hashing を衝突させる方法

概要 Xorshift によって生成された乱数列について、いくつかの場所の xor を取ると seed に依存せずに になる。 Xorshift Xorshift - Wikipedia 説明は Wikipedia に丸投げする。 本記事では簡略化のため、実装例の一番上にある周期 の実装について議論する…

周期関数の極小点を求めるアルゴリズム

定義 が を満たすとする。 を与えると を の時間計算量で取得できるとして、 を満たす を の時間計算量で求めるアルゴリズムが存在する。 アルゴリズム 一般の数列を三分探索すると極小点が求まるとは限らない - noshi91のメモ 上記の記事の後半で紹介してい…

一般の数列を三分探索すると極小点が求まるとは限らない

概要 三分探索を行うと極小点が つも求まらないような数列を構成した。 また、一般の数列に対して の時間計算量で極小点を つ求めるアルゴリズムを説明する。 定義 を実数列とする。 整数 が の極小点であることを、 を満たすことと定義する。 ただし仮想的…

Aliens DP で辺の本数が区間で指定される場合

概要 https://dic.kimiyuki.net/d-edge-shortest-path-monge この記事においてラグランジュ双対などで説明した部分を凸共役の観点から解釈し、「 本以上 本以下使う最短路」も同じように解くことができることを解説します。 本文 合成積 関数 の合成積 は \b…

容量下限などが付いている最小費用流

概要 辺の流量に下限があったりする最小費用流を、思いつく範囲で一般化してみました。 記法の定義 を有向グラフとします。 フロー に対して、その境界 を で定義します。 つまり、境界は各頂点から流れ出る量を表しています。 ベクトルに対して不等号を使っ…

最小カット問題の k 値への一般化

概要 最小カットを用いると、 及び劣モジュラな について \begin{align} \text{Minimize}&\quad \alpha + \sum _ i \theta _ i (x _ i) + \sum _ {i \lt j} \phi _ {i, j}(x _ i, x _ j) \cr \text{subject to}&\quad x \in \lbrace 0, 1 \rbrace ^ n \end{a…

Monge 性が関係する問題リスト

概要 Monge 性が関係している問題のリストを作ります。 noshi91 は過去問をあまり埋めていないので、貧弱なリストになると思います。 もし載っていないものがあったら教えてもらえると嬉しいです (noshi91 に対するネタバレを気にする必要はありません)。 リ…

クエリが整数の Convex Hull Trick の 凸 判定

概要 Convex Hull Trick で最小値取得クエリの が整数の時、アルゴリズム内で直線が不要かどうかチェックする部分を簡単に記述することが出来る。 特に、傾きと切片を掛けることでオーバーフローする問題を発生させない。 本文 Convex Hull Trick で、最小値…

割れない時の行列式

概要 逆元が必ずしもない状況で行列式を計算する方法を紹介します 一般の可換環上の行列式 n91lib_rs/division_free_determinant.rs at master · noshi91/n91lib_rs · GitHub 除算を使わない のシンプルなアルゴリズムが知られています。 除算無しでも にな…

私用メモ: 畳み込めるものまとめ

長さ 同士の列を畳み込むのが でできるやつ 時間計算量 備考 , 高速フーリエ変換 環, Schönhage–Strassen 環, 高速ゼータ変換, メビウス変換 環, 高速ゼータ変換, メビウス変換 環, 2 で割れる, 高速アダマール変換 環, subset convolution 環, 高速ゼータ変…

競プロのアルゴリズム関連略称まとめ

随時募集しています 略称 正称 APSP All Pairs Shortest Path BB Branch and bound BBST Balanced Binary Search Tree BFS Breadth First Search BIT Binary Indexed Tree BM Berlekamp-Massey BM Boyer-Moore BSGS Baby-Step Giant-Step CHT Convex Hull Tr…

みんぷろ2018決勝-A Uncommon Θ(Alog(log(A)))

A - Uncommon これを として時間計算量 で解きます。 畳み込み ゼータ変換・メビウス変換を理解する - Qiita 添え字 gcd での畳み込みで AGC038-C を解く - noshi91のメモ 添え字の での畳み込みをおおまかに理解しているとします。 は行列 を用いて と表現…

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

変数 への の割り当てに対してコストが以下の図のようになるとします。 コストを最小化するとき、 ならば最小カットで表現できます。 説明 最小カットで使えるプリミティブな操作を考えます また、解に直接値を加えることで全体に することが出来ます。 量 …

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

出来ない分割の例 木に対して、頂点集合を に分割する がつながっている: 内の任意の頂点対のパスは に含まれる が小さい: が小さい: 反例: スターグラフ 出来る分割の例 根付き木に対して、頂点集合を に分割する がつながっている: 内の任意の頂点対のパス…

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

概要 本稿では整数の での逆元について取り扱います。 文中の合同式は です。 拡張ユークリッド互除法で逆元を求める 互除法の手順を高速化できるかもしれないという提案 から の逆元を で計算する 個の数について全ての逆元を で計算する (おまけ) 拡張ユー…

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

本記事は皆様からのご指摘を募集しております 誤った記述があるかもしれません 概要 競技プログラミングをやっていると などの表記を見掛けることも多いでしょう *1。 それぞれについて、大雑把な意味をまとめました。 アルゴリズムの挙動の正確な把握は競技…

2-SAT のアルゴリズムの証明

概要 蟻本で 2-SAT のアルゴリズムを最初に見たとき、私はその正当性について何ら疑問を抱きませんでした。 これは私の頭がよく回ったからではなく、単に行間に気づいていなかったからということに最近気づきましたので、反省を兼ねて記録します。 反例のよ…

添え字 gcd での畳み込みで AGC038-C を解く

概要 数列 に対し、その gcd 畳み込み*1 を以下のように定めます この畳み込みの計算方法と、応用として AGC038-C を解く手順を示します。 数列の変換で要素毎の乗算に変換 数列から数列への関数 を導入します。 は倍数の和を取る変換で、以下のように定義し…

Offline Level Ancestor Θ(N+Q)

概要 シンプルなアルゴリズムですが、Level Ancestor Problem 自体の知名度が低そうなので宣伝を兼ねて紹介します。 Level Ancestor Level Ancestor とは、根付き木について定義される概念です。 の祖先であって、深さが であるもの ( の深さ ) の深さが分か…

総和に制限のある部分和問題の bitset 高速化

1が18個→1+2+4+8+3 にするやつをして、今回の問題だとそこで新たにできた4ともともとある4は同一視できるから4が1個増えたと思っていいよって下から順番に上の表現に直していくことで、1つ1つの個数を最大2個の状態まで変形することができて、種類数はO(√N)…