Hatena::Grouptopcoder

Gus@topcoder

topcoderのid:gusmachineの記録です。普段の日記は揺動散逸日記をどうぞ。

2008-12-24

SRM 431

21:50

250 AC, 500 AC, 1000 opened. challengeは1成功1失敗。

非常にうれしいことに、500が久しぶりに解けました。一時間以上使ってしまいましたが。

前回のDPが解けなかったこともあり、これが解けないと存在意義的な意味で問題だと思い気合で通しました。

250

各障害物に当たる確率を求めて足すだけ。atan2はどっちがyか謎なのでcomplex<double>::argを使いました。

500

方針は(何桁目か, 直前の桁の数字, 何グループ作ったか, 最後のグループの差分)でDP。

五重ループが面倒だと思いmemoizeにしようとするものの、groupの切れ目をどう回収すれば良いのか分からなかったのでDPにしました。

  • 最後のサンプルが通らない。こんなの手計算で分かるわけがないので当てもなくprintfデバッグ
    • 結果non-descending orderを忘れていただけでした。変更してsampleと一致。
  • 最大のケースは1000, 1000じゃないですか。てっきり10, 10だと思っていました。
  • まずテーブルが崩壊するのでテーブルを書き換え。さらにエントリー数が爆発するので必要な所だけ埋めるようvectorからmapにしました。
    • 後から考えるとmapにする意味はほとんどない。
  • ループが終わらない。
  • __gnu_cxx::hash_mapたすけて。
  • ところでテストデータcount(1000, 20)とか0になるんですけどあってるの? まだバグってない。
    • 良く考えたらグループ10以上はできるわけがなかった。ということは100倍高速化できる!
  • グループ10までにして100倍高速化。
  • まだ時間がかかる。
    • グループ10までなので、余裕でテーブルを確保可能。vectorに直す。
  • 終了4分前に提出。

1000

みてない。

Challenge.

500で if (A >= 9) return 0;を撃墜。ついでにAをあまり使っていなそうなコードに1000, 500を出すものの失敗。一勝一敗。