noshi91のメモ

データ構造のある風景

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

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

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

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

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

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

JSC2019 参加記

A を読む 解けない B を読む 解けない C を読む セグ木で丁寧だけど L/2 付近の挙動が良く分からなかったので放置 D を読む 解けない E を読む パターンマッチング系なのでどうせ S か T で Trie 作って、Aho Corasick すると終わり ひいひい言いながらライ…

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

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

Offline Level Ancestor Θ(N+Q)

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

2 ポインタ/ノード で親方向を探索する二分木

概要 最もシンプルなポインタによる二分木の実装は、各ノードが左子と右子を保持することでしょう。 一方でこの実装では親方向へ遡ることが出来ません。すると例えば平衡二分探索木のイテレータを実装するときなどに問題になります。 親へのポインタを保持す…

top tree 概要

概要 niuez.hatenablog.com top tree の記事が出ていたので、あまり触れられていない部分を補足していくモチベーションで書きました。 segment tree を知らないと読んでもあまり面白くないと思います。 link cut tree を知っていれば分かりやすいです。 その…

素集合の要素の列挙と併合 (単方向循環リスト)

概要 以下の 2 種類のクエリを処理します。 と同じ集合の要素を全て列挙します。 時間計算量 を含む集合の要素数 がそれぞれ含まれる集合同士を併合します。 が同じ集合に含まれているとバグりますが検出はできません。 時間計算量 理論 同一集合内のノード…

総和に制限のある部分和問題の 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 書いた後で、概ね同じ内容を説明している記事を見つけました。分かりやすさには個人差があると思うので、本記事にも…

modint 構造体を使ってみませんか? (C++)

2019/04/01 実装例の訂正などを行いました。 2019/04/13 実行時に法が決まる問題についての説明を追加しました。 modint is 何 競技プログラミングの問題で、答えを 1000000007 (あるいは他の素数) で割った余りを求める問題は頻出です。これらの問題ではア…

北大・日立新概念コンピューティングコンテスト2018の出力とかするやつ

概要 正の点を取ってる人が少なくて寂しいので共有します。 私が使っているものと同じですが、バグがあるかもしれません。(あったら私は終わり) 使いたい場合は自由に使ってください、責任は取れませんが... コンストラクタで n と s を指定します。s は x, …

あなたの庭に永続データ構造を飾りませんか?

2019/02/06 永続 Stack のやや丁寧な実装例を追加しました 2020/12/13 数式などを整えました 概要 あなたのライブラリに新しい彩りを与える永続データ構造の紹介です。 永続データ構造とは 永続データ構造とは、普段のデータ構造で更新をするときに更新前の…

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 高速ゼータ変換は添え字を集合とみなして各添え字について部分集合の和を計算します。これと同じことを約数でも…

AtCoder でレートが 2400 に到達しました

ARC103 にて AtCoder のレートが 2402 となり、橙コーダーになることができました。黄になってからもデータ構造の勉強ばかりやってきたので、レート上昇に貢献したデータ構造たちを挙げていこうと思います。 Union Find Tree 恐らく最も使用頻度の高かったデ…

Splay Tree で三分探索木を組む

はじめに 最近競技プログラマーの間で Splay Tree のブームが来ているらしいので、それに乗っかり記事を書くことにしました。 Splay Tree は直近にアクセスした値への再アクセスが高速であったり、自己組織化する動的木にも使用されていたりと大変興味深い平…

構築 O(N) クエリ O(1) の RMQ

2019/03/10 大雑把な説明を追加しました 2019/07/08 細微な修正を行いました 概要 RMQ は競プロでも頻出のデータ構造です。本記事では競プロで実際に速度の向上が見込める高速な RMQ の実装について書きます。 本題 一般に良く知られる LCA に変換して ±RMQ …

WaveletMatrix で快適な整数列ライフを送ろう

この記事は内容に様々な問題があったので、削除されました。 Wavelet Matrix については下記のページを参照してください。 Wavelet Matrix - data-structures

ARC098 E Range Minimum Queries O(NlogN)解法

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

UnionFindTree に関する知見の諸々

2018/08/17 ポテンシャル付きUnionFindTreeの記述を変更し、RetroactiveUnionFind についての記述を追加しました。 2019/07/19 集合内の要素の列挙についての記述を追加しました。 はじめに UnionFindTree って知ってますか? 競プロでは恐らく最も使用頻度…

Disjoint Sparse Table と セグ木に関するポエム

2018/09/09 実装を少し変更しました 2021/02/18 数式を tex を使ったものに変更しました 2021/02/18 不適切な表現を変更しました 2021/02/18 msb の意味が適切でなかったので、修正しました 前半: https://discuss.codechef.com/questions/117696/tutorial-d…

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

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

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

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

Atcoderでレートが2000に到達しました

はじめに タイトルの通りなのでポエムを書こうと思います。大分イキった文章に仕上がりましたので苦手な人は見ないようにしてください。 もし自分と同じような競技プログラマーの方が居れば、参考になるかもしれないしならないかもしれない。 やったこと 昨…

競プロで使うビットベクトル

はじめに JOIの春合宿で簡潔データ構造の講義があり、競プロ界隈でも簡潔データ構造の機運が高まっているため(本当か?)、競プロで便利なビットベクトルの実装について書きます。 本記事で紹介する実装では、以下の性能を実現します。 bit列の長さをNとした…

各操作とmergeをO(α(N))で行うhashmap

概要 一般的なhashmapのサポートするキーの検索と挿入/削除に加えて、2つのhashmapを併合して1つにする操作を全てO(α(N))で行うhashmapの解説です。(α()はアッカーマン関数の逆関数) 注意点として、併合する可能性のあるhashmapにおいてkeyの重複は許され…

部分永続Union-Find Treeについて

スライドです(説明終了) バグってる可能性があるので注意してください verifyしましたが直したかどうか忘れました(最悪)