Hatena::Grouptopcoder

じじいのマラソン反省会@TopCoder

ニコニコ生放送:red.cliff.jp
TopCoderでプログラムしてみた(Algorithm Single Round Match専用):http://red.cliff.jp/topcoder.html

2011-06-01

shindannin20110601

TCO11 Round 1

01:07

結果

62位/368 Rating 1754→1795

大反省点

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

ポイント

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

f:id:shindannin:20110601092551j:image

f:id:shindannin:20110601092550j:image

基本的には重なる黒のマスが多い文字からおいていったのだが、上のIのように、TLEはIに負けたりする。つまり、

「実際にはかなり合ってるのに、登場することができない不幸な文字があるのでは?」

と思い

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

というのを多くのテストケースでまわし、文字の選ばれやすさの重み付けを決めるという方針で行った。

しかし、結果はほぼ効果がなかった。実際には、ほとんどの文字の「当たっているのに選ばれない」=「当たっていないのに選ばれる」の確率はITLEなどを除き、ほぼ一緒になってしまった。

Marathon Match 68

00:51

結果

9位/147 Rating --→1754

大反省点

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

反省点

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

ポイント

「回」型の配置パターンで62.5ptsは取れるのは予想がついたけど、「回」型の配置に気づくのが遅すぎた。また、正方形のときにしか対応できないアルゴリズムを書いてしまったので、「田」型への応用が難しくなってしまった。

唯一良かったのは、大きさの違う正方形「回」を組み合わせることにより、rcFillingScoreが満点のままで「田」型にする方法を思いついたこと。これのおかげで、上位になんとか食い込むことができた。

例えば、3等分の「田」にしたいときは、横幅がN%3==0,N%3==1は以下のような配置にできる。普通の「田」だと隙間の行ができてrcFillingScoreが下がってしまうが、これならOK.

f:id:shindannin:20110601085352j:image

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

f:id:shindannin:20110601085359j:image

あと、上位の方は

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

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