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

TCO11 Round 1

TopCoder マラソンマッチ

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

結果

62位/368 Rating 1754→1795

大反省点

  1. 調査してね(インターネットつかえます)
  2. 文字を置く・何か置く、やり直し(Undo)が可能な部分については、最初からやり直し可能な実装をしていかないと、だめです。
  3. 最初の解答ができるまで、とにかく、がんばれ。
  4. 前回の反省点を守ろう。同じ失敗をくりかえす自分は最悪です(>_<)
  5. マラソン開始日前に、もやもや要素をすべてとりのぞく。何も用事がない・借りがない状態でマラソンをスタートしましょう!
  6. マラソン期間中に、アクシデントにまきこまれない。普通の生活をしよう。
  7. Javaを自分の場合つかわないので、Javaでの採点部分や、scan部分などは、できるだけはやくC++に移植する。
  8. ちゃんとマラソンスタートしたら、はじめる。毎日安定してやる。
  9. はやめにスタートしたほうが、計算リソースを有効に使える。
    • ぎりぎりなってからだと常にパソコンでプログラムを書きたいので、計算結果待ちとかの時間が無駄。はやいうちにスタートしておけば、夜中に計算とか、出勤中に計算とか、有効に計算リソースを使うことができる。
  10. パソコン2台あるのを有効に使う

ポイント

(いろいろあったのですが、マラソンRound2前に書く時間がなくなってしまったので、すごいてきとーです・・・。せめてツールの画像だけでも。本当は画面右側に文字情報のリストが表示され、選択中のものだけ色を変えたりすることもできます。)


基本的には重なる黒のマスが多い文字からおいていったのだが、上のIのように、TLEはIに負けたりする。つまり、
「実際にはかなり合ってるのに、登場することができない不幸な文字があるのでは?」
と思い

  • 外れている文字を使ったら選ばれにくくする
  • 答えにあるのに使わない文字があったら選ばれやすくする

というのを多くのテストケースでまわし、文字の選ばれやすさの重み付けを決めるという方針で行った。
しかし、結果はほぼ効果がなかった。実際には、ほとんどの文字の「当たっているのに選ばれない」=「当たっていないのに選ばれる」の確率はITLEなどを除き、ほぼ一緒になってしまった。