Hatena::Grouptopcoder

yehara のTopCoder日記

 | 

2009-03-09TCO09 Round 1 このエントリーを含むブックマーク

Level 1

与えられた数が、連続した0以上の整数の和で表せるかを判定する問題。本番中にとったアプローチは以下の通り。

  • 値の平均値を求め、個数が奇数の場合は平均値整数であること、個数が偶数の場合は平均値の小数部分が 0.5 であることを判定する
  • 先頭の値が 0 以上であることを確認する

これで問題はないのだが、いきなり先頭値を計算してそれが 0 以上の整数であることを確認する方が早かった(個数の奇偶別の判定もいらないし)。最初は先頭が 0 未満のケースを見逃してたり、変数名の書き間違いなどのつまらないミスがあり、15 分近くもかかってしまった。202.08 点。

Level 2

DP なのかと思いつつ、直接的に確率を求めるアプローチでいけるはずと考えて挑んだ。

  • K-1 個の値が N 以下の数のグループ
  • 1個の値が N のグループ
  • M-K 個の値が N 以上の数のグループ

に分かれる確率を求めようとするも答えが合わず。ずいぶん時間を使ったあと、漸化式をたてての再帰方式に切り替えるもやはり答えが合わず。時間切れ。

終了後、以下の3グループに分割して確率を求めるとうまくいった。

  • nl(0〜K-1)個の値が N 未満の数のグループ
  • M-nl-nu 個の値が N のグループ
  • nu(0〜M-K)個の値が N より大の数のグループ

Level 3

開くこともできず

まとめ

残念ながら 958 位で通過ならず。早く解けていれば Level 1 の正解だけでも通過できていたようだ。

本番では Petr 氏と同組になり、その凄さを目の当たりにした。私が Level 1 で手こずっている間にもう Level 2 まで終わっているし。Challenge Phase でも Petr 氏が撃墜した 1 つを除き、残りはすべて System Test に通っていた。30 分余りで全完して、間違っているやつをすべて撃墜しても rating が 32 も下がるとは。1完でも rating が上がる私とは格が違いすぎる。

トラックバック - http://topcoder.g.hatena.ne.jp/yehara/20090309
 |