Topcoder Open 2015 Marathon Match(Round 3)の参加日記

Topcoder プログラミングコンテスト マラソンマッチ

Round1が53位/171人、Round2が61位/171人だった。今回の目標も上位2割。

 

前回、前々回の反省点まとめ。

  1. 問題をちゃんと読む（前回は終了後に判明した誤読があった）
  2. 紙と鉛筆で考えてから組む。いきなり実装しない
  3. Web等を参考にしすぎない。アルゴリズムは自分で考え、完全に理解したものを使う
  4. ローカルのバッチ環境は早めに構築する
  5. ビジュアライザも早めに作る。なるべくデバッグ・調査しやすいように
  6. 定数組み合わせがありそうならバッチを作る。手でやらない
  7. パラメタ調整にExampleケースは使わない。ケースが少なすぎる
  8. テスタのコードを読むべき

 

  • 開催前

反省を踏まえ、あらかじめパラメタ調整用のバッチ環境を作っておいた。山登りと焼きなましを実装。前回の問題で試してみたら、けっこうスコアが上がったのがショックだった。（実際のパラメタ値も、手でやった場合とかなり異なっていた）

 

  • 問題概要
  1. NxNのセルで構成されるBoardがある（N: 20～60）
  2. M種類のピンがある（M: 1～10）
  3. ピンの種類ごとにスコアが与えられる（1～10）
  4. Boardにはランダムにピンが打ってある。空セルもある
  5. セルにピンのある確率はP（P: 0.1～0.9、与えられない）
  6. 各ピンは、隣のピンを飛び越えて上下左右のいずれかにジャンプできる。空セルはジャンプできない
  7. ジャンプ先は空セルであること
  8. ジャンプ先はBoard上であること
  9. 飛び越えられたピンは消える
  10. 連続でジャンプし、ジャンプした距離x消えたピンのスコア合計だけのスコアが入る
  11. 一回の連続ジャンプで使えるのは一つのピンのみ
  12. 獲得スコアがなるべく大きくなるように、連続ジャンプを求める（複数）
  13. 最終スコアは、各テストケースごとにベストスコアとの相対得点を求め、それを平均したもの 
  14. ピン打ちは、ランダム以外に次の方法でも行われる
    　・0～10個の点を選ぶ
    　・各点から半径1～N/4の円の内部にあるセルを同じタイプのピンで埋める
    　 （別のピンがあっても無視して上書きする）
  15. 制限時間は15秒

 

  •  結果

暫定40位/181人。また目標には届かなそうだ。

 

  • やった方法

単純に、山登りで点数が最大になる手を選んでいった。

https://bitbucket.org/yambe2002/tco-2015-marathon-round-3

  1. 盤上の全ピンでループ
  2. 対象ピンを全方向にぴょんぴょん飛ばしていく（飛べるピンがなかったら終了）
  3. 他のピンを動かせば道ができる場合はそれも試す（別ピンの動きは２手まで）
  4. １番点数の高い最終盤面を使って1へ

3を普通にやると重いので、ピン配置のパターンを10個くらい作ったのが面倒だった。

また、当然全手の探索は不可能なので、残り時間により適当に試す数を減らしていった。

 

コンテスト後のForumによると、上位陣との大きな違いは、

  1. 単純に全手を試したりしていない。ランダムに選んで深く読み、長い連続ジャンプを探すようにしてる
  2. 高速化して幅の広いサーチ（ビームサーチ）
  3. 方向もランダムにするのが重要。同じ方向パターンだと効率の悪いジャンプになる
  4. 別ピンの動きは2手以上
  5. 全然違うやり方もある（焼きなまし）
  6. コピーのオーバーヘッドを減らすため、ピンの得点は保存しない方法もある

あたりと思われる。特に1、2は今後のマラソンマッチでも重要そうなので覚えておこう。

 

  • 反省点
  1. 序盤はパフォーマンスより見やすいデータ構造を優先するべきだった

 

  • TCO2015マラソンの感想

マラソンマッチに初めて参加したが、Round1～3いずれも上位３割くらいだったのは、個人的には悪くない（だってSRMは緑だし…）。

思ったより楽しかったので、勉強がてら普段のMMにも参加しよう。