2011-10-05

■ [SRM]SRM520 00:30

http://community.topcoder.com/stat?c=coder_room_stats&cr=22744421&rd=14545&rm=310101

• Coding
  • 250
    • 読んだ瞬間全探索
    • Javaにはnext_permutationないので6通りベタ書きしてしまった。まあそれくらいなら
    • 添字ミスではまって時間ロス
    • 貪欲でもいけるみたいだけどそんな自明じゃない気がして
  • 500
    • 基本部分は上位の人から順に「N点取った場合はM通り」を記録してDPやれば計算量20*20万で大丈夫だけど、
    • 3問のうちいくつかを解いたときに特定の点数をとる方法が何通りあるかを数えるほうが難しい
    • 0,1問なら自明
    • 2問でもちょっと考えると山型／￣＼な感じになることがわかる
    • 3問の場合は…
      • 3問の得点をA・B・C、2問目と3問目だけでN点取る場合の数をX[N]とすると、
      • 合計がM点になるケースは、1問目が1点の場合+2点の場合+…+A点の場合=ΣX[i](M-1<=i<=M-A)
      • で、これを元にすると合計がM-1点のケースも尺取法っぽく1つ頭から取って1つ後ろを落とすことによりO(1)で計算できる
    • BIT使ってる人も多かった。ライブラリ持ってたらそっちの方が速いかも
    • また添字ミスではまって時間ロス
  • 1000
    • 読んだだけ
    • 解いてる人のコード見ると短くて興味深い
• Challenge
  • 落とせそうなのなかったので何もせず
  • DivisionSummary見ても+50してもあまりうれしくなさそうな上に-25が痛そうだった
• System Test
  • 通った
• 結果
  • 209.21 + 235.90 + 0.00 + (50*0 - 25*0) = 445.11
  • 67位/810人
  • レート 2178->2227