Algorithm

Kruskalで迷路生成

Kruskalで全域木を求めることで迷路生成ができると聞いて。

分枝限定法を利用した巡回セールスマン問題の解法のデモ作った

Jarバイナリ ソース 説明 分枝限定法を用いた巡回セールスマン問題の厳密解の解法を可視化する。緩和問題を分割して探索木を構築しながら、長さの上界を使って枝刈りをする。簡単のため、ユークリッドTSPやメトリックTSPの性質は用いず、また有向辺を用いて…

IOI2009 "Salesman"

はじめてのあいおーあい。ろくに確認もせずテストデータにとりあえず投げた結果玉砕し、その後しょーもないことで時間を潰した。練習量が足りない。死にたい。 problem IPSJの雑誌とテレビの両方で見かけたので解いてみようと思った。問題の名称がどう見ても…

最長共通部分文字列と最長共通部分列

今日から少し、典型DPを扱ってみようと思う。最長共通部分文字列(longest common substring)と最長共通部分列(longest common subsequence)。前者は連続という条件つきで、後者は連続でなくても順序が維持されていればよいというもの。 前者はO( (n+m)min(n,…

並列化における効率化の目安は(n/log n)倍。たぶん。

分散化の場合のイメージと大分違うような気がするけど、直感レベルでの話しかしてないからよくわからない。 まあなんで僕が(n/log n)倍かというと、実際並列アルゴリズムが大体そんな感じっぽいから。 畳みこみ(最大値や総和)の計算 O(n) → O(log n) ソート …

KMP法+ボイアームーア=有限オートマトン

という気がしてきたので、文字列検索の有限オートマトン化をしてみた。…普通にこれでいいじゃん!有限オートマトンの生成にかかる時間およびメモリはn=キーサイズ,c=文字の種類とおいてO(cn)なので、そこで少し遅れをとるけど、検索が非常にシンプルで高速(…

Dancing Linksを用いたKnuth's Algorithm Xによる「四角に切れ」ソルバーの実装

「四角に切れ」とは以下のような問題である。 あるサイズの格子(将棋盤タイプ)が与えられる。 マスには数字が書かれているか、書かれていない。 格子全体を長方形の集合に分割する。 全ての長方形にちょうど1つずつ数字が入り、かつ長方形の面積がその数字と…

バイトニックソート書いた

バイトニックソート(bitonic sorter)は、並列処理に適した「ソーティングネットワーク」という種類のソートアルゴリズムで、直列での時間計算量はO(n log^2 n)ですが、最大nで並列できて、その結果O(log^2 n)で計算できるようになります。 マージソートの類…

ヒープソートってかっこいいよね

/* ヒープソート(heapsort) ヒープ構造を用いたソート方法 特徴 1. 「その場」(in place)で実行できる(マージソートやバケットソートは別の配列が必要になる) 2. 最悪でもO(n log n)で実行できる(クイックソートの最悪ケースはO(n^2)) 3. かっこいい 4. 安定…

割り算が壊れたので自分で実装してみました。

あけましておめでとうございます。このブログは通常営業となりました。 概要 http://turi2.net/blog/724.html http://d.hatena.ne.jp/nitoyon/20070629/four_operations_implementation_in_javascript 多倍長での除算がこの前うまく実装できなかったので、復…

超わかりやすい拡張ユークリッドの互除法

ユークリッドの互除法を考える。 数a,bが与えられる。 1. 最初はx=a, y=bとする。 2. xをyで割った余りにする。 3. yをxで割った余りにする。 4. 2に戻る。 5. xかyが0になったときに、もう一方が最大公約数である。 ここで、この数x,yを、別の方法で表現す…

UnionFindとPriorityQueueと本選5番

UnionFindのコードを書けるようにした。去年の本選5番はPriorityQueueを使う方法が想定されているが、UnionFindでも解ける(とhosがいってた)ので、試してみた。PriorityQueueのコードも書いた。殆ど同じ。 #include <algorithm> #include <climits> #include <cstdio> #include <iostream> #include <utility></utility></iostream></cstdio></climits></algorithm>…

iostreamは遅いという話

benchmark of 10,000,000 number's input time ( yes 100 | ./a.out ) Optimization Flags | number |iostream| stdio ---------------------+------------+--------+------ CXXFLAGS="" | 100 | 9.830 | 3.664 CXXFLAGS="-O2 -Wall" | 100 | 10.006 | 3.831…

パソコン甲子園の問題1が綺麗に書けたで賞を今さらやってみた #include <stdio.h> int main() { while(1) { int i, hands[5], count[3]={0}, states[]={2,3,1}; for(i=0;i<5;++i){ scanf("%d", &hands[i]); if(!hands[i])return 0; hands[i]--; count[hands[i]]=1; } </stdio.h>…

パソコン甲子園参加記 - 「日本一である必要は何なのか、3位じゃだめなのか」

だめです。賞金の額が違います。 チームと結果 プログラミング部門P04、筑波大学附属駒場高等学校、チーム名「18.039リットル」。 三位。なお本校から本選出場したもう一つのチーム、「rand()」は優勝。 id:JAPLJのところは準優勝。上位3チームがなんかデジ…

書けるようになりたいアルゴリズム

Linear Programming (Simplex Method) Maximum Flow Problem (Ford–Fulkerson algorithm) Arbitrary precision (multiplying with FFT) Random (xorshift method)