valarray

C++ code

最近サポートベクタマシンや、クラスタリングを適当に組んだりするときに、3次元以上の点を表すのにちょうどいいデータ構造として、valarrayを使っていた。valarrayは算術演算が定義された配列みたいなイメージで雰囲気で使っていたのだが、初期化周りのこと…

2007-10-28

銚子に行ってきた

misc

そう、あの千葉の東のやたらとんがったところに行ってきた。 270度ぐらい海が見えるのだが、まぁ残念なことにカメラでは130度ぐらいが限界だった。まぁ人間でも180度ぐらいだけど・・・。台風が過ぎた後だったのですごいきれいに日没も見ることができた。

2007-10-19

OBOG模擬地区大会参加者

ICPC

とりあえずこれを見て欲しい。 2007/Practice/模擬地区予選/参加受理チーム一覧 - ACM-ICPC Japanese Alumni Group上海交通・・・・鬼過ぎる。

2007-10-18

REP解禁!!

TopCoder code

#define REP(i,n) for (int i = 0; i < n; ++i) ついに使ってしまった。バッドノウハウとか言われてるから使わないでいたけど、TopCoderで見る限り書くのだけでなく読む方もforでかかれてるより読みやすい。特に数学系の式のケースだともうREPがシグマ記号…

2007-10-16

範囲更新データ構造(改良版)

Algorithm code

この前のは同じ色が連続してしまう可能性があったが、ちょっと考えれば防げるんじゃないかと思ってコードを書き直してみた。これでconnectがいらなくなった。"upper_bound(x)"は「xより上」のxに最も近い値を指すイテレータを返すので、"--upper_bound(x)"が…

2007-10-13

範囲更新データ構造

Algorithm code

色塗り問題を解くデータ構造を勉強してみた。 Makegumiライブラリを参考にさせていただいて、何やっているか理解し、改めて自分で書いてみた。Makegumiには合宿3日目の最大流のときから本当にお世話になっている。 fromの情報だけあればtoの情報が要らなくな…

2007-10-11

アジア予選そろそろだなぁ。

ICPC

アジア予選のスケジュールも発表されて、チーム紹介とかもin Englishで書かないといけなかったり、エクスカーションに行くかとかも決めないといけない。まぁチーム紹介はk君に任せればいいでしょう。なんかこんなこと言ったら良くないのかもしれないけど、…

2007-10-10

二部グラフの最大マッチング＝最小頂点被覆

Algorithm

nyaasanに教えてもらった「最大流-最小カット定理」を使うということを元に、昨日わからなかった二部グラフにおいて最大マッチングが最小頂点被覆と等しいということを証明してみようと思う。正直これを聞いても自分の中で納得するまでに大分時間かかってし…

2007-10-09

最大マッチングと最小頂点被覆

Algorithm

二部グラフにおいて最大マッチングと最小頂点被覆は等しいらしい。実際にいくつかの例で試してみたら確かにそうなるから正しいんだろう。でも理由がわからない。そもそもこの事実は二部グラフ以外でも成り立つのだろうか。誰か教えてください。まじめに。

2007-10-08

二部グラフの最大マッチング

Algorithm code

考察タイム終わった後実際に簡単な4問は解いてみた。 PKU2060で初めて最大流量を使わない2部グラフの最大マッチングのコードを書いた。Web上にメモっとこ。 typedef vector<vector<int> > graph; struct BGM { int L, R; //左右のノード数 graph g; vector<int> r2l; //右->左</int></vector<int>…