noshi91のメモ

データ構造のある風景

区間を 2 次元平面にプロットする

概要 区間 を のそれぞれを軸とする 次元平面にプロットするという方法を紹介します。 図 まず、 つの区間を置いた図がこれです。 赤い点がプロットされた区間であり、斜めの対角線を と思うと で示した部分がその区間に該当します。 点線によって領域が つ…

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

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

yukicoder 1467 Selling Cars Θ((M + N) M + N log (N))

概要 No.1467 Selling Cars - yukicoder の非常に雑な解説 解法 を固定して最小費用流にエンコードすると以下のようになります。 頂点の数値は湧き出しの量です。 実際には適切に座標圧縮します。 これは series-parallel graph なので最小費用流が効率的に…

競プロ C++ 部分集合走査ライブラリ

概要 for (auto t: subsets(s)) で s (の bit 列を集合と解釈したとき) の部分集合を走査できるようなライブラリを書きました。 単純には std::vector<int> を返せばいいのですが、速度が少し気になるので、それを解決します。 部分集合に限らず、多次元ループな</int>…

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

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

{x | b^x = a (mod m)} の構造

概要 が与えられて の構造を観察します。 結論 について、次のうちいずれかが成り立ちます。 証明 とすると、中国剰余定理から 。 を 1 つ固定して考えると、 のとき、 は存在しないか、一意に定まる。 のとき、 の形の条件が付く。 のとき、 は存在しないか…

整数と実数と不等号と切り上げと切り捨て

同じ列にある つの式は、の元で同値です。 次の つの式が成立します。

割れない時の行列式

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

ICPC2020 国内予選 参加記

Poyashi で参加して 6 完 4 位でした 開始前 リハーサル参加のためかなり早めに来たが、模擬に参加してるのでほとんど練習の必要がないことに気付く。 ライブラリを書きながら開始を待つ。 コンテスト開始後 記憶がかなり曖昧なので間違ってるかも。 A moyas…

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

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

Range Mode Query 空間 Θ(n) 構築 Θ(n√n) クエリ Θ(√n)

概要 Range Mode Query - data-structures これをもう少しだけ詳しめに解説します。 面白いので好きなアルゴリズムです。 アルゴリズム まずは平方分割して、ブロックの境界を端点とする区間 ( 個ある) の全てについて最頻値とその頻度を計算します。 他にも…

部分永続 Union Find Θ(log(log(n)))

概要 部分永続 Union Find のアルゴリズムの変種を考えました 注意: 実測では使い物にならない気がします 空間計算量 - 単一の要素からなる集合 個で初期化する 時間計算量 - と が属する集合を併合する 時間計算量 - 回目に が呼ばれた直後に が属していた…

代数的構造を乗せるデータ構造の設計について

概要 SegmentTree などのように、代数的構造 (特にモノイド) を乗せるデータ構造は多い。 この部分の設計は様々だが、「静的メンバを実装した型を受け取る」設計を他の設計と比較する。 設計のバリエーション A: std::function で関数オブジェクトを持つ tem…

「あーだこーだー」 第四回 非公式まとめ

注意: この記事は非公式です。また、情報の正確性や取捨選択について著者は一切の保証をしません。 概要 コンテスト関係で重要と思われる情報を抜粋、要約しました。 雑談などの情報は省略、あるいは大筋のみになっています。 まとめ AtCoderの公式生放送「…

「あーだこーだー」 第三回 非公式まとめ

注意: この記事は非公式です。また、情報の正確性や取捨選択について著者は一切の保証をしません。 概要 コンテスト関係で重要と思われる情報を抜粋、要約しました。 雑談などの情報は省略、あるいは大筋のみになっています。 まとめ AtCoderの公式生放送「…

オムライス

概要 オムライスを作り、食べた 今日の自炊 pic.twitter.com/JlPlOda42n— 熨斗袋 (@noshi91s) 2020年3月31日 作り方 みじん切りにした玉ねぎを炒める 鶏もも肉を加えて炒める ケチャップを加えて炒める 炊いた白米を加えて炒める チキンライス完成 卵を焼く …

AtCoder で rating が 2800 に到達しました

概要 到達当時の記録 AtCoder AtCoder Performances AtCoder Problems AtCoder Scores ライブラリ Library | This documentation is automatically generated by online-judge-verify-helper

競プロ用 C++ struct 超初級

概要 競プロ用の C++ ライブラリを作るための struct の使い方を説明する メンバ変数 struct を使うと、std::pair<int, int> と似たようなものを作ることが出来ます。 #include <iostream> struct t { int a; int b; }; int main() { t x; x.a = 1; x.b = 2; std::cout << x.a <<</iostream></int,>…

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

随時募集しています 略称 正称 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のメモ 添え字の での畳み込みをおおまかに理解しているとします。 は行列 を用いて と表現…

列の連結/全要素列挙をする永続データ構造

某に載せるほどか...? 載せることにしたらこっちは消えます 以下の操作を実現する永続データ構造が存在する 単一の要素 からなる列を作成する 時間/空間計算量 列 を連結した列を作成する 時間/空間計算量 列 の全要素を順に列挙する 時間計算量 アルゴリズ…

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

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

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

概要 Li Chao Tree で小さいほうから 個取得できる ただし取り出した 個の順番は保証されない 空間計算量 時間計算量 per query アルゴリズム 全てのノードは高々 個の直線を保持します。 元の Li Chao Tree と同様、クエリの点を覆うノードの直線だけでクエ…

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

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

バグ記録

全般 オーバーフロー 降順ループを昇順にする 入力の縦横を間違える 早期 return の return 忘れ コピペの添え字間違い 値の初期化忘れ H と W を間違える return を書き忘れる 順列の逆写像を出力している インタラクティブ 要素数 2N を N と勘違いする 0/…

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

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

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

概要 以前記事を書いたのですが消したので別の場所にもう一度書きました。 今度はある程度まともな実装付きです (その分遅いですが)。 Sliding Window Aggregation - data-structures 計算量解析 Queue の場合 ポテンシャル関数を で定義します。 Deque の場…

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

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

区間代入/区間積 Θ(logN)/query

概要 遅延セグメント木は様々な区間操作が で可能です。 一方で、代入と積の組み合わせは累乗を計算する必要があり、そのままでは に悪化してしまいます。 本稿では空間計算量を に抑えたまま、 で処理する手法を提案します。 また、積に限らず一般のモノイ…

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

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