https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16494&compid=12525
ルール
- グリッドの中に迷路っぽいものがあります
- 迷路の周囲のセルを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の結果を示します。中のほうまで行けていません
反省
- 上位陣はビームサーチだそうです。「2つの操作の間で依存関係が強いから」だそうです。納得
- せめてvalid pathを全部表示するくらいのビジュアライザは作るべきでした (上位陣はほとんど作ってた)
gettimeofdayが遅いのを忘れていました… (Komakiさんのブログ参照)
