たのしいメトロポリス法のメモ - 穴日記
適当なメモなので間違っていたら突っ込んでください Metropolis法でレンダリングするのが最近ますます流行っているらしいです。SIGGRAPH2012のQuasi-Monte CarloのコースでもMetropolis Light Transportとかが話題になってたみたいです。 https://sites.google.com/site/qmcrendering/ さて、よく聞くMetropolis法とは実はただのサンプリング手法でしかありません。手元の「パターン認識と機械学習 下巻」でも「第11章 サンプリング法」のところで出てきます。これによると、Markov Chain Monte Carlo（いわゆるMCMC）というのは最初物理学に起源があり、Metropolis先生とかが開発したそうです。 Metropolis法とはマルコフ連鎖モンテカルロによってある確率分布pに従うラン
はてなブログ | 無料ブログを作成しよう
25,Summer color 1 … みちのく初夏の記 ・「 チャグチャグ馬コ 2025」 Snapshot 風物詩 【 チャグチャグ馬コ 】 挨拶をありがとう…今日は頑張ってね！暑いから休み々…。 美しい瞳…南部駒の魅力の一つ。 BGMはもちろんこの曲…♬♬♬ www.youtube.com 南部美人の横顔に魅かれます。 今日はまかしといて～っ…頼もしくも可愛らしいね、元気に育て…
情報オリンピック夏季セミナーの参加記一覧とか - 簡潔なQ
2012/08/25 - 08/29の間、夏季セミナーというのにチューターとして参加していました。以下はその記録として参照できる各種媒体へのリンクです。 募集案内 実施の概要 参加者のtwitterリスト 発表会の様子(Togetter) その1 その2 その3 その4 その5 slideshare 『確率と計算 ―乱択アルゴリズムと確率的解析―』 (2) @nullmineral ARC #003 D「シャッフル席替え」の乱択アルゴリズムによる解法の解説 (4) @hyksm 乱択アルゴリズムでK-th numberを解く (5) @HziwarA 最小全域木に対する乱択アルゴリズムの評価 『抽象によるソフトウェア設計-Alloyではじめる形式手法』 (1) @sugspi_c Alloyさん (2) @everysick Alloyでハミルトン閉路 (3) @ichigo_o_re A
情報オリンピック夏季セミナー(2012) 発表会 その1
情報オリンピック夏季セミナー http://www.ioi-jp.org/seminar/2012/summer-semi.html で高校生・高専生が4日間のゼミで学んだことの発表会の記録 まとめ その1 http://togetter.com/li/363651 『確率と計算 ―乱択アルゴリズムと確率的解析―』 まとめ その2 http://togetter.com/li/363672 『抽象によるソフトウェア設計-Alloyではじめる形式手法』 まとめ その3 http://togetter.com/li/363694 『Introduction to Algorithms』 続きを読む
はてなグループの終了日を2020年1月31日(金)に決定しました - はてなの告知
はてなグループの終了日を2020年1月31日(金)に決定しました 以下のエントリの通り、今年末を目処にはてなグループを終了予定である旨をお知らせしておりました。 2019年末を目処に、はてなグループの提供を終了する予定です - はてなグループ日記 このたび、正式に終了日を決定いたしましたので、以下の通りご確認ください。 終了日: 2020年1月31日(金) エクスポート希望申請期限:2020年1月31日(金) 終了日以降は、はてなグループの閲覧および投稿は行えません。日記のエクスポートが必要な方は以下の記事にしたがって手続きをしてください。 はてなグループに投稿された日記データのエクスポートについて - はてなグループ日記 ご利用のみなさまにはご迷惑をおかけいたしますが、どうぞよろしくお願いいたします。 2020-06-25 追記 はてなグループ日記のエクスポートデータは2020年2月28
第12回アルゴリズム勉強会に行ってきました - アスペ日記
人生初勉強会。 やったのは counting sort と radix sort。 この二つは書いたことがなかったので、Python で超手抜きに書いてみた。 https://gist.github.com/1395308 base = 10 def radix_sort(x, max): radix = 1 while radix < max: x = counting_sort(x, radix) radix *= base return x def counting_sort(a, radix): c = [0] * base for k in a: r = (k / radix) % base c[r] += 1 for i in range(1, base): c[i] += c[i - 1] b = [0] * len(a) for k in reversed(a): r =
動的計画法とナップサック問題を学びたい人におすすめのサイト - ダウンロードたけし（寅年）の日記
組み合わせ最適化の手法として「動的計画法」というモノがあります。 wikipediaから抜粋 動的計画法（どうてきけいかくほう、英: Dynamic Programming, DP） コンピュータ科学の分野において、ある最適化問題を複数の部分問題に分割して解く際に、そこまでに求められている以上の最適解が求められないような部分問題を切り捨てながら解いていく手法 一見難しそうですが、実は理解するのは以外と簡単です。いろいろな場面で応用が利く便利な手法ですので、覚えておいて損はないものです。コンピュータ系、情報系のお勉強をする人であれば、おそらく一度は習ったりするかもしれません。 ナップサック問題と動的計画法 動的計画法の一番親しみやすそうな例として「ナップサック問題」というのがよく取り上げられます。 こんな感じの問題です。 今ここに様々な大きさの品物が置いてあるとします。そしてそれらの品物は各
ALGORITHM NOTE ナップザック問題 Knapsack Problem
大きさ w と価値 v を持った品物が N 個あり、これらを大きさ W のナップザックに入れたいとします。このとき、大きさの合計が W を超えず、価値の合計が最大になるような品物の組み合わせを求めたい。これがナップザック問題です。各品物を「選択する」か「選択しない」かの組み合わせなので、厳密には0-1ナップザック問題ともいいます。(各品物が複数個ある場合は、0123ナップザック問題と呼ばれます) この問題を力任せで解こうとすれば、N 個の品物を「選択する」か「選択しないか」の全組み合わせを全て調べることになるので、計算効率は O(2N) となります。N が数十個でも、実用的な時間では計算できません。 品物の大きさ w、ナップザックの大きさ W がともに整数であれば、ナップザック問題は動的計画法により O (NW) の効率で厳密解を求めることができます。 C[i][w] が、大きさ w のナ
Leonhard Gruenschloss
Quasi-Monte Carlo (QMC) Samplers Halton A very fast C++ implementation of the Halton sequence that supports both Faure-permutations and random digit permutations. Together with the component (i / N) this will yield a Hammersley point set. Comes with a Python script to generate optimized code for arbitrary dimensions. It also includes code to enumerate samples in a 2D domain, for example pixels. MC
嘘解法のススメ - てきとーな日記
（この記事は Competitive Programming Advent Calendar の 18 日目の記事として書かれました．まだ18日です！セーフ！！！） 自分はICPC時代によく嘘解法を駆使して問題を解いていたので（ジャッジの方々ごめんなさい），よく使われる嘘解法テクニックを紹介したいと思います． これらのテクニックはマラソンマッチのようにそもそも最適解を求める必要のないコンテストにおいても活用できます． 嘘解法とは プログラミングコンテストにおいては，ジャッジの用意した入力データに対し，正しい答えを出力できれば正答とみなされます． このため，正しくない解法（嘘解法）が通ったりすることがときどきあります． しかし一般に嘘解法で通ることはあまりなく，嘘解法を試すのは終盤まで控えるべきです． 残り時間が少なく今から正しい解法を考える・実装するのは無理だという場合の最終手段と考えてく
文字列検索（直感的な文字列検索とKMP法）
文字列に対する検索 以前、表の中からある特定の値を持つデータを探し出す「探索 」を学習しましたが、そのときは「このキーをもったレコードを探し出しなさい」と指示しました。 では、文字列の場合はどうなるのでしょうか？ 文字列の検索では、文字の並びが重要なので、「文字abcがこの順番に並んだ場所を探し出しなさい」というように指定します。 ここで、「探したい文字の並び」のことをパターンといいます。 今の例は「パターンabcを探し出しなさい」と言い換えることができます。 また、検索される文字列のことをテキストと呼びます。 つまり、文字列の検索とは、「テキスト中で指定されたパターンが出現する場所を見つける操作」と定義することができます。 力まかせのアルゴリズム 文字列の検索を行うのに、真っ先に思いつくのは、次のようなアルゴリズムでしょう。 まず最初にテキストの先頭にパターンを重ね合わせます。
はてなグループの終了日を2020年1月31日(金)に決定しました - はてなの告知
はてなグループの終了日を2020年1月31日(金)に決定しました 以下のエントリの通り、今年末を目処にはてなグループを終了予定である旨をお知らせしておりました。 2019年末を目処に、はてなグループの提供を終了する予定です - はてなグループ日記 このたび、正式に終了日を決定いたしましたので、以下の通りご確認ください。 終了日: 2020年1月31日(金) エクスポート希望申請期限:2020年1月31日(金) 終了日以降は、はてなグループの閲覧および投稿は行えません。日記のエクスポートが必要な方は以下の記事にしたがって手続きをしてください。 はてなグループに投稿された日記データのエクスポートについて - はてなグループ日記 ご利用のみなさまにはご迷惑をおかけいたしますが、どうぞよろしくお願いいたします。 2020-06-25 追記 はてなグループ日記のエクスポートデータは2020年2月28
はてなグループの終了日を2020年1月31日(金)に決定しました - はてなの告知
はてなグループの終了日を2020年1月31日(金)に決定しました 以下のエントリの通り、今年末を目処にはてなグループを終了予定である旨をお知らせしておりました。 2019年末を目処に、はてなグループの提供を終了する予定です - はてなグループ日記 このたび、正式に終了日を決定いたしましたので、以下の通りご確認ください。 終了日: 2020年1月31日(金) エクスポート希望申請期限:2020年1月31日(金) 終了日以降は、はてなグループの閲覧および投稿は行えません。日記のエクスポートが必要な方は以下の記事にしたがって手続きをしてください。 はてなグループに投稿された日記データのエクスポートについて - はてなグループ日記 ご利用のみなさまにはご迷惑をおかけいたしますが、どうぞよろしくお願いいたします。 2020-06-25 追記 はてなグループ日記のエクスポートデータは2020年2月28
二分探索の話 in icpc直前会議
Statistics Favorites 1 Downloads 0 Comments 1 Embed Views 0 Views on SlideShare 110 Total Views 110 二分探索の話 in icpc直前会議 — Presentation Transcript ⼆二分探索索の話@hama_duICPC国内予選直前対策会議 in チームラボ(⼀一部修正を加えてます。) こんにちは。¤ @hama_du ¤ 「はまづ(ず)」と読んでね ¤ 修⼠士２年年¤ ICPC出場経験 ¤ ⼈人間⼒力力なくてチーム作れなかったのでなし！ ¤ (国内予選にすら参加してない) ¤ ⾃自⼤大学をひいきするため活動中¤ その他、主なプロコンの成績 ¤ Topcoder : 1606(SRM) / 1703(MM) ¤ Codeforces : 17
動的計画法は再帰で表せ
動的計画法の説明は常に再帰関数で書き表すことにしています．いやゆるメモ化再帰です．参照透過な関数は，同じ引数に対して同じ値を返すので，保存しておけばいいという感覚です．計算量の見積もりも簡単で，引数の異なり数に関数中のループの上限をかければおしまいです．特に再帰で書くことに慣れていれば自明に書けますし，テーブルを使ったDPと違って，ループの順番を意識する必要がありません．このテクニックは学部時代に@ohkuraに教えてもらいました．関数型言語に触れた今でこそ当たり前に見えますが，当時は目から鱗だったのを覚えています． メモ化再帰と不動点に関する@kinabaさんの日記や，プログラミングコンテスト的には@chokudaiさんの記事が参考になります． 今更ですが，ちょっと例で説明します．フィボナッチ数を計算する関数fib(x)は再帰式で，fib(x) = fib(x - 1) + fib(x
プログラミングコンテストでの乱択アルゴリズム - iwiwiの日記
DeNA 主催の TopCoder メンバー交流イベント "TopCoder Meetup in Japan" で「プログラミングコンテストでの乱択アルゴリズム」というタイトルで話をさせてもらいました． プログラミングコンテストでの乱択アルゴリズム View more presentations from iwiwi 乱択アルゴリズムは，プログラミングコンテストで頻出のトピックとは少なくとも今は言いがたいですが，今年の Google Code Jam で急に 2 問も出題されたことを中心に，ちょくちょく出始めています．少し体系的に議論できるぐらいには問題がたまってきたかなというのと，もしかしたら更に流行るこれからに備えることができるかなということで，乱択アルゴリズムを題材に選びました． イベントではそのほか，DeNA の会社紹介，立食スタイルの交流会，副島さん (=rng_58) への 1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
最強最速アルゴリズマー、情報オリンピックの問題を一刀両断？「脳内で解いたけど、たぶん簡単」→勘違いだったことがわかり解決
Page Not Found
アルゴリズムイントロダクション15章 動的計画法
http://www.kupc.jp/editorial.html