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

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. 他のピンを動かせば道ができる場合はそれも試す(別ピンの動きは2手まで)
  4. 1番点数の高い最終盤面を使って1へ

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

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

 

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

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

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

 

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

 

  • TCO2015マラソンの感想

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

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