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と呼ばれる最大部分配列問題をで解くアルゴリズムがある。 このアルゴリズムは…

max(∅)=-∞ は半群のモノイド化

全順序集合に思いを馳せながら寝たら思いついたネタを投げます。 導入 数学書かなにかで次のような記述を見たことがあるかもしれません。 を正の整数全体の集合とする。 このとき、に対してと定義する。 ただし、とする。 「ただし、とする」 これ、特殊扱い…

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

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

gcd/lcmとmin/maxが同型という話

DDCC2017本戦の問題「B - GCDロボット」の解説の別解、gcd/lcmとmin/maxの話が面白かったので考察してみた。 結論から言うと、gcd/lcmの空間はmin/maxの空間の可算無限個の直積と束同型であることがわかった。

転倒数と測度の話

// 転倒数について調べてたらwikipediaに気になる記述があった。 列の転倒数 (inversion number) は、その整列性の測度として広く用いられる[3][2]。(wikipedia) いったいどんな可測空間上で定義された測度なんだ?と気になって調べた。

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

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