CODE THANKS FESTIVAL 2017 参加記

参加記

12/2にCODE THANKS FESTIVAL 2017に参加してきました。

f:id:ark4rk:20171203201334j:plain

ハル研究所プログラミングコンテスト2017 参加記

参加記マラソン

競プロ数学

DDCC2017本戦の問題「B - GCDロボット」の解説の別解、gcd/lcmとmin/maxの話が面白かったので考察してみた。

結論から言うと、gcd/lcmの空間はmin/maxの空間の可算無限個の直積と束同型であることがわかった。

数学

転倒数について調べてたらwikipediaに気になる記述があった。

列の転倒数 (inversion number) は、その整列性の測度として広く用いられる[3][2]。(wikipedia)

いったいどんな可測空間上で定義された測度なんだ？と気になって調べた。

アルゴリズム数学

最小全域木問題の有向グラフバージョン。

無向グラフに対する最小全域木は、クラスカル法とかプリム法とかで求められるけど、有向グラフの場合はどうすればいいのか気になったので調べてみた。

Chu-Liu/Edmonds' algorithmというアルゴリズムで計算量は $O(nm)$ 。頑張ったら $O(m\log n)$ や $O(m + n\log n)$ とかにできるらしい。 $O(m + n\log n)$ のやつはフィボナッチヒープを使うとのこと。

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