Hatena::Grouptopcoder

TopCoder煮ブログ

本家ブログはこっち → http://d.hatena.ne.jp/nitoyon/

2008-10-19

SRM422 DIV1

| 03:28 | SRM422 DIV1 - TopCoder煮ブログ を含むブックマーク はてなブックマーク - SRM422 DIV1 - TopCoder煮ブログ

250 と 500 を解けたつもりになったが、500 を Challenge された。全体的に点数が低めだったらしく、ついに Yellow に!

14601514

SRM 422 DIV1 全体では312位、TopCoder 全体では1132位。

PrimeSoccer

14分で解いて204pt。組み合わせを求めるところで時間かかってしまった。パスカルの三角形使うのがシンプルなのかなぁ。対偶で計算したけど、そのまま求めている人も多かった。

→上位の人は1回のインターバルで0回入る確率から順番に、n回のインターバルでどうなるかを順番に求めていってる。動的計画法か。

CavePassage

最大で N=13 ってことは 2^N * N^3 のアルゴリズムだったとしても高々10^7ぐらいなので力技コース。がんばって書き下したつもりだったが、詰めの甘さを発揮して Challenge で追撃された。思い当たる節を修正して System Test に提出してみたがやっぱり撃沈。根本的にどこかでバグがあるようだ。

(追記) 分かった。行った人と違う人が帰ってきてもいいのか! 自分の方針だと、{{3, 3, 6}, {1, 1, 1}, {"YYY", "YYY", "YYY"}, 6} が -1 になる。しかも、帰ってくる人が複数の場合もある。これは想定外!

WorkersOnPlane

見てすらいない。

感想

500を解きたかった…。が、今の実力ではこれは無理だ…。

今回から、TopCoder部 - ハチロク世代Skype chat に参加してみた。楽しい。