通過の正式通知が来た、Round 1の時間に関しては最初は7/25-31まで選択肢があったが、集計の結果偏りがあったのか、土曜日の10:00と25:00、日曜の18:00の三つの中から二つの時間を選ぶことになっていた。各ラウンド上位840名がRound 2に進出できる。あと各ラ…

Rateが1969->2000で2000点台に 250 連結している部分はすべて完全グラフに直して、頂点が一個の部分に関しては最大連結成分のところに合わせればよい。 500 開始アドレスの候補となる位置は与えられるアドレスの部分かk個前で、高々100個程度なので100^3のDP…

3問中3問解いて、すべて通った。1問解けば通過なので何事もなければRound 1に進める。スコアボードをみると7000人弱が通過している、つぎのRound 1からRound 2には2520人進める。追記：各問題のプログラムを貼っておく A 次にでてくるのが一番遅いクエリを常…

Kleinberg and Tardos のAlgorithm Designが日本語版で出ている。価格は15000円。英語版もそれくらいするのでこれから買おうと思ってた方はこっちをかってもよいかも。

250 本質的には先頭からできるだけ重ねて連結するだけ、ただし連結するときにx_i 600 要約するとn,m 900 正解しているひとのコードを見ると非常にわかりやすい。要は一回の試行時にあるマスが塗られる確率がpならばK回の試行で塗られる確率は1-(1-p)^Kなので…

昨日、自分の数理輪講の発表が終わってひと段落したので一週間ほど実家に帰ります。

Javaの幾何ライブラリを使って解いてみた。多角形と線分の距離をもとめるというそのままの関数はなかったので自分で一から書くのに比べて、そんなには楽にならなかった。 import java.awt.geom.Line2D; import java.awt.geom.Point2D; import java.awt.geom.…

今年は観戦側。東大内のボーダーが6問になっていてびっくりしました。問題を見た感じだと今回はすべての問題ができるように作ってあったので6問解くチームはでるかなとは思っていたけど3チームもでるとは。 各問題に関する感想(A,Bはちゃんと読んでないので…

250 毎回ソートして、高さが高いものから使っていく。 500 ターゲットの点をルートとした木を考えたときに、リーフ以外の点に飴がk個置かれているという状態がokならばその点の飴を全部除いて、子供に2k+1個置いた状態もokなのでなるべく深い部分に飴が集中…

250 上司、部下関係のグラフが与えられた時に、部下を一人も持たない人の給与を1，そうでない人の給与を自分の部下の給与の合計と定義するとき、支払われる給与の総計を求めよという問題。メモ化再帰を書くだけ。 500 状態空間は3^12しかないので、これもメ…

グループの方でQualification Roundに関して補足説明があったのでメモ 問題は3問出て、どれか1問に正解すればRound 1に進める、人数制限とかは基本的にない． Qualification Roundは24時間行われる、ただし問題の内容としては1時間程度あれば1-2問解けるレベ…

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に進める．そ…

250 8!個のすべての順列に対して何本線が引けるかを計算して最大のものをとればよい． 500 高々12*12ぐらいの数字(-100から100)が書かれた紙を折っていく、折った時に重なった数字は合計する。折ってった時のセルの数字が最大となるように折れという問題。 …

先週あたりから解きだしてみた、現在120問解いた。

順位があまり良くなかったためRateが1880->1775へと下がった 250 三角形の下から値を決めていく．もしくは全部の要素を見ていって決定できるところがあったら決定するを繰り返して，全部埋まるまでループする． 500 長さが3000までのintの配列 A が与えられ…

内定貰えました。一応これで就活は終了するつもりです。

250 大きさがn(A[j]となっているペアに対してのみ行う)。たとえば(1,4,3,2)で4と2を交換すると(1,2,3,4)となって一回で終了するが、3と2を交換した場合(1,4,2,3)で終了しない。このとき交換の回数の期待値を求めよという問題。 ここで配列Aに関して交換の回…

http://www.spoj.pl/ZFUN08/ SPOJのコンテストに先週あたりから参加しています。あんまり長期間行うコンテストに参加した経験はなかったのですが、色々と文献調査とかしながら問題を解くのはなかなか面白いです。 一応、一通り手をつけて現在ランキング7位に…

250 与えられたn(= a_2 >= a_3 >= ... >= a_n, a_i 再帰、もしくはDPで解ける。 550 次の二つの媒介変数表示の曲線が与えられたとする。ここで2つのt,sは独立に動く、またt,s以外の変数は与えられる。 このとき、二つの曲線が交わるかどうかを判定して、交わ…

大型連休後半らしい、実感はないけれど。ところで5月6日が振替休日になっていることに違和感を感じたので調べてみたところ、2005年に5月4日(日)が国民の休日から国民の祝日になったことに伴って、最も近い国民の休日でない日の5/6が休日になったようです。 …

250 n(素数、q>=2)の形で表せるかどうか答えよ、表せるならば{p,q}も求めよという問題。 qを固定したらp=exp(log(n)/q)で求まるので、これで出して素数かどうか確認する。 500 1,0からなる文字列s1,s2が与えられたときにs1の部分文字列をひっくり返していく…

PKUの解いた問題数がちょうど700問目になった。 700問目の2112 Optimal Milkingは頂点数がK+C個の重みつき無向グラフが与えられて、1..Kの頂点にミルクマシンが置いてあり、K+1..K+Cの頂点に牛が1匹ずついるときに各牛がミルクマシンに配置させるときに最も…

珍しく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>…

今日のSRM399で最大流の問題が出てて、結構よく出てライブラリと持っていないとその場で書くのは難しいのでコードをここに張っておく。 class MaximumFlow { int size; int flow[][]; int capacity[][]; int q[]; public MaximumFlow(int capacity[][]){ siz…

また落ちた。志望理由をちゃんと詰めてなかったのでそのあたりでgdgdになったのが理由だと思う。

今研究室で四年生の実験のTAをやっています。実験の題材は「パターン認識システムの製作」でパターン認識を使った何かシステムを作るというもの。テーマを相談させて決定させたところ言語の自動判別をやることになった。 言語の自動判別というと最近Google A…

Google Code Jamのベータテストに参加してみました。 今回のルールは大体次のようなものでした。(昨日書いたことの整理もかねて) 制限時間は2時間 各問題にはスコアがあって、順位はスコアの合計で決定される、同着の場合は回答時間の合計の短い方が勝つ。 …

アリーナのチャットで見かけてリンクをたどったら、こんなもの(http://code.google.com/codejam/)があった。 制限時間とか詳しいところはまだ読めていないけど、基本的にはICPCの国内予選と同じで入力をダウンロードしてきて出力をファイルでサブミットする…

250 数字の位置の場合の数は高々6通りで、演算子の場合の数は3^3通りで6*3^3通りに対してすべて試す。 500 DP。行列の位置、パスの長さ、前通ったパスの番号をキーとする。本番で書いたコードは端の部分の埋め方が間違っていたせいでSystem Testで落ちた。 1…

賞金付きで人が多かったせいか、サーバの不調で20分遅く始まる。 250 高々長さが8の配列に対して、k個の連続する区間を反転させるという操作を繰り返したとき、最短何回でソートされた状態にできるかを返せという問題。 状態空間が8!=40320しかないことに気…