この記事は、Competitive Programming Advent Calendarの２５日目用に書かれたものです。 はてなダイアリーの容量制限のため、３記事に分割して投稿してあります。 （１）　__________の　ＩＣＰＣアジア地区予選２０１１参戦記　No.1/3 （２）　__________の　ＩＣＰＣアジア地区予選２０１１参戦記　No.2/3 （３）　__________の　ＩＣＰＣアジア地区予選２０１１参戦記　No.3/3

This particular audibilization is just one of many ways to generate sound from running sorting algorithms. Here on every comparison of two numbers (elements) I play (mix) sin waves with frequencies modulated by values of these numbers. There are quite a few parameters that may drastically change resulting sound - I just chose parameteres that imo felt best. After making this video I found that so

前に書いていた奴をまとめて prezi にしてみた。 http://d.hatena.ne.jp/rti7743/20100418/1271603136 svm数式を一切使用しないSVMの話 on Prezi

情報オリンピックの春合宿で担当した講義のスライドをアップロードしました． プログラミングコンテストでの動的計画法 プログラミングコンテストでのデータ構造 講義は動的計画法についてとデータ構造についてで，それぞれ独立しています． 動的計画法については，動的計画法のアルゴリズムを導くにあたっての非常に基本的な部分について話しています．動的計画法がよく分かっていない人や，苦手な人にオススメ． データ構造については，Union-Find 木，バケット法，セグメント木について話しています．特に，バケット法やセグメント木の話は，中上級者向けですが，世の中の資料がかなり少ないので，活用されることを期待します． 講義を受け持つのははじめてで不安でしたが，生徒さん達に褒めてもらえたりもしていて嬉しいです． http://twitter.com/tozangezan/status/10718667041 ht

SATソルバっていうのは，充足可能性問題（SATisfiability problem）を解いてくれるソフトウェアのことで，SATソルバで数独を解くとか，以外と身近なところに応用があったりします．SATソルバは数独を解くだけじゃなくて，プログラムの停止性の判定に使うとか，いろいろな応用を考えることができる良いものです．普通，SATソルバはCNFという論理式の特殊な形を取り扱います．日本語だと乗法標準形とか言うらしいですけど，別にこの言葉は忘れても良いと思います．詳しくはWikipediaでも見てもらえれば良いのですが，CNFは，変数かそのnot付けたやつ，をorで結んだやつ，をandで結んだやつ，という意味です． CNF ::= c1 && ... && c2 c ::= l1 || ... || l2 l ::= x | !x 任意の論理式(変数(x)とor(||)とand(&&)と「な

ちまたの競馬予想会社のうさん臭さは、「そんなに儲かるならなぜ自分で買わない」という言葉で表されるが、ほんとに儲かる人間はやはり自分で馬券を買っていることを証明した事件だと言える。 asahi.com（朝日新聞）が競馬の配当１６０億円隠す　英国人社長のデータ分析会社という記事を報じているが、新聞紙面ではその隣に関連記事も掲載されているので、これを引用する。 「なぜそんなに稼げた - 3連単を分散買い」（2009年10月9日付朝日新聞より） ユープロ関係者らによると、同社は、天候や出走馬の血統、騎手などの各データを入力、解析する競馬必勝プログラムを使い、高確率で配当金を得ていたという。だが、億単位の資金を使い、ほとんどの組み合わせの馬券を買うという、一般の競馬ファンにはまねできないやり方だった。 05年設立の同社が目をつけたのは、「3連単」という馬券。1着から3着までを順番通り当てるもので、配

今日のInterpolative codingの話が面白かったのと復号の部分のコードが必ずしも自明ではないかと思ったのでメモ。 Interpolative codingは長さと出てくる値の最小値、最大値が分かっている狭義単調増加な自然数のリストを圧縮する方法である。 ここで最大値とはリストの最大値ではなく、たとえば転置リストであれば最大の文書IDなど圧縮を行う際に出てきうる値の最大値である。 Interpolative codingの基本的な考え方としてはたとえば1から20までの数が表れるとわかっておりかつリストの長さが20であるということが分かっていれば、なにもデータがなくてもリストが[1..20]であるとわかるということに基づいている。 ここでは例で説明する。長さ7のリスト<7;3,8,9,11,12,13,17>を圧縮することを考える。またここで出てくる数の最大値は20であることが分

以前JavaScriptのGoogleMapsを使って書いた「東京を走る路線のデータを使って、最短経路問題をダイクストラ法で解く」はたくさんブックマークついてうれしかったんだけど、その中でもid:nitoyon氏が「１サイクルごとにアニメーションしてほしい！」と書いてくれたのがずっと気になっていた。 作ったの結構前のことなのでダイクストラ法がどういうアルゴリズムなのかさえも忘れてしまう俺にとっても、アニメーションするとわかりやすくていいかも…と思って手を出してみた。 502 Bad Gateway 出発駅と目的駅を入力して検索ボタンで最短経路を検索 計算中の赤い線が最短経路が確定したルート、緑の線が確定してはないけど距離が更新されたルート 以下いいわけとか： 今回はGoogleMapsAPIのFlash版を使ってみた。なんかFlex2SDKが公式ページからダウンロードできなかったり、Goo

SAT solver が周りでほのかに流行っている(いた?)ので，個人的には SAT solver よりも断然便利な SMT solver について書いてみようと思いたった． SMT って? SMT は Satisfiable Modulo Theories の略で，SAT だと命題変数を並べて CNF で記述しなければいけないところを，int とか，プログラムで使うような変数が扱える上，述語が使える． なので一般に記述量が減り，人間に(SAT問題よりは)読みやすくなる傾向にあると思う． SMT Solver SMT Solver については http://combination.cs.uiowa.edu/smtlib/ でいろいろ見つかるけれど，ここでは The Yices SMT Solver を使ってみる． 環境準備 Mac OS X Leopard Yices 4.2.2 例題 S

新年すっかりあけてました。 今年もよろしくお願いします。 年末年始はドタバタして昨年を振り返られなかったのですが、せっかくなので2008年に読んだ論文で私個人のベスト５を以下に列挙してみます。 D. Sontag, et. al. "Tightening LP Relaxations for MAP using Message Passing", UAI 2008 [pdf] Graphical ModelのMAP推定問題で従来解けなかった規模の複雑さの問題を高速にしかも最大であるという保障付きで解けるようにした。書いたメンバーはこの問題に関するオールスターのような感じ。解く問題は、n個の頂点からなるグラフで、各頂点には変数x1...xnがついていて、各頂点と各枝に対し関数gi(xi)、gij(xi,xj)が与えられた時、∑i gi(xi) + ∑ij gij(xi,xj)が最大となるよう