code
Google Code Jamの関係で、多倍長演算クラスを作ってみた。 JavaのBigIntegerと比べて格段に見劣りするし、確実にgmpxxを使った方がいいし、自分は本番Python使って全く困らなかったけど、それでもライブラリなしでコピペしてC++で解きたいときに。 constと…
Cabocha 0.6 pre系列はインターフェースが変わったので、取得できるものを全部列挙する感じで組んでみた。 #include <iostream> #include <string> #include <cabocha.h> using namespace std; //How to compile? //g++ -O2 `cabocha-config --cflags` cabochasample.cpp -o cabochasample</cabocha.h></string></iostream>…
O(n)のはず。 結構昔に作ったものだけど、ブログにメモとして載せとく。 確か、アルゴリズムデザインって本を参照したはず。 #include <iostream> #include <vector> #include <ctime> #include <cstdlib> using namespace std; int select(vector<int> S, int k) { int n = S.size(); int i = rand(</int></cstdlib></ctime></vector></iostream>…
チョイ暇だったので、30分ぐらいで作ってみた。本当はディスク使うからこんな風にstlのvector使ってやればいいってもんじゃないんだけど・・・。 検証してないから間違ってるかもしれない。 詳しい解説は・・・後で書くかもしれない。 実装的にはTrustRankと…
http://www.topcoder.com/stat?c=problem_statement&pm=1779&rd=4575 簡易NFSA(非決定性有限オートマトン)を作る問題。 実際自分は適当にfor文でごり押ししたら通っちゃったけど、ほかの人のソース見てきれいなのがあったから、今後のために書いておく。 ま…
inputデータをファイルから読み込むときに使う雛形。 プラクティスセッション中にファイルからの入力ができないチームが結構いたおかげで改めて考え直すきっかけになった。来年からは主催者側が「ファイルからのインプットをできるようにしてきましょう。」…
最近サポートベクタマシンや、クラスタリングを適当に組んだりするときに、3次元以上の点を表すのにちょうどいいデータ構造として、valarrayを使っていた。valarrayは算術演算が定義された配列みたいなイメージで雰囲気で使っていたのだが、初期化周りのこと…
#define REP(i,n) for (int i = 0; i < n; ++i) ついに使ってしまった。バッドノウハウとか言われてるから使わないでいたけど、TopCoderで見る限り書くのだけでなく読む方もforでかかれてるより読みやすい。 特に数学系の式のケースだともうREPがシグマ記号…
この前のは同じ色が連続してしまう可能性があったが、ちょっと考えれば防げるんじゃないかと思ってコードを書き直してみた。これでconnectがいらなくなった。"upper_bound(x)"は「xより上」のxに最も近い値を指すイテレータを返すので、"--upper_bound(x)"が…
色塗り問題を解くデータ構造を勉強してみた。 Makegumiライブラリを参考にさせていただいて、何やっているか理解し、改めて自分で書いてみた。Makegumiには合宿3日目の最大流のときから本当にお世話になっている。 fromの情報だけあればtoの情報が要らなくな…
考察タイム終わった後実際に簡単な4問は解いてみた。 PKU2060で初めて最大流量を使わない2部グラフの最大マッチングのコードを書いた。Web上にメモっとこ。 typedef vector<vector<int> > graph; struct BGM { int L, R; //左右のノード数 graph g; vector<int> r2l; //右->左</int></vector<int>…
ちょっと二分探索の挙動で気になったことがあったので書いておく。挙動というのは指定した値が見つからなかった時や同じ値が複数存在した時にどうなるかということだ。配列内を探索するならSTLのlower_boundとupper_boundを使えばいいだけの話なのだが、最近…
ちょっと他人のコードを読んでいてなるほどと思ったからメモ。 これで少しハードコーダーを脱せるかもしれない。２次元の探索問題でよく自分の上下左右を探索したい時がある。これを普通にコーディングするとどっかで下のような感じになっているはずだ。 dfs…
