Ark's Blog

𝔇eadline-𝔇riven 𝔇evelopment

ようこそ

アルゴリズム

線形空間𝔽₂^V上の問題に対する連結グラフから全域木への帰着

連結無向グラフが与えられたとき、それが線形空間上の問題であれば、連結グラフから全域木に帰着できるかもしれないという話です。着想は ABC 155: F - Perils in Parallel の解説から得ました。想定解の一部に「連結グラフの問題を全域木の問題に帰着」して…

半環上の最大部分配列問題とKadane's algorithm

この記事はSunrise Advent Calendar 2019の9日目の記事です。 adventar.org 内容はごった煮ということなので、アルゴリズムと代数について書きます。 TL; DR Kadane's algorithmと呼ばれる最大部分配列問題をで解くアルゴリズムがある。 このアルゴリズムは…

UnionFindまわりの用語の整理

Union findとかquick findとかweighted hogehogeとか、いまいち自分の中で用語が整理できてなかったので整理した。 主に[1]の論文を参照しているが、メモなので雑に調べている箇所もある。 Set union problem (union find problem) Set union problem(union…

全順序集合に対するimos法の拡張

AtCoder Beginner Contest 128のE - Roadworkで、imos法を拡張したアルゴリズムを思いついたのでメモ。 前提 imos法を知らない人はこちら imos法は可換群に対して特定のクエリを高速に処理するアルゴリズム 今回は全順序集合への拡張を考えた

bitによる部分集合の列挙 と 数学的理解

bitテクニックで、集合の部分集合を列挙するものがあります。その紹介と数学的理解です。

Kadane’s Algorithm | 最大部分配列 問題

DPについて調べてたらKadane's algorithmという聞いたことないアルゴリズムが出てきたので調べてみた。 Kadane's algorithmは、最大部分配列問題(maximum subarray problem)をで解くアルゴリズムみたいです。 以下は、最大部分配列問題とそれを解くアルゴリ…

D言語にもDequeがほしい!

Dequeとその実装の話

最小有向全域木を求める | Chu-Liu/Edmonds' algorithm

これはなに 最小全域木問題の有向グラフバージョン。 無向グラフに対する最小全域木は、クラスカル法とかプリム法とかで求められるけど、有向グラフの場合はどうすればいいのか気になったので調べてみた。 Chu-Liu/Edmonds' algorithmというアルゴリズムで計…