プログラム
Number MindをMCMCで解いてみた。 方針は与えられた数sに対して、評価関数c(s)を真の正解の数との二乗誤差とおく。今状態sから状態tへの遷移確率を とおいて遷移していく、これを繰り返していくと に従ってsをサンプリングすることができ、c(s)が低いものほ…
Code Jam 2008の日程が決まったようです。 Qualification Roundが7/17(木)の08:00(GMT+9)から7/18の08:00までで、7/25-31までのどれか都合のいい日を選択という形でRound 1が行われる。 Round 1は最高2回まで参加できて、全体で2520人がRound 2に進める．そ…
先週あたりから解きだしてみた、現在120問解いた。
珍しくC++のコードを書いていたら次のようなコードを書いてはまった。 #include <map> #include <iostream> using namespace std; struct A{ int size; A(int s) : size(s){} }; map<char , A*> m; void f(){ A a(3); m['a'] = &a; cout << m['a']->size << endl; } int main(){ f(); c</char></iostream></map>…
上の研究会でMeCabを使ってAUtolinkを実現する話が出ていたので実際に実験してみた. MeCab の辞書構造と汎用テキスト変換ツールとしての利用を参考にした． 置換するキーワードリストとしてはWikipediaの記事タイトルを用いた.記事タイトルはダウンロードサ…
ハル研 コンテスト参加してみた． なんかいろいろやってみたけど結局最初に書いたのが一番早い．P.S 家に帰ってすこしいじったら圧倒的に早くなったと思ったら，単に-O4がかかってただけだった，ということはかなり効率の悪い書き方をしているということだろ…
某所のO(1)とか言うプログラムの結果が手元のgccで計算するとfib(71)以降の結果が一致しない．誰も指摘してないから処理系によるのかな．
少しSQLの勉強をしてるので，練習に今年の国内予選BをSQLでといてみる．まず，利用記録は下のようにloginテーブルに格納されているものとする time(時間) pid(pc番号) sid(学生番号) in(1:ログイン, 0:ログアウト) 775 1 1 1 780 4 2 1 790 2 1 1 800 2 1 0 …
すずかけ台までは電車で往復2時間近くかかるのでコンテストの問題を印刷して電車の中で考えてた．で今日実装してたけど紙の上で考えるのと実際にやるのはずいぶんと違った． 電車で思った感想 A やるだけ B やるだけ C DP D 未知のパラメータが6つあって，拘…
メモ 来月あたり研究室にQuad Coreのマシンが来るので，OpenMPっぽく簡単にループ等を並列化してくれるJavaのライブラリを探してたところParallel Java Libraryとかいうものを見つける．やってくれることは下のような逐次のコードを //seq for (int i = 1; i …
TopCoderのアルゴリズム部門のアクティブな日本人参加者の参加時期に関する累積部門をグラフにしてみた．データはDataFeedで取ってこれるものを利用した．具体的にはActive Algorithm Coder Listで日本人のCoderリストをとってきて個々のAlgorithm Rating Hi…
JFreeChartというjavaのチャートを書くためのライブラリを使ってみた．基本的にはTopCoderのRating Historyで他人のレートの動きも重ね合わせたいなと思うことがあってそういう機能はついてないようだったので自分で作ることにした．日付と値を指定すると簡…
Favorite APIをもちいてはてブの人気エントリの上位500までの記事を書いているユーザ間のつながりをPajekで可視化した． グラフの大きさはノード数178，エッジ数462となった． できた画像はhttp://www.stat.t.u-tokyo.ac.jp/~tsubosaka/img/hatena.gif Pajek…
Favorites APIからお気に入りユーザの一覧を取得してグラフとして可視化するプログラムを作ってみた． Main.javaがエントリーポイントで引数にuserIdを与えるとそのユーザをノードとして表示する．クリックするとつながってるユーザをひっぱってきてグラフに…
行ってきた．13:00頃に着いたら200人ほど入る会場がいっぱいになっていた．低価格で高並列計算ができるというのにかなり多くの人が興味を持っているよう．あと受け付けに大量の名刺があったので外部から聞きに来ている人が結構多かったみたい．話自体は結構…
http://tech.puredanger.com/java7でJava 7の概要を読んでた． 普通に便利そうなのが Strings in switch statements Comparisons for Enums JavaBean property support More Script Engines BigDecimal operator support Java Media Components(追加，という…
いま大きめのネットワーク*1に対して，解析をしてるんですが，ノートPCではメモリにデータがのらないのでDBつかってごまかしながら作業してたんですが，よくよく考えるとなんのために家のデスクトップに2Gも積んでるのかと思いそっちで作業したら100倍ぐらい…
時間，空間計算量が小さいアルゴリズムがあるならそっちを使いましょう． 複数ケースがある場合は配列をとったときにGCが間に合わない時があるのでSystem.gc()を呼ぶ．このばあいTLEになる可能性があるのでその辺はヒューリスティックに． Inputが大きいとき…
java.lang.Integer.valueOf(int)の実装は public static Integer valueOf(int i) { final int offset = 128; if (i >= -128 && i <= 127) { // must cache return IntegerCache.cache[i + offset]; } return new Integer(i); } SE5以降上のようになっている…
http://www.linux.or.jp/JF/JFdocs/XML-RPC-HOWTO/xmlrpc-howto-intro.html#XMLRPC-HOWTO-SPEC本当に予想以上に速かった．
数理科学図書館で借りたい本があったので，久々に駒場に行く．図書館のあたりがカフェテリアとかができて，相当様変わりしてた．本郷とは違って，授業の空きのため，そのあたりをぶらついている人たちとか*1，授業の間で人が大量に移動するとことか，駒場東…
上位300名まで通過でDivision Place 290位だからたぶん通った．しかし，今回もぎりぎりで通過だとは． 250 Greedyでいいんじゃないのと思って実装．200ptゲット．しかし，その後よく問題を見返すと引数の配列のサイズは0も含むと書いてある．0インデックスに…
http://download.wikimedia.org/からダウンロードできるXMLファイルからタイトルとそのタイトルからのリンク(今のところリンクというよりも［［*］］の部分)を取り出すプログラム追記： とりあえず，タイトルにauto_incrementなIDをつけてDBに吐いたのだが，…
今日，大規模ネットワークの可視化という話の中で，ノードの相互作用のO(n^2)の計算を，これを利用することにより100倍近い速度で実行できるということを聞いた．値段はアカデミック版で\120万，Pen4×100と同じぐらいの値段だから妥当と言えば妥当だと思う．
半日，プログラムを書いててeclipseのコードアシストが利いてなかったことに今気づいた．そりゃ補助なしに$bean->getLongLongName()とか打ってれば作業速度が遅れるのも当然か．
http://acm.pku.edu.cn/JudgeOnline/problem?id=2631 与えられた重みつきグラフの直径を求めよという問題．ただし，グラフは木である．なお，グラフの直径とはグラフの任意の点対の最短距離の中の最も大きい値のことをいう．Floyd-Warshallとかは計算量的に…
Javaの言語仕様によると，配列に対してのインデックスはint値しか許されておらず，longをインデックス値とするとコンパイル時のエラーとなる．ただ，これって32bit環境の時は当然の制約だけど，OSの環境が64bitになって，PCにメモリを8GBとか乗せることも可…
今日解いた問題はhttp://acm.pku.edu.cn/JudgeOnline/problem?id=24111×2のタイルでh×w(h,w再帰的に全探索する．ただし，h段目を埋めるときにはh-1段目のタイルの形状だけに注目すればよいので，メモ化が効いてmax(h,w)*(2^min(h,w))ぐらいの記憶領域を用い…
ゼミが休みになったので少し解く．とりあえず順位をひとつあげる．とりあえず100位と34問差があるので当分2ページ目には載れそうだが，あと100解いてもまだ2ページ目なんだよな．解いた問題は以上 http://acm.pku.edu.cn/JudgeOnline/problem?id=3117 http:/…
http://acm.pku.edu.cn/JudgeOnline/problem?id=3193java補正がかかるので，単にソートして二分探索するだけ．以下ソース
