Rustコトハジメ

プログラミング言語Rustに関する情報をお届けします。

LCAを実装した

LCA (Lowest Common Ancestor)は、木構造の中でもっとも低い共通の祖先を調べるデータ構造です。 これはナイーブに実装すると、ノード数分だけ時間がかかってしまいますが、Sparse Tableと同様のアイデアを用いることによってO(logN)まで落とすことが出来ま…

Sparse Tableを実装した

Sparse Tableというのは、配列上のある範囲の最小値(あるいは最大値)を持ったインデックスを返すためのデータ構造(いわゆるRMQ)で、ナイーブに実装すると明らかにO(N)かかるが、Sparse Tableだと構築にO(NlogN)かかるがクエリ自体はO(1)で終わる。 その…

Chu-Liu/Edmondsアルゴリズムを強連結成分分解を使って実装した

www.rustforbeginners.com で、SCCについて説明しました。今回は、SCCを応用して、最小全域有向木を探すアルゴリズムを実装します。一番参考になったのはこちらです。アルゴリズムとしては同じですが、SCCを使って自分で実装してみます。 www.creativ.xyz ア…

強連結成分分解

強連結成分分解(Strongly-Connected-Components, SCC)をメモっておきます。 強連結成分というのは、有向グラフにおいて、そのグループに含まれている点は、どの点u,vをとってもお互いに行き来出来るというものです。例えばサイクルなどは明らかに強連結成…

フォードファルカーソン法の復習

一回理解したと思ったんですが、もう一度読んだら全く理解不能だったため、蟻本に書いてあることを自分の言葉で書き直して復習します。 フォードファルカーソン法というのは、辺の容量が与えられたネットワークにおいてs-tの最大流を求めるアルゴリズムです…

牛ゲーの解法

スマホゲームを作ったり他のブログをやってたら2ヶ月間、競プロの勉強から離れていて、戻ってみたら牛ゲーのことすらすっかり忘れていたのでここで復習しておきます。(ものは忘れかけた頃に復習するのが良いのです。2ヶ月も開けたのは意図的です) 牛ゲーと…

ijkがMoongiftで紹介された

www.moongift.jp www.rustforbeginners.com おれが開発しているエディタijkが、Moongiftに紹介された。 Moongiftというのは新しいオープンソース・ソフトウェアを紹介している記事サイトで、時々ツイッターなどで見ることがあり、気になったものがあれば読む…