数学
連結無向グラフが与えられたとき、それが線形空間上の問題であれば、連結グラフから全域木に帰着できるかもしれないという話です。着想は ABC 155: F - Perils in Parallel の解説から得ました。想定解の一部に「連結グラフの問題を全域木の問題に帰着」して…
この記事はSunrise Advent Calendar 2019の9日目の記事です。 adventar.org 内容はごった煮ということなので、アルゴリズムと代数について書きます。 TL; DR Kadane's algorithmと呼ばれる最大部分配列問題をで解くアルゴリズムがある。 このアルゴリズムは…
全順序集合に思いを馳せながら寝たら思いついたネタを投げます。 導入 数学書かなにかで次のような記述を見たことがあるかもしれません。 を正の整数全体の集合とする。 このとき、に対してと定義する。 ただし、とする。 「ただし、とする」 これ、特殊扱い…
bitテクニックで、集合の部分集合を列挙するものがあります。その紹介と数学的理解です。
DDCC2017本戦の問題「B - GCDロボット」の解説の別解、gcd/lcmとmin/maxの話が面白かったので考察してみた。 結論から言うと、gcd/lcmの空間はmin/maxの空間の可算無限個の直積と束同型であることがわかった。
// 転倒数について調べてたらwikipediaに気になる記述があった。 列の転倒数 (inversion number) は、その整列性の測度として広く用いられる[3][2]。(wikipedia) いったいどんな可測空間上で定義された測度なんだ?と気になって調べた。
これはなに 最小全域木問題の有向グラフバージョン。 無向グラフに対する最小全域木は、クラスカル法とかプリム法とかで求められるけど、有向グラフの場合はどうすればいいのか気になったので調べてみた。 Chu-Liu/Edmonds' algorithmというアルゴリズムで計…