アルゴリズム資料 Permutation Tree (こどふぉブログ勉強月間2)
こどふぉブログ勉強月間では、 codeforces blog の積読を消化して、ついでに日本語の資料を作っておくことを目標にします。
参考資料
Tutorial on Permutation Tree (析合树）codefo...
LibraryChecker
アルゴリズム資料 
競プロ Library Checker 解説 永続queue (Persistent Queue)
体系的な解説はほとんどできていないと思います。それでもよければ
永続 queue とは
これのことです↓
永続 stack
前提知識です。 pop back した後の stack へのポインタを管理すれ...
競プロ Library Checker 解説 Edge Coloring of Bipartite Graph
参考文献
Alon, Noga. "A simple algorithm for edge-coloring bipartite multigraphs" (
競プロライブラリ用はこの方法がよくて、また短くて簡単なの...
レポート Euclidean MST (Library Checker) correct.cpp の解説
背景
競プロでは、ユークリッド距離最小全域木の計算方法として、 Fortune のアルゴリズムでドロネー図(Delaunay diagram)を構築し、ドロネー図の最小全域木を計算するという方法がよくとられていま...
レポート Double-Ended Palindromic Trees 解説
Library Checker への提案を踏まえ、 で提案された Double-Ended Palindromic Trees の原理をさらい、これを実際のプログラムとして実装する過程を解説します。
arXiv preprint...
レポート 区間代入/区間積 O(logN)/query で償却計算量にしないアルゴリズム
changelog
2024-02-23 問題文中の積の説明を改善。実行時間測定用の例題の具体的な問題を説明。
概要
こういうものがあります。
:
その記事によると、計算量を償却することで空間 ...
レポート 競プロAdC やってるみたいなので Library Checker の解法紹介をぶっこむ
競プロ Advent Calendar 2022 の 1 日目担当の Nachia です。よろしくお願いします。
時間で変化する状態については、 2022/11/10 以降に取得した情報で書きます。
ライブラリ作り（盆栽）って...
競プロ Range Sort Range Product ってなんですか
雑な記事です
do you know the problem ...
お気持ち
ソートした部分を binary trie(補足1) で持っておけば、 split が $O(\log N)$ になるのでソートが...
解法解説 グラフの彩色数求値 $O(2^n n)$ や $O(2^n)$ を定数倍高速化したもの
この記事の第 1 部は、競プロ Advent Calender 2 日目として公開されています。
第 1 部 2021-12-02 投稿
第 2 部 2023-12-14 投稿
第 1 部：問題
Library...