久々にやった。 Div.2なので問題が簡単だった。 Division Placed: 5位

無事終了。 KAISTの人たちと飲みに行って、その後、ホテルの部屋で一緒に飲んだ。 いろいろな話ができて楽しかった。

英語での発表は、恥ずかしがらないことが重要だと思った。 次に英語で発表するときは、カンニングせずにがんばる

緊張最高潮

明日から韓国

NIIはうちの大学の近くにあったね。 今年も海外勢が強そうなので、日本のチームも頑張って欲しいね。 もちろんうちの大学も頑張って欲しいね。

と書こうとしたら、日をまたいでいた。

「すべてのAはXXXである」という命題を証明するときに、より証明しやすくするために、より制約の強い「すべてのBはYYYである」という等価な命題に帰着して「すべてのBはYYYである」を証明するという方法がある。 特に、クラスAがクラスBを包含していて、「す…

２回目の100秒切りデタッ

とりあえず二桁順位を目指そうかなぁ

Codeforces初参加!!! Div. 2だからか、問題が簡単だった。 5問中4問ACで全体31位

Amortized Analysisをわかっている気でいいたけど、 必要になって初めてちゃんとした理解が得られたような気がする

http://cstheory.stackexchange.com/

凸集合Sの点の凸結合は,Sに含まれるということ

また自転車を買ってしまった。 まだ2台目だから場所は大丈夫だけど、 これ以上買うと置き場所がヤバイな。あと、シャワーを浴びているときに、 Amazon.comから何かが届いてた。 たぶんKindle

受理された論文のレビューが送られてきた。 前回落とされた時のレビューに比べると、 査読者がしっかり読んでくれていることがわかるようなレビューだった。

そしてVazirani本。 わかんなかったところが、わかった。 よく考えると、当たり前のことが書いてあるので、 詳しい説明をしなかったのだと思うが、私のような初学者の為に、 もう少しわかりやすかったらよかった。 この部分を過ぎたら、サックリ読破。 続い…

やっぱりVazirani本。 ５章のk-center問題を勉強中。 詳細はMetric k-center - Wikipedia。 ちなみに、distanceがmerticでないとすると、P=NPでない限り、 計算可能関数f(n)において、近似率f(n)以内を達成できないことが知られている。ある証明がよくわかん…

初Acceptキタッ!!

引き続きVazirani本４章。 Multiway cutとMinimum k-cutの近似アルゴリズムについて。 Multiway cutはk個のterminal集合が与えられたときに、 あるcutを取り除くと、各terminalが別々の連結成分に属するような、 最小重みのcutを求める問題。k>=3でNP困難で…

引き続きVazirani本で勉強。 ３章まで完了。あんまり内容について記述するのはまずいのかな？ Metric TSPの2-近似とそれを1.5-近似に改善するところが面白かった。 2-近似はシンプルで良いのだが、2-近似の何が悪いのかをしっかり分析して、 それをうまく改…

今日はVaziraniの近似アルゴリズムの本の１章を読んだ。 頂点被覆問題は、グラフの極大マッチングを求めて、 両端点をカバーすると、2-近似アルゴリズムになる。 近似アルゴリズムの知識は余り無いので、これを機に勉強する。 今日は２章まで読んで寝よう。

ヨセフス問題のk=2の特殊な場合。 TLEで放置してたんだけど、wikipedia見たら答えが書いてあった。 n人で一人飛ばして処刑していくとき(つまりk=2)、 nは二進法でb_0b_1b_2b_3...b_kであるとき、解はb_1b_2b_3...b_kb_0になるらしい

５日連続で疲れたけど、内容も充実していたのでよかった。 まぁ、まだレポートが残ってるけど。 明日はオープンキャンパス。

http://math.mit.edu/~goemans/teaching.html http://homepages.cwi.nl/~lex/ http://www.cs.illinois.edu/homes/chekuri/

とりあえず進路の確保はできたので、あとは研究するのみ

発表は、今取り組んでいる内容についてしゃべることにする。 内容は、さほど難しくはないけど、数学に慣れていないとキツイかも。 未解決の内容も含んでいるし、背景が壮大な分野なのでいいかも

無事終了&無事帰宅。今日の内容はmultiflowの話。 今日は二つの意味で非常に勉強になった。 一つめの意味はそのまんまの意味で、 もうひとつの意味は、自分がいかに修行が足りていないかを知ることができた。明日は1限から試験監督TA

無事終了。今日の内容はスケジューリングに関すること。 今日の午後の内容はかなり難しかった。あとゼミの中間発表に関して不穏なメールが来たので、 内容を大幅に変更する必要がありそう。