昨日，解法と共に知った問題．メモ． n個の要素が与えられる． また，2つの要素を受け取り，同じか否かを判定する判定機が与えられる． この判定機を用いて n/2よりも多く同じものがあるかを判定したい． 計算時間は判定機の使用回数とする． 例） {A, A, B,…

実装したので，メモ． 実装といっても，単純なアルゴリズムなので，コードは至極シンプル． import System.Random (randomRIO) solovayStrassen :: Integer -> IO Bool solovayStrassen n = return.isProbablyPrime n =<< randomRIO (1,n-1) isProbablyPrime…

なぜ， 最小費用流 @ C++ - 落書き、時々落学 をしたかというと，仇打ちです．当初，最小費用循環流を実装していた． →できた →検証しよう →UVa 10594 時間オーバー，別の問題（2部グラフの最小費用最大マッチング）ではOKだった． →別のアルゴリズムで UVa …

最小費用流実装した． 最小費用流のアルゴリズムは少なくとも3種類ぐらいある． とりあえず，フローを求めてから，負閉路を頑張って消していく 最小費用0フローからはじめて，augmenting shortest path で増やしていく push, relabelの一般化（よく知らない…

最大流アルゴリズムを実装した．Edmonds Karpは増大道に沿ってフローを更新（大域的操作）に対して， Push RelabelはPush か Relabel（局所的更新）のみ． だから，楽に実装できると思ったら，実はたいして変わらなかった．Edmons Karp // O(VE^2), BFS = O(…

前回の続き．今回は強連結成分分解する． しかも，DFS1回だけ実行． アルゴリズムは非常にシンプル．そして，結構分かりやすいと思うのだが． アルゴリズムの解説等は以下が比較的分かりやすいと思う． http://www.ics.uci.edu/~eppstein/161/960220.html#sc…

Project Euler等で時々C++を使うのだが， いまだかつて，classを一度たりとも使っていないことに気がついた． まぁ，僕は「オブジェクト指向なんてくそくらえ」な立場なので問題ないといえば問題ないが．しかし，使えるに越したことはない． ということで練…

UnionFindさえあれば，結構簡単に実装できるのね． ただ，正しく動くかほとんど確認していないので，バグがあるかも． // disjoint_set.h #include <iostream> using namespace std; class UnionFind { private: int *root, *rank; // root < 0 のときはサイズの情報 p</iostream>…

Dijkstra まだ一度も走らせていない。 たぶんバグあり。 module Dijkstra where import Data.List import Data.Graph import Data.Array.IArray import Debug.Trace import qualified Data.Set as Set type Weight = Array Edge Int -- g=graph, w=weight, d…