Hatena::Grouptopcoder

cafelier@SRM

cafelier のSRM参加記録です。コンテスト中に考えてたことを執拗に全部書き残すとどうなるだろうかという試み本番中にこういうコードが書きたかったなあ、という後で書いた反省コードを書き残す試み

スパムが来たのでしばらくコメント欄をはてなユーザ限定にしています、すみません、

 | 

2009-09-12

Small最速理論

| 20:33 | はてなブックマーク -  Small最速理論 - cafelier@SRM

ついでなので、メタな戦略についても考えていることをだらだらと書いてみる。

  • Largeは見向きもせずにとにかくSmallだけ解けるアルゴリズムを考える

のが去年からの自分の方針です。Small用に考えたコードでそのままLargeを解けたら儲け物だけど、大抵そうもいかないので、Large用にはあらためて新しく考えてコードを書きおこします。

  • 理由A: せっかくSmall/Large分かれてるコンテストなんだから普段のSRMとかと違うことをやりたい
    • やりたい。(これが理由の7割)
  • 理由B: Smallだけでも全完できればそれだけで結構上まで行ける。
    • 2008
      • ラウンド名 Small全問解いた場合の順位, Smallの最高得点問題を落として残り解いた場合の順位 / 足きりライン
      • Round 1A (3) 450-604, (2) 813-1405 / 840
      • Round 1B (3) 262-376, (2) 616-1019 / 840
      • Round 1C (3) 223-375, (2) 621-1570 / 840
      • Round 2 (4) 319-852, (3) 1173-1409 / 1000
      • Round 3 (4) 226-253, (3) 329-396, (2) 626-667 / 500
      • APAC Local (4) 35, (3) 83-86 / 36
      • AMER Local (4) 52 / 21
      • EMEA Local (4) 86 / 43
      • Final (5) 100人中:61位~71位
    • 2009
      • Round 1A (3) 425-428, (2) 685-726, (1) 741-2028 / 1000
  • 理由C: テストケース入手
    • まずSmallをSmall専用コードで解くのは、あとで改めてLargeを解く時にも役立つと思う
      • Smallだけ解けるような単純なコードは、わりと楽に一発で正しく書ける
      • Largeを解けるような工夫したコードは、一発で正しく書くのは難しい
        • テストが充実していると正しく書くのが楽になる ←重要
        • Smallを解いておけば100ケース近いテストが手に入る!

サーバへのsubmitでcorrect/incorrectを見てテストするのだと、ペナルティも食らいますし、そもそもどんなテストケースでincorrectと言われたのかわからなくて、あんまりデバッグの役に立たないので…。手元に正しいinput-outputがあると大違い。

  • 理由D: そんなにタイムロスもないような気がする
    • Small用コードと別にLarge用コードを書き直す、というと無駄に時間かかるようにも思うんですが、入出力の部分や途中のデータ構造、補助関数も結構使い回せるので、意外とやってみると悪くない

とかなんとか。

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

presented by cafelier/k.inaba under CC0