タイトルの通りです。学びがあるたびに更新していきます。
2020/10/20 : Euler tour
以前から存在自体は知っていたが初めて利用した。DFS順に木の頂点や辺を配列に埋め込むことで、LISや頂点間距離などをセグ木を用いて求めたりできる。
この問題はその延長線上にある問題。初めて解説を見たときは意味が分からなかったが、理解した今見るとやるだけにも見える。Euler tourの練習問題みたいな問題だと思った。
2020/10/24 : Hallの定理
atcoder.jp以前から知ってはいたが実際に問題で使ったのはこれが初めて。今見るとどう見てもこの定理を使いそうな問題なのに、慣れてないと意外に気付かないもんですね。ってか忘れてた。
2020/10/31 : ラグランジュ補完
大学受験生時代に何かの模試でラグランジュ補完を見た気がするが、当時は自分が使うには高級すぎる概念だと思ってパスした記憶がある。今見るとめっちゃ大事やんとなる。これまで飛ばした多項式の問題が2-3問くらい解けそう。
2020/11/25 : O(N^3)に見せかけてO(N^2)になってるやつ(呼び方不明 更新: "2乗の木DP"と言われるらしいです)
呼び方不明だが、黄埋めをしていたら似たような考え方を用いる2問に遭遇した。初見だとかなりO(N^3)に見えてしまうのでメモ。
2問とも部分ごとの探索結果をマージしていく。サイズがA, Bである2つの部分の結果をマージするのにO(AB)かかるので一見O(N^3)かかるが、よく考えるとO(N^2)であることがわかる。気付いてしまえばどうということはない計算量解析だがうっかりしやすいと感じた。
2020/12/09: 最大正方形/最大長方形
いずれも計算量はグリッド面積に対して線型。
最大正方形: えっこんな簡単なDPで解けるんですか？
最大長方形: 蟻本に載ってたヒストグラム中の最大長方形に帰着するのは盲点だった。
12\19 高速きたまさ法
yosupo.hatenablog.comk項間線型漸化式の第n項をO(k^2 * logn)で求める。行列累乗ならO(k^3 * logn)だが、さらに高速に行えるという話。行列累乗だと行列の中身がスカスカになるのでコストが削減できないかなあと思ったことはあったが、このアルゴリズムはその具体的な手法を与えている。漸化式の線型性をうまく利用しているという印象。
これを使うと↑が解ける。実装めんどくさい。
2021/01/28 グラフの橋と関節点(Lowlink)
灘校パソコン研究部部誌2014「競技プログラミングで使えるグラフ理論の基本」
ARC111-Dにも応用できる考え方らしい。
「DFSの探索中に探索済みの頂点が出てきたらそれはDFSで取り出した全域木における先祖か子孫」はDFSの良い性質なんだなと思った。
verify用はこれ。
2021/01/29 並列二分探索
M回の操作列の途中で初めて~~なのはいつ？などのクエリが複数個ある際の二分探索。クエリごとに下界と上界を持ち、操作列を１回回せば１つの二分探索と同じ要領でクエリごとの答えの範囲(上界-下界)が半分になる。１回の操作にかかる計算量はO(M+Q)なので、全体として計算量はO((M+Q)logM)。
2021/02/08 ブルーフカ法
最小全域木を求めるアルゴリズム。プリムとクラスカル以外にもあるんですね。その時点での連結成分ごとに外へつながる辺のうち最もコストが小さいものを選び、それを小さい順にクラスカル法の要領でつないでいく。
クラスカル法に比べると無駄に複雑なことをやっているように見えるので、使う機会はないと思っていたのだが、「全ての辺の重みを調べきれないが、連結成分から伸びる辺のうちコストが最小の辺を調べられる」場合はこれが有効になる。
atcoder.jpちなみに非想定。
2021/02/24 プリューファーコード・ケーリーの公式
頂点ラベルあり・辺ラベルなしの木は、n^(n-2)通り存在する(n: 頂点数)。かなり非自明な公式。プリューファーコードと１対１に対応していることを用いる証明が簡単。上の問題もこの応用で解く。
