行ってきた。Dのsmallしか解けず惨敗。 D 木が2つ与えられた時に、木Aが木Bに含まれているかどうか判定せよという問題。 smallはNが8個しかないので8!通りラベルづけを試せばよい。 largeはルートをそれぞれの木に対して決めた後、Aのそれぞれの部分木がそれ…

500人通過中117位で通過。 D small 典型的DP C small N B small , large (現在地 * 扉1の配置 * 扉2の配置)の状態空間に関して幅優先する。扉の位置が一つの壁に関して4通りあるとか銃を撃つときにはターンを消費しないと色々と条件があり、実装にかなり手間…

1000人通過中377位で通過。 D-small 最初はAを読んでたけどよくわからなかったのでsmallの点数が5ptだったこれを解いた。k A 各ゲートに対して0,1を取る時のそれぞれの最小回数を下から求めていく。 B-small 最初5重ループとかを書いてみたけど実行時間がか…

C-largeはソートされたリストに対してi番目の要素の検索と要素の削除が効率的に行えるデータ構造があればよい、一般的には赤黒木などの平衡二分木が必要になるんだけど今回の問題は挿入を考えなくてよいので単に子要素がどれだけあるかを保存した二分木をつ…

199位でRound 2に通過。 A 格子点上の点がn個与えられた時に重心が格子点にのるような異なる3点の取り方の数を出せという問題。とりあえずsmallに関してO(n^3)のコードを書いて通しておく。よくよく考えるとx,yに関しての3で割った余りのみ見ればいいことが…

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

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

グループの方で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に進める．そ…

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

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