noshi91のメモ

データ構造のある風景

noshi91 が書いた AtCoder のユーザー解説一覧

Increasing Prefix XOR https://atcoder.jp/contests/arc141/editorial/4048 と を比較することで、答えの具体的な形を FPS を使って導出する。q-binomial coefficient と関係がある。 Stonks https://atcoder.jp/contests/abc250/editorial/3945 離散凸解析…

ICPC 2022 国内予選 参加記

potato167, noshi91, tatyam で参加しました。 tatyam 視点 → ICPC 2022/23 国内予選参加記 (tatyam 視点) | 東京工業大学デジタル創作同好会traP 初手 A: potato, B: tatyam, C: noshi で担当。noshi は実装が遅いので序盤の速度ゲーに触りたくないため、こ…

競プロにおける約数の個数の見積もり

概要 を満たす の正整数の約数の個数の最大値は 程度と思っておけば競プロの計算量の見積もりで便利そう。 実験 を の正の約数の個数として、 と定義し、 と の関係を見る。 つまり、 と見積もると実際 *1 にはその 倍から 倍程度に収まることになる。 例え…

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

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

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

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

重心分解で 1 点更新区間取得

概要 木上の等高線集約クエリ - suisen のブログ この記事で未解決になっていた変種 を解決する。 を可換モノイドとし、 頂点の木 の各頂点には の元が書き込まれているとする。 に書かれている値を に書き換える。 から距離 以上 未満の頂点に書かれた値の…

ICPC2021 Yokohama Regional 感想

チームメイトに投げる場面が多く自分の実力の低下を感じた。 K を検索したのが一番の貢献だったはずだが通せなかったため無に 来年度どうするかあまり考えていない (参加はしたい) 今年は特に問題が面白いと感じたので upsolve 予定

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

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

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

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

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

概要 Monge グラフ上の $d$-辺最短路長を計算するアルゴリズム | Kyopro Encyclopedia of Algorithms この記事においてラグランジュ双対などで説明した部分を凸共役の観点から解釈し、「 本以上 本以下使う最短路」も同じように解くことができることを解説し…

Top Tree の構造の変種

注意: 雑です 概要 [1] で定義された top tree は、葉が underlying tree の辺に対応するなどの条件があります。 [2] は splay tree をベースにした top tree を説明しています。 [1] の定義にはわずかに合致しないものの、いくらかの良い性質を持つ構造を思…

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

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

カタラン数を鏡像法で理解する

概要 この記事の内容は [1] の解説の一部を抜き出して説明したものです。 カタラン数 が と等しいことを、鏡像法 *1 で説明します。 本文 は、グリッド上を右上方向に、 から まで、 を満たすように移動する方法の数と一致します。 の条件を一旦忘れて、 か…

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

3 次元空間のクエリを処理する Wavelet Matrix

概要 Wavelet Matrix は 2 次元空間の点群に関するクエリを処理するデータ構造と見ることが出来ます。 これを発展させて 3 次元空間の点群に関するクエリを で処理するデータ構造が存在します。 出来ること を非負整数の つ組の列として、データ構造を構築す…

区間を 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…

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

長さ 同士の列を畳み込むのが でできるやつ 時間計算量 備考 , 高速フーリエ変換 環, Schönhage–Strassen 環, 高速ゼータ変換, メビウス変換 環, 高速ゼータ変換, メビウス変換 環, 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の公式生放送「…