読者です 読者をやめる 読者になる 読者になる

Marathon Match 68

TopCoder マラソンマッチ

(2011年6月1日の記事を移行したものです。)

結果

9位/147 Rating --→1754

大反省点

  1. 開始日になんでもいいから提出して追い込む!
  2. 準備完了までは集中!
    • ちゃんとスコアがでるようになると、面白いので集中できる。準備の段階が面白くないので脱線しやすい)
  3. 異常を早めに察知するために、ときどきArenaにいって、サブミット&まわりの人のチェック(提出時間・得点)
  4. テストケース50個では少なすぎ
    • 誤差でまくり論外!!!テストケースは最悪でも300,500は必要
  5. 疲れているときにできること、疲れているときにできないことにタスク分けして作業をすすめる。
  6. 10秒間の計算時間があるのを有効に使ったアルゴリズムにする
    • 最後のほうまで、即終わるアルゴリズムだったので…

反省点

  1. サブミッションの問題(1時間30分次の提出ができないのでお早めに。
    • 早めに知ってれば、「へび」配置をいれるかいれないかも含めて調整できたのに・・・。
  2. タイマーの問題(10秒)Clock関数。とくにアリーナ上では、時間がかかるよう。
    • gettimeofdayのほうがよい?
  3. 序盤の準備にわりと時間がかかる。
  4. やってみて気づくことはたくさん。なので、後で追い込むのではなく、最初から少しずつやってったほうがいい。
  5. ソースは丁寧に書く。リファクタリングは、時間に余裕があるときなら、多少眠くても疲れててもできる。
  6. ネット切断は効果的だったけど、たまにはアリーナものぞくべきだった。

ポイント

「回」型の配置パターンで62.5ptsは取れるのは予想がついたけど、「回」型の配置に気づくのが遅すぎた。また、正方形のときにしか対応できないアルゴリズムを書いてしまったので、「田」型への応用が難しくなってしまった。
唯一良かったのは、大きさの違う正方形「回」を組み合わせることにより、rcFillingScoreが満点のままで「田」型にする方法を思いついたこと。これのおかげで、上位になんとか食い込むことができた。
例えば、3等分の「田」にしたいときは、横幅がN%3==0,N%3==1は以下のような配置にできる。普通の「田」だと隙間の行ができてrcFillingScoreが下がってしまうが、これならOK.

4等分の「田」にしたいときは、以下のような配置もある。

あと、上位の方は

  • 「回」「田」以外でも点対称な配置はいろいろあった
  • 置き換えが可能なアルゴリズムにしていた。

といった点で大きく差がついた。