noshi91のメモ

データ構造のある風景

アルゴリズム

最小カット問題の 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)…

ICPC2019国内予選D Ο(NlogN)

予選落ちました 本番で AC しましたが、証明の誤りがありましたらご指摘をお願いします。 解法 c=a-b をして階差を取ると、次のような問題に帰着できます。 c[0]...c[n] があります。「c[i]+=1, c[j]-=1 (i

拡張ユークリッド互除法を非再帰ベースで理解する (C++)

2021/02/18 数式を修正しました 拡張ユークリッド互除法とは 方程式 の解 を 1 つ求めるアルゴリズム*1です。 注意 qnighy.hatenablog.com 書いた後で、概ね同じ内容を説明している記事を見つけました。分かりやすさには個人差があると思うので、本記事にも…

k 値数列の転倒数

2019/04/20 実装の誤りなどを修正しました。 2021/02/18 説明を大幅に変更しました。 概要 qiita.com こちらの記事を読んで 値だけでなく一般の 値について拡張できそうだと思ったので、それを書きます。 値転倒数が伴う群 \begin{align} G &= \mathbb{Z}^k …

高速ゼータ変換の約数版 O(N log(log(N)))

添え字 gcd での畳み込みで AGC038-C を解く - noshi91のメモ 高速化前の実装と、実用例などが書かれています 概要 kazuma8128.hatenablog.com 高速ゼータ変換は添え字を集合とみなして各添え字について部分集合の和を計算します。これと同じことを約数でも…

ARC098 E Range Minimum Queries O(NlogN)解法

はじめに ARC098お疲れさまでした。Fを終了1分前に記念提出したらサンプル以外ACしていた(=埋め込みで全完狙えてた)ので少し残念な気持ちです。それはそうとE問題が準線形時間で解けることが解説で示唆されていたのでそれについて書こうと思います。E問題の…

ABC091/ARC092 D Two Sequences の解法について

O(N * log(max(a))解法 解法の軸は解説の通りですが、いくらかの工夫をします。まず、数列のソートに桁ごとのバケットソートを使用します。下位の桁から順に計算していけば基数ソートの動きそのままになるので、各桁で O(N) でソートが可能です。数列 a, b …

二部グラフ判定をUnionFindTreeで行う

2018/06/16 ライブラリの変更に伴い、コードを書き直しました。 概要 二部グラフ判定の方法を調べるとBFS/DFSが良く出てくるのですが、UnionFindTreeと頂点拡張を用いた方法が簡潔で使いやすいと感じたため覚え書きを兼ねて書きます。 アルゴリズム 全ての頂…

LISの計算について

LISは競プロでも低くない頻度で出現する題材です。 一般に知られている計算方法では単純な配列を用いてO(NlogN)でLISの計算が可能ですが、BITを用いることで同じ計算量でより直感的に(個人差あり)LISの計算が可能なのでそれについて少し書きます。 与えられ…