解きたい問題 障害物のある平面において起点と終点を結ぶ経路を探索し直線数を最小化したい。 障害物は線分で与えられる。 経路の長さは目的としない。 この画像は問題の単なる一例であり、障害物は平面上に自由に置けるものとする。 解決手順 適当な細かさ…

問題 連結無向グラフのカットのうち最小のものを求める。 実装 ソースコード(IdeOne) 解説 乱択アルゴリズムによる実装。 一辺をランダムに選んで縮約していく。 最後に2点残る。これらの点に縮約された点が大域最小カットである可能性は以上。 頂点の数をと…

問題の定義 平面上のn個の点の中からユークリッド距離が最小の点の組み合わせを出力する。 実装 ソースコード(Ideone) 解説 入力をランダムにシャッフルしたのちに逐次添加アルゴリズムを用いる。 アルゴリズムが実行される任意の時点において、一辺の長さの…

説明 乱択逐次構成法で点列から凸包を求めます。 三角形から始めて順次凸包を大きくしていく。 実行時間はO(nlogn)。

コンペ形式 レナとミナミの国際プログラミング選手権 【幼なじみ or 許嫁】国際プログラミング選手権を制したコード7選+α こちらに参加しました。

説明 QuickSelectと呼ばれているO(n)時間アルゴリズムを利用する。

目的 Fast Fourier Transform (FFT) のアルゴリズムとして Cooley-Turky 法が紹介されることが多いと思いますが、あまり触れられることのない、もうひとつのアルゴリズムである Stockham 法について書きたいと思います。