Ark's Blog

数学とか競プロとか参加記とか備忘録とか

ようこそ

アルゴリズム

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というアルゴリズム…