contest

ICFPC 2012

http://icfpcontest2012.wordpress.com/年に1度のICFP Contestでした。 O(nwn)というチームで参加していました。自分以外のメンバー:@uwitenpen,@kou_miyam,@hasi_t,@nico_shindannin,@WtbH ICFPC4回目の参加で初めてチームを作ってみた。 1日目 問題読んで…

ICFP Programming Contest 2010

http://icfpcontest.org/2010/ 年に一度のお祭り、今年も参加しました。1人チームです。 score: 102.991 others' cars solved: 178 cars submitted: 0 で70位くらい? 1台くらいは車を出荷したかったなぁ。次から次に現れてくる謎を解くのに夢中であっという…

ICFP2009 Programming Contest

http://www.icfpcontest.org/ 年に一度のお祭り・ICFP Contestでしたよー。 が、けっこう心待ちにしていたはずなんだけども、あまり好きなタイプの課題じゃなく、どうも気分が乗りきらず途中で投げ出してしまった。へちょい。コンテスト72時間中の実働は15時…

UTPC2009

東京大学プログラミングコンテスト(UTPC)というやつに参加して遊んでいました。 http://www.utpc.jp/2009/ レッドコーダー経験者が10人以上という、オールスターと言ってもいいそうそうたる参加者の面々を向こうに回して、なぜか優勝してしまったっぽい。…

TopCoder SRM 435 DIV1

練習の成果がきてるー Coding Phase 250点問題 二分木の1つのノードを切り落としたとき、残った木にリーフは何個あるか。実装するだけ。サイズが小さいのでどんな方法で書いてもまず大丈夫。けっこう易しい部類の問題。 500点問題 DNAの塩基配列と、コドン→…

TopCoder SRM 434 DIV1

マラソンマッチに取り組んでいる最中のSRMは頭の切り替えが必要だ。 練習会の成果を出せるか。 Coding Phase 250点問題 数字の二次元テーブルが与えられる。テーブルの中を一定の間隔で飛んで数字を拾っていき、拾った数字を1つの整数として読んだとき、平方…

Marathon Match 48

TopCoderのMarathon Matchに初挑戦しました。 いつもやってるSRM(Single Round Match)との違いはこんな感じ。 SRM スピード勝負。問題文に関数の仕様が書いてあってその通りに作る、というのを75分で3問。早く提出するほどスコアが高い。 Marathon 長丁場…

TopCoder SRM 433 DIV1

ふにゃふにゃ。 Coding Phase 250点問題 文字列検索。愚直に書くと時間内に終わらない。遅そうなパターンにはアドホックな方法で対策をしたけれど、カバーしきれなかった例があったみたいでテストFailed。文字列のちょっとした性質をひとつ使えば簡単に答え…

TopCoder SRM 432 DIV1

SRM初め。 Coding Phase 250点問題 ランプがN行M列に並んでいる。初期状態でランプはそれぞれついてたり消えてたり。「ある列のランプすべてのオンオフを切り替える」という操作をK回繰り返したあと、全てのランプがオンになっている行の数を最大化する問題…

TopCoder SRM 431 DIV1

今年最後のSRM。 Coding Phase 250点問題 xy座標平面上のx>0の範囲に、y軸と平行な壁が何枚かある。原点から角度-π/2〜π/2の範囲でランダムな方向にビームを撃ったとき、壁を突き破る数の期待値を出す問題。Math.atanを使うだけです。なんかいまいちな問題だ…

EclipseCoder導入

TopCoderでの素早いコード書きを支援するプラグインが色々ある中、「どうせボトルネックはアルゴリズムを考えるところだしなあ」とこれまで導入は見送っていました。 ですが、だんだんとコンテストに慣れてきて、簡単な問題では考えるところよりもテスト等の…

TopCoder SRM 430 DIV1

練習のため過去の解けなかった500点問題を解いていたが、だいたい解き方が分かっている状態で書いてもなかなか通るものができなくてへこんでいる中のSRM。 システムのトラブルで開始時間が数分遅れた。運営の皆さんお疲れ様です。 Coding Phase 250点問題 整…

TopCoder SRM 429 DIV1

そろそろ壁を越えたい今年残り3回のSRM。 Coding Phase 250点問題 各点が部分矩形として何回使われるかを直接計算できるので、愚直に足し合わせる。最大100×100なので問題なし。 500点問題 量の関係が有向グラフになる。関係を一つずつ当てはめていって、過…

TopCoder SRM 428 DIV1

21:00から。この時間帯は一番参加しやすいはずなのになぜか調子が悪いときが多い。日本人の参加者が過去最高、89人。来年の前半には100人突破もあるか。 Coding Phase 250点問題 C++の人なら「next_permutationで一発やん」というところだが、Javaにはそんな…

TopCoder SRM 427 DIV1

今日は通院のため有休を取っていたので、平日午前のSRM参加。ちょっといけない気分。 Coding Phase 250点問題 ある惑星の公転周期と自転周期が与えられて、閏年の周期は何年かを答える問題。最大入力が10億なのに最初ループで一つづつ調べるコードを書こうと…

SRM425 Level2 PiecesMover

コンテスト中に書いたコードは、時間がかかる入力が来ると結果が出るまでに20秒以上かかってました。 この程度の遅さなら、アルゴリズムのオーダーが悪いのではなくて定数項の違いだろうと思い、ちょっと書き直し(オーダーが間違ってたら、遅いケースでは何…

TopCoder SRM 425 DIV1

寒くて指が動かしにくい季節です。最近お仕事であまりコード書いてないのでタイピングの調子がいまひとつ。 Coding Phase 250点問題 碁盤目上をロボットがランダムウォークする。4方向それぞれへ向かう確率はパラメータで与えられる(等確率というわけではな…

TopCoder SRM 424 DIV1

半月ぶり。なんか睡眠不足で疲れた。 Coding Phase 250点問題 自然数Nが与えられる。各桁の数字をかけた結果がNと等しくなるような自然数Mの中で最小のものの桁数を答える問題。そのようなMが存在しなかったら-1を返す。まずNを素因数分解しようとしていたけ…

SRM 423 Level1 TheTower

参加できなかった前回のTopCoder SRM、遅ればせながらPractice Roomでやりました。噂ではかなり難しかったらしい。 時間を75分計ってやってみたところ、Level1(300点問題)は35分くらいでsubmitできました。システムテストも通って152pt。これは確かにいつ…

CavePassage解けた

昨日の続き。これまでの実装だと、もう最短経路ではないと分かっている要素もキューに追加されていってたので、それを抑制したらかなりの時間短縮になりました。システムテストの一番遅いやつで500ms弱。よしよし。しかしこの量のアルゴリズムを制限時間内に…

SRM 422 Level2 CavePassage

前回のSRMの500点問題、手が出なかったので復習。1時間強をかけてダイクストラ法で書いてみました。こんなに時間がかかってしまうと本番ではとても無理だな…。どうやったらこんなのが20、30分で書けるようになるのだろう。 それはさておき、僕が書いたコード…

TopCoder SRM 422 DIV1

今回からハチロク世代TopCoder部でチャットしながらのSRM。これは楽しいし勉強になる。 Coding Phase 250点問題 組み合わせで確率を計算して足し合わせるだけ。今回はほとんどミスなくスムーズにいけたぞ。少し練習した成果が出てきてます。 500点問題 こん…

TopCoder SRM 421 DIV1

Coding Phase 250点問題 二分探索で調べるだけ。今回はなかなか素早く解法が見えたなあと思っていたら、またもやイージーミスをずっと見つけられずにとても時間を費やしてしまった。二回連続でこのパターンか……。 500点問題 これ数学的にちゃんとやろうとす…

TopCoder SRM 420 DIV1

Coding Phase 250点問題 単純にシミュレーションして調べるだけ。のはずが、イージーなミスをずっと見つけられずにとても時間を費やしてしまった。 500点問題 深さ優先探索+メモ化したら、OutOfMemoryかStackOverflowだ。キャッシュサイズを色々いじっても同…

TopCoder SRM 419 DIV1

平日午前中SRM。他にもちょっと用事があって、せっかくだからというわけで有給休暇を取っての参戦です。 だいたい月に一回くらい日本時間の日中にSRMのスケジュールが組まれてるから、それに併せて有休を取ってけばちょうど良い消化ペースになるな…。いや実…

アルゴリズムコンテストの勘所

一度も書いたことが無いと意外と手こずる、再帰的な/再帰的に問題をシラミ潰す方法… 深さ優先探索, 幅優先探索, 分割統治法, メモ化, 動的計画法 … はひととおり把握しておいた方がよいかも。 d.y.d - アルゴリズムコンテストの挑み方 そうですね! そこが今…

TopCoder SRMでのスコア計算

TopCoderでのスコア計算式 TopCoder SRMでは、問題を開いてから提出までにどのくらい時間がかかったでスコアが決まります。時間がかかるほど獲得するスコアが低くなる。その具体的な計算式がヘルプに載っています。 MPを問題の最大ポイント、TTをCoding Phas…

TopCoder SRM 418 DIV1

イエローコーダーとして初めてのSRM。さてこの地位を保てるか。 Coding Phase 250点問題 高校の数学Ⅰでありそうな組み合わせの問題。最大サイズが小さいので、どんな方法で解いても時間オーバーになる心配はまずない。トラップになるような箇所もなく、ただ…

TopCoder SRM 417 DIV1

今回0点だったらたぶん二軍落ちなTopCoder。緊張するー。ここしばらくの睡眠不足がどう出るか。 Coding Phase 250点問題 文字列textとprefix、suffixが与えられて、textの部分文字列の中でできるだけ長くprefix、suffixとマッチするものを探す。入力の最大長…

TopCoder SRM416 DIV1

半月ぶりのTopCoder。ひゃっほう。 …と思ってやってたら過去最低の出来だった…。前回からの間、過去問を見るとか言っときつつできてなかったからなあ。 250点問題 考え方は間違えていなかったものの、イージーミスをしていて撃墜されてしまいました。テスト…