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

Topcoder Marathon Match 89 MazeFixing 参加記

TopCoder

https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16494&compid=12525

ルール

f:id:kujira16:20151028220556p:plain

  • グリッドの中に迷路っぽいものがあります
  • 迷路の周囲のセルをborder cellと呼びます
  • 任意のborder cellから迷路に入ります。迷路に入ったら,セルに書いてある文字に従ってセルを移動します
    • S → 同じ向きに進め
    • R → 右に90°曲がってから進め
    • L → 左に90°曲がってから進め
    • U → Uターンしろ
    • E → どのマスに進んでも良い
  • 任意のborder cellから迷路に入り,セルに書いてある文字に従って移動した軌跡をpathと呼びます。この中でも,次の条件を満たすpathをvalid pathと呼びます
    • 同じセルを2回踏まない
    • border cellから始まってborder cellで終わる

タスク

  • あなたは迷路内にあるE以外のセルをE以外の文字に変える操作が何回か行えます
  • 全てのvalid pathを計算したとき,valid pathによって踏むことのできるセルの数を最大化してください

やったこと

  • 評価関数を「valid pathで踏むことのできるセルの数 × 10000 + (validでないものも含めて) pathで踏むことのできるセルの数」と設定して山登り法を使ってみました
  • 変更するセルの選択を行うときに,「(validでないものも含めて) pathで踏むことのできるセル ∧ 隣接しているセルに得点されていないものがあるセル」というものを選んでみました
  • 同じセルを2回踏むとアウトなので,Uは基本的に邪魔です
  • プロファイラを使ってみると評価関数が重たかったので,精度を下げて近似する,呼び出し回数を減らせるように工夫する,などができないか試してみましたが,うまくいきませんでした
  • 今回はプロファイラとしてcallgrindを使ってみました。評価関数が全体の9割以上だったので,頑張って速くすると全体の5割くらいになるまでには速くなりました

結果

-seed=10の結果を示します。中のほうまで行けていません

f:id:kujira16:20151028225410p:plain

反省

  • 上位陣はビームサーチだそうです。「2つの操作の間で依存関係が強いから」だそうです。納得
  • せめてvalid pathを全部表示するくらいのビジュアライザは作るべきでした (上位陣はほとんど作ってた)
  • gettimeofdayが遅いのを忘れていました… (Komakiさんのブログ参照)

ソースコード

github.com

おすすめのリンク

shindannin.hatenadiary.com

topcoder.g.hatena.ne.jp

topcoder.g.hatena.ne.jp