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

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

今日は6人中3人しか集まらずに個人で解く事に。しかもただ個人戦で競っても簡単な問題だけ解いて終わってしまうから、時間内にはコード書かずに問題の解き方を考えるところまででやめるというルールでやってみた。 問題セットは東大の過去の練習会に使われて…

Statisticsが画期的な円グラフで表示される！！ いつもFireFoxで見てたから気づかなかった。無駄にがんばってるな。 最近PKUの改良が目覚しい。何でこんなやる気を出したのだろう？ソースコードの色分けがされるようになってSubmitしたソースがやたらと見や…

人生最低点をとってしまった。-25点。 250点問題でローカルでテスト通ってからSave,Compile,Submitするのに15分もかかってしまった。自分のネット環境が悪いのか、向こうのサーバーが悪かったのか良くわからない。しかもなんかが0の時の対処をし忘れて撃墜さ…

1398で青色コーダーになりました。 てか、俺がDiv1での一番簡単な問題をばっちりミスってる間ににゃあさんはDiv1でトップを取っていたようで。すごすぎる。

B3ながら山名研ゼミに参加してきた。まだ申請書が通ったわけでもないのに普通に出席までとってもらった。 ゼミの発表は中国語構文解析の手法の論文紹介をしていたっぽかったんだけど、正直何がすごいのか良くわからなかった。 結局、自由文脈文法って何だっ…

TopCoder初参戦。Div2はやたらと簡単で1時間もしないうちに3問解き終わってうはうはしてたら、ばっちりChallange PhazeでChallangeされてしまった。ミスは、再帰で全探索してるのに再帰抜ける時に、--visitedを書くのを忘れた。てかこれでなんでサンプル通っ…

TopCoderでCodeProcessor+TZTester+FileEditを元にエディタだけ設定してみた。まだ一度もTopCoderやったことないのにこんなことやって大丈夫なのかは知らない。これでエディタ環境はこれ以上ない状況ができているはずなので、今後自分のレートの上下は完全に…

WeTECとか言うわけのわからない英語力判定テストを受けた。一年の入学したてのときよりも点数が落ちてしまった・・・。明らかに単語力とリスニング力は落ちている。うすうす感じてはいたけど、現実をたたきつけられるとやっぱショック・・・。

ICPC関係の人の間でTopCoderがはやっているみたいなのでちょっと興味を持った。いろいろTopCoderのサイトを見てみたので使えるページをメモっておこうと思う。 まず、参加するためには欠かせないコンテストスケジュール。 http://www.topcoder.com/tc?module…

ちょっと二分探索の挙動で気になったことがあったので書いておく。挙動というのは指定した値が見つからなかった時や同じ値が複数存在した時にどうなるかということだ。配列内を探索するならSTLのlower_boundとupper_boundを使えばいいだけの話なのだが、最近…

反省 とりあえずこのOBOG合宿でわかったことは 本の最後のほうに出てくるようなアルゴリズム問題 幾何問題 数学問題 がうちらは弱いってこと。 1.については、さすがに最近は聞いたこともないというようなのは減ってきたけれど、実際に問題に出会ったことが…

今日端末室スケジュールを見たら、我らが聖地であるUNIX端末室がほとんどうまっている・・・。せっかく今期は授業少ないのに・・・。 練習どこでしよ・・・(´・ω・｀)

さっき帰ってきた。 ・・・疲れた。とりあえず、二日目にがんばりすぎた。5時間に6問解けたのは初だったし、同じ量解いてもうちらの頭脳の消耗量は他のチームの10倍ぐらいな気がした。 そして結局三日目に予定通りの最下位を取ってしまった。特に三日目のは…

明日からICPCのOBOG合宿に行ってきます。 国内予選の順位が10位まで誘ってもらったみたいなんで、参加者の中でうちらが最下位。これはもうがんばるしかない！！しかもプログラムを組むようになったのは大学生からだからプログラム経験年数からしても、最下位…

結構いい線いったんだけど、一部答えが合わず、結局解けなかった。いろいろ検索しながら調べてたら中国剰余定理使うっぽいなぁというとこまではたどりついたんだけれども・・・。 純粋関数型雑記帳でtanakhさんが書いてた通り、うまく計算できてなくてlong l…

この問題よく読むとPKU2976 Dropping testsと考え方同じじゃん！ 答えをXと置いて、それぞれの経路の重みをg-Xtってすればいいだけじゃん！！後は負辺あるし、Bellman-Fordで経路探索するだけか。ほんと黄さんの言ったとおりだった。 てか、ここまで考察を書…

今日は大分前にあったMaximum-Cup 2007の復習をnobuとやった。 せっかくOBOG合宿に呼んでもらったので、今までできてなかった問題を聞けるように付け焼刃の追い込み。

ちょっと他人のコードを読んでいてなるほどと思ったからメモ。 これで少しハードコーダーを脱せるかもしれない。２次元の探索問題でよく自分の上下左右を探索したい時がある。これを普通にコーディングするとどっかで下のような感じになっているはずだ。 dfs…

久しぶりになってしまった。 8月に入って SoC設計Bの実習でVHDLを学び、FPGAの音声デコーダを作り、 バドミントン合宿で体力を奪われ、 最近3日はインターン行ってた。 実はこれだけで毎日予定が埋まっていた・・・。 他にもやることもあったから日記なんて…

今日は晴れてテスト最終日。 実験レポート提出状況を見たら OK OK OK OK OK OK この無機質な文字の羅列が生み出す感動はこの実験をやった人にしかわからないであろう。 指導書を写すというタイピング練習、五円玉で書いたグラフ、思い出が走馬灯のように駆け…

結局5位争いしている人に入れてない俺は負け組・・・。

10万8千円でさらにポイント20%つくから結構安い。 スペックは CPU Celeron1.8G RAM 1G HDD 80G Office、ウイルスバスター付 のA4ワイドのノートPC。 メモリが1GもあればVistaでも問題なさげ。 いいなぁ。 今は10万でこのスペックが買えるのか。

パターン認識演習の授業でやっているじゃんけんの手の認識だが、授業で習ったHaar特徴量を使った認識は認識率が悪く、結局色を元に面積で計算したほうが高精度という結論が出てきた。 もともこもねぇ・・・。 何も認識してねぇじゃん・・・。 てか最初はあっ…

今日はインターンのジョブマッチングとやらに行ってきた。ジョブマッチングとか言うからインターンでどの部署で働くのか決めるだけだから、ちょーよゆーとか思ってたら、そうでもなかった。 会社に着いたら他のメンバーと一緒に待合室に案内されてそこにいる…

国内予選に向けての練習で見つけた面白かった問題を忘れないうちに書いておこうと思う。この問題は、2005年のStanford Local Contestの問題セットをやったときに出会った問題だ。 問題 Inputの形式は以下のように与えられる。 ... ... 問題の内容は、 ある人…

なんか最近SecondLifeの日本語版も公開されたらしい。 すごい興味あるんだけど、SecondLifeやってるぐらいならPKUやれって話しだし、Haskellやれって話しだし。 やったら負けな気がする・・・。 でもやらなかったらそれはそれで負けな気がする・・・。 なん…

オペレーティングシステムの授業で出たコマンドインタープリタを作るという課題なのだが、これがグループ課題なのがなんとも厄介。Cで200行から300行でかけそうな課題なんだけども、それを4人で協力するのは難しい。 一人は全く連絡取れないし、他の二人はパ…

そんなこんなで他人のコードを見た後、うちらは何を間違えたのかなぁと思って自分たちのコードを読み直すと、最初の木の同形判定をするためのオペレータ部分 bool treeless(const Tree* lhs, const Tree* rhs) { if (lhs == NULL && rhs == NULL) return fal…