2018-01-01から1年間の記事一覧
2019/04/20 実装の誤りなどを修正しました。 2021/02/18 説明を大幅に変更しました。 概要 qiita.com こちらの記事を読んで 値だけでなく一般の 値について拡張できそうだと思ったので、それを書きます。 値転倒数が伴う群 \begin{align} G &= \mathbb{Z}^k …
添え字 gcd での畳み込みで AGC038-C を解く - noshi91のメモ 高速化前の実装と、実用例などが書かれています 概要 kazuma8128.hatenablog.com 高速ゼータ変換は添え字を集合とみなして各添え字について部分集合の和を計算します。これと同じことを約数でも…
ARC103 にて AtCoder のレートが 2402 となり、橙コーダーになることができました。黄になってからもデータ構造の勉強ばかりやってきたので、レート上昇に貢献したデータ構造たちを挙げていこうと思います。 Union Find Tree 恐らく最も使用頻度の高かったデ…
はじめに 最近競技プログラマーの間で Splay Tree のブームが来ているらしいので、それに乗っかり記事を書くことにしました。 Splay Tree は直近にアクセスした値への再アクセスが高速であったり、自己組織化する動的木にも使用されていたりと大変興味深い平…
2019/03/10 大雑把な説明を追加しました 2019/07/08 細微な修正を行いました 概要 RMQ は競プロでも頻出のデータ構造です。本記事では競プロで実際に速度の向上が見込める高速な RMQ の実装について書きます。 本題 一般に良く知られる LCA に変換して ±RMQ …
この記事は内容に様々な問題があったので、削除されました。 Wavelet Matrix については下記のページを参照してください。 Wavelet Matrix - data-structures
はじめに ARC098お疲れさまでした。Fを終了１分前に記念提出したらサンプル以外ACしていた(=埋め込みで全完狙えてた)ので少し残念な気持ちです。それはそうとE問題が準線形時間で解けることが解説で示唆されていたのでそれについて書こうと思います。E問題の…
2018/08/17 ポテンシャル付きUnionFindTreeの記述を変更し、RetroactiveUnionFind についての記述を追加しました。 2019/07/19 集合内の要素の列挙についての記述を追加しました。 はじめに UnionFindTree って知ってますか？ 競プロでは恐らく最も使用頻度…
2018/09/09 実装を少し変更しました 2021/02/18 数式を tex を使ったものに変更しました 2021/02/18 不適切な表現を変更しました 2021/02/18 msb の意味が適切でなかったので、修正しました 前半: https://discuss.codechef.com/questions/117696/tutorial-d…
O(N * log(max(a))解法 解法の軸は解説の通りですが、いくらかの工夫をします。まず、数列のソートに桁ごとのバケットソートを使用します。下位の桁から順に計算していけば基数ソートの動きそのままになるので、各桁で O(N) でソートが可能です。数列 a, b …
2018/06/16 ライブラリの変更に伴い、コードを書き直しました。 概要 二部グラフ判定の方法を調べるとBFS/DFSが良く出てくるのですが、UnionFindTreeと頂点拡張を用いた方法が簡潔で使いやすいと感じたため覚え書きを兼ねて書きます。 アルゴリズム 全ての頂…
はじめに タイトルの通りなのでポエムを書こうと思います。大分イキった文章に仕上がりましたので苦手な人は見ないようにしてください。 もし自分と同じような競技プログラマーの方が居れば、参考になるかもしれないしならないかもしれない。 やったこと 昨…
はじめに JOIの春合宿で簡潔データ構造の講義があり、競プロ界隈でも簡潔データ構造の機運が高まっているため(本当か？)、競プロで便利なビットベクトルの実装について書きます。 本記事で紹介する実装では、以下の性能を実現します。 bit列の長さをNとした…
概要 一般的なhashmapのサポートするキーの検索と挿入/削除に加えて、２つのhashmapを併合して１つにする操作を全てO(α(N))で行うhashmapの解説です。(α()はアッカーマン関数の逆関数) 注意点として、併合する可能性のあるhashmapにおいてkeyの重複は許され…
スライドです(説明終了) バグってる可能性があるので注意してください verifyしましたが直したかどうか忘れました(最悪)
LISは競プロでも低くない頻度で出現する題材です。 一般に知られている計算方法では単純な配列を用いてO(NlogN)でLISの計算が可能ですが、BITを用いることで同じ計算量でより直感的に(個人差あり)LISの計算が可能なのでそれについて少し書きます。 与えられ…
