Ark's Blog

参加記や備忘録などを書いていきます

ようこそ

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というアルゴリズムで計算量は$O(nm)$。頑張ったら$O(m\log n)$や$O(m + n\log n)$とかにできるらしい。$O(m + n\log n)$のやつはフィボナッチヒープを使うとのこと。

この記事では$O(nm)$のアルゴリズムについてまとめる。

続きを読む

第6回 git challenge 参加記

「ブログに書くまでがgit challenge」とのことで、ブログを始めました!

git challengeとは

mixiさん主催の、gitに関する技術を競うコンテストです。 今回は第6回でした。

mixi-recruit.snar.jp

続きを読む