前編 (平衡二分探索木編) はこちら http://www.slideshare.net/iwiwi/2-12188757
プログラミングコンテストでの乱択アルゴリズム
前編 (平衡二分探索木編) はこちら http://www.slideshare.net/iwiwi/2-12188757
実世界で超頻出！二部マッチング (輸送問題、ネットワークフロー問題）の解法を総整理！ - Qiita
0. はじめに --- 二部マッチング問題は実世界で超頻出 はじめまして。NTTデータ数理システムでアルゴリズムを探求している大槻 (通称、けんちょん) です。 好きなアルゴリズムはタイトルにもある二部マッチングですが、会社ではなぜか「DP が好きな人」と呼ばれています。 以前に動的計画法 (DP) の典型パターンを整理した記事を執筆したのですが、DP と並んで超頻出の話題として二部マッチング問題があります。二部マッチング問題とは、例えばマッチングアプリなどに見られるように、2 つのカテゴリ間で最適なマッチングを構成していく問題です。実問題で登場する二部マッチングは以下のように多岐にわたります: マッチングアプリで男女のペアを最適化する (「男」と「女」) インターネット広告分野で、ユーザの興味に合う広告を出す (「ユーザ」と「広告」) 企業検索サービスなどで、ユーザの検索履歴に合う企業を
私が書いた最速のハッシュテーブル – PART 1 | POSTD
結局、やり出したら止まりません。私は以前、” I Wrote a Fast Hashtable（私が書いた高速なハッシュテーブル） “という記事と、それに次いで” I Wrote a Faster Hashtable（私が書いたより高速なハッシュテーブル） “という記事をブログにアップしましたが、今回ついに、最速のハッシュテーブルを書き上げました。これが意味するところは、ルックアップがどのハッシュテーブルよりも速いということです。それに加えて、挿入や削除も（最速とまではいかないまでも）非常に速く行えます。 秘訣は、探索回数の上限を設定したロビンフッドハッシュ法を使用することです。ある要素が、その理想的な位置からX数以上、離れた位置にある場合、テーブルを拡張することで、全ての要素が、その大きなテーブル内において、理想的な位置に近づくようにします。結果的に、このやり方は非常にうまくいきました。
トップページ | Programming Place Plus アルゴリズムとデータ構造編
トップページ ここは、Programming Place Plus の、アルゴリズムとデータ構造編のトップページです。 各種アルゴリズムとデータ構造に関して、詳細な解説や、Ｃ言語を使った具体的な実装例があります（Ｃ言語についての情報は、Ｃ言語編を参照してください）。 データ構造 整列アルゴリズム 探索アルゴリズム その他のアルゴリズム APPENDIX リンク集 参考書籍
O(1)というのはご機嫌に速いということ？ | 配電盤
「実際に起こりうる状況ではご機嫌に速い」という意味で「O(1)」と書くことがあるわけですが、誤解が生じるのでやめたほうがいいと思います。 たとえばn桁の足し算は、2つの整数および結果が適当なレジスタに収まるうちは、1クロック（程度）でできるのでご機嫌に速いわけですが、O(1)というわけではもちろんなく、O(n)だと考えるのがふつうでしょう。 もう少し厳密に言うと、精度に限りがあるのであれば、指数関数もO(1)でよい、ということです（ベキ乗はO(1)でOK?） もう少し厳密に言えば、O記法は極限の概念の上に成り立っているものなので、精度に限りがあるときには使いません。精度に限りがあるのなら、結果の入ったテーブルを使うことで、どんな関数でもご機嫌に速く計算できます。もっとも、テーブルを作るのに時間がかかるわけですが、 こうして一度出した結果を覚えておいて、あればそれを使うという方法はメモ化(m
計算量
3. 例 ● 問：1 ~ Nまでの整数の総和を求めよ – 普通に計算する → N-1回足し算 → O(N-1) – 公式を使う → 足し算と掛け算と割り算 → O(3) ● 計算の仕方によって計算量が違うことがある 4. いくつかのルール ● O記法の中身は一番大きな規模だけ残す ● 係数は1にする ● 例 – O(N-1) → O(N) – O(4N^2 + 2N) → O(N^2) – O(N^2 + M^2) → NとMが独立なのでこれ以上無理 – O(2^N + N^2) → O(2^N) – O(3) → O(1) 5. なぜか ● 中の変数が非常に大きな値になった時のことを考える ● O(5N^2 + 100N + 4)の場合 – N = 1 → 109 – N = 100→ 60004 – N = 10000 → 501000004 – N = 100000000 → 500
色々なダイクストラ高速化
HCPC 勉強会 (2019/4/4) - Convex Hull Trick ※文字が見えない場合は、ダウンロードするかフルスクリーンにしてご覧ください
「充足可能性問題(3-SAT)を解く乱択アルゴリズム」 by Julia - Qiita
前置き 元ネタは、結城浩氏著の「数学ガール 乱択アルゴリズム」。 新しい言語を覚えるとき、慣れるために「充足可能性問題（3-SAT）を解く乱択アルゴリズム」（p.353）を実装するという癖をつけていま1す。 ということで。前回の Egison版 に引き続き。勉強開始約1ヶ月の Julia ( http://julialang.org/ ) で実装してみました2。 開発環境・動作確認環境 Mac OSX 10.9.5 Julia 0.3.5 コード # Rw3sat.jl sample(a::Array) = a[rand(1:end)] immutable Literal index::Int not::Bool end literal(index, not) = Literal(index, not) # issatisfied(l::Literal, x::BitArray{1}) =
競技プログラミング特有の変な実装テク - ichyo.jp
初めに この記事はCompetitive Programming Advent Calendar 2014の15日目の記事です． 競技プログラミングでは，アルゴリズムをひらめく力や，数学やアルゴリズムの知識量などが強さを決める大きな要素ではありますが， もちろん，プログラミングを使った競技である以上は，コードの実装力が勝敗を分けることもあります． 例えば，ICPC系のコンテストでは，アルゴリズムを考える能力よりも，実装量の多いプログラムをいかにバグなく高速に実装するかが重要な 問題セットが与えられることが時々あります． 競技プログラミングと無縁なプログラマーは，実装力と聞くと， クラスの構造をうまく設計したり，変更に強い美しいコードを実装する能力だと想像する人がいるかもしれません． ですが，プログラミングコンテストに必要な実装力は，そうした保守性や拡張性ではなく， 「目的の処理をシンプルな
t.dvi
Purely Functional Data Structures Chris Okasaki September 1996 CMU-CS-96-177 School of Computer Science Carnegie Mellon University Pittsburgh, PA 15213 Submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy. Thesis Committee: Peter Lee, Chair Robert Harper Daniel Sleator Robert Tarjan, Princeton University Copyright c 1996 Chris Okasaki This research was sponso
遅いソート - 鍋あり谷あり
http://bugrammer.hateblo.jp/entry/2014/08/16/014212 ( バブルソートよりも非効率なソートアルゴリズムを探して ―― ストゥージソートとスローソート ) を読んで。 ちゃんと終わるけどもっと遅いソートがあるので書いてみた。 たぶん名前がついていると思うんだけど、調べてないので名称不明。 こういう奴。 def try_all_sort(s) s.permutation(s.size){ |x| return x if x.each_cons(2).all?{ |a,b| a<=b } } end typical case では bogo sort と同じオーダー。 bogo sort と違って、worst case は有限。O((N+1)!)だと思う。 で。ベンチマーク。 100要素を1000回なんて宇宙が消滅するまでに終わらないので、試した
バブルソートよりも非効率なソートアルゴリズムを探して ―― ストゥージソートとスローソート - Line 1: Error: Invalid Blog('by Esehara' )
はじめに 恐らく、プログラマの中で配列内の要素を整列させたりするソートにお世話にならなかった人、というのは余り考えられないのではないでしょうか。しかし、とはいえ、大抵はソートを自前で実装せず、組み込み関数であったり、あるいは何らかのライブラリで済ませることが殆どだと思う。 車輪の再発明というよりも、バグとか、自分が考慮していなかった挙動などを避けるために、自前でソートを組むことは余りないのですが、とはいえ、自分なりにソートを実装して見ると、それがどういう特徴を持ったソートであるか、というのがわかりますし、また、ソートというのはいったいどういう操作で実現されるのかという洞察が深まってくるなあ、という実感があったりする。 なので、今回はあるソート二つについての話を書くのが趣旨です。 最高のアルゴリズムはある、だが最悪のアルゴリズムは何か 一口にソートといったところで、ソート自体にも銀の弾丸があ
A Very Brief Introduction to the Pi-Calculus (in Japanese)
π-calculus 超入門 π-calculus は、80 年代の終わりごろに Milner らによって提案された並行計算のモデルの一つです。そこでは、プロセスと呼ばれる複数の独立した主体が、通信チャネルと呼ばれるデータの通り道を介して値をやりとりしながら、計算を行っていきます。π-calculus にはいろいろな変種があるのですが、ここではとりあえず次のような構成要素からなるものを考えましょう。 new x . P 新しいチャネル x を作ってから、プロセス P を実行する (channel creation) x![v1, ..., vn] チャネル x に値 v1, ..., vn を送る (asynchronous output) x?[v1, ..., vn] . P チャネル x から値 v1, ..., vn を受け取って、P を実行する (input guard) P |
ビットを数える・探すアルゴリズム
作成日：2004.05.04 修正日：2012.09.01 このページは 2003年の9/11、9/28 の日記をまとめて作成。 はじめに PowerPC 系や Alpha などには population count と呼ばれるレジスタ中の立っているビット数を数える命令が実装されている。 集合演算を行うライブラリを実装したい場合などに重宝しそうな命令である。 職場でこの population count 命令について話をしているうちにビットカウント操作をハードウェアで実装するのは得なのか？という点が議論になった。 CPU の設計をできるだけシンプルにするためには、複雑で使用頻度の低い命令は極力減らした方がよい。 例えば SPARC は命令セット中にビットカウント演算があるが、CPU 内には実装しないという方針をとっている(population 命令を実行すると不正命令例外が発生し、それを
平方数かどうかを高速に判定する方法 - hnwの日記
平方数とは、ある整数の平方（＝二乗）であるような整数のことを言います。つまり、0,1,4,9,16,...が平方数ということになります。 ところで、与えられた整数が平方数かどうかを判定するにはどうすれば良いでしょうか。与えられた整数の平方根の小数点以下を切り捨て、それを二乗して元の数になるかどうか、というのがすぐ思いつく実装です。 <?php function is_square($n) { $sqrt = floor(sqrt($n)); return ($sqrt*$sqrt == $n); } しかし、平方根の計算は比較的重い処理です。もっと高速化する方法は無いのでしょうか。 多倍長整数演算ライブラリGNU MPには平方数かどうかを判定するmpz_perfect_square_p関数が存在します（PHPでもgmp_perfect_square関数として利用できます）。本稿ではこの実装
はてなグループの終了日を2020年1月31日(金)に決定しました - はてなの告知
はてなグループの終了日を2020年1月31日(金)に決定しました 以下のエントリの通り、今年末を目処にはてなグループを終了予定である旨をお知らせしておりました。 2019年末を目処に、はてなグループの提供を終了する予定です - はてなグループ日記 このたび、正式に終了日を決定いたしましたので、以下の通りご確認ください。 終了日: 2020年1月31日(金) エクスポート希望申請期限:2020年1月31日(金) 終了日以降は、はてなグループの閲覧および投稿は行えません。日記のエクスポートが必要な方は以下の記事にしたがって手続きをしてください。 はてなグループに投稿された日記データのエクスポートについて - はてなグループ日記 ご利用のみなさまにはご迷惑をおかけいたしますが、どうぞよろしくお願いいたします。 2020-06-25 追記 はてなグループ日記のエクスポートデータは2020年2月28
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
競技プロ的なアルゴリズムのスライドのまとめ Wiki - yukicoder
Home — Memory Management Reference 4.0 documentation
マルチコア時代のLock-free入門
A collection of links for streaming algorithms and data structures
