Ark's Blog

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

ようこそ

数学

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