cafelier@SRM

Small最速理論

GCJ | 20:33 |

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

• 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用コードを書き直す、というと無駄に時間かかるようにも思うんですが、入出力の部分や途中のデータ構造、補助関数も結構使い回せるので、意外とやってみると悪くない

とかなんとか。