初日
問題文公開、お題は「迷路が与えられるので、セルを修正してたくさん探索しような！」です
とりあえず、まず迷路の盤面から'U'を別の要素に置き換えてみるテスト。Uターンマスはその時点で探索失敗してしまうので（盤面の外側だと大丈夫だけど1pt)
邪魔以外の何者でもないのでとりあえず消してみる。
25.86
— イカID: simanman (@_simanman) 2015, 10月 13次に、ランダムじゃなくて貪欲にしてみる。（S, R, Lに置き換えてみて一番スコアが良いやつを採用）
ちょっと上がった。
点数低いやつの結果を見てみると、外周は探索しているけど、中心部まで到達しきれてない感じか。
適当に直線決めて、それに沿うように'S'に変えていけばとりあずF点は取れるのかな、細かい点を取りに行くなら、外周を'U'に変えるとか？（微妙）
外周は'S'のほうが良さそう。というより'S'以外の値が入っているとなかなかつらい感じがする。
Forumちょっと覗く、
The 'U' cells make the maze a bit more interesting. I'm not going to give you a hint on how to use the 'U' cells :)
'U'の使いみちがあるっぽいけど本当かよ
snuke氏が作った便利ツールを今回どんどん使っていくぞ！
ひたすらSを増やして遊んでる
38.97
— イカID: simanman (@_simanman) 2015, 10月 13今日はここまで、適当にSを追加するだけではだめそう
2日目
ある任意の点から探索をはじめて、最初の方角と反対の方向を向いた時に、セルを修正するようにしてみる。
色々やって6割ぐらいはとれそうな感じ。
61.49
— イカID: simanman (@_simanman) 2015, 10月 144日目
いままでは経路を作ることを考えてたけど、盤面を一回Sで埋め尽くしてそこから、一部の盤面を元に復元していく戦略でいってみるか
1つのセルを通る方法は「上、右、左、下」の4方向あって、これが例えば正方形の盤面を全て埋め尽くした場合は各セルは4の値をもっていて、
これを元の盤面に戻すとこの値が各セルで減っていく訳だな、各セルで4つの状態を持っている
Eが存在している場合は、4つより大きくなることがある。
Uを設置すると隣接するセルの状態の数が最初は2減る、2つ目はSの場合は2減ってこのセルへの到達は不可能
Sのセルの回りにL字型にUを設置されるとそのセルへの到達ができなくなる。
5日目
色々あって、とりあず適当に盤面を生成してから、そこから山登りで盤面を更新していく方針にしてみた。
72.65
やっと7割台
最終日
日記が毎日続かないのはご愛嬌
結局5日目から方針をコロコロ変えて元に戻ってきた感じ。
戦略としては、まず山登りを始める前に初期盤面を生成します。
こんな盤面があったとして
探索ポイントがこうあるとする
例として、一番下側から探索を始めるとして
一歩目、いきなりUにぶつかってEND
だと、経路ができないのでここでSに置き換える
再度進める
今度はUでは無いが、Lを連続で踏んでしまった。この場合Uターンすると生存率が低めなので、Rに置き換えて方向を修正する
再度、探索。
ゴールすることができたので、これで1つの経路が完成。これを全ての探索ポイントから行い一番良さそうな奴を採用する。
これが1セットの作業。確定した経路のマスは次のターンから更新ができなくなる（更新したら経路が破壊されるので）
これをF（マスを修正出来る数）が0になるか、どの探索ポイントからもゴールにたどり着けなくなるまで進める。
ここまでが初期盤面作成処理。（この段階だと7割）
ここから余った時間で山登りで点数を地道に稼ぐ
実際に何するかというと、現在の盤面からEとWとSを除いたセルをランダムで2点選びこれをランダムな値に変更する。
変更後にスコア計算。スコアが上昇していたら採用。これを時間が切れるまで延々と繰り返す。（これで75点辺り）
あとはゴニョゴニョとパラメータをいじって3点伸ばす(78点）
ビジュアライザの編集
- クエリの数が多くても表示するように
- どのマスを変更したかがわかるように色づけ
今後はこの辺りもっと力を入れていこう
感想
- 見た目良さそうな問題だったけど、実際やってみると後半の伸びが無くて結講つらかった
- スコア計算の計算量が重すぎて、盤面が大きいと初期盤面の生成段階で大分時間を使ってしまう。スコア計算の実装を軽くする方法がサッパリだった
- 本当は焼きなましとかが良さそうな気がしてたけど、良い近傍が思いつかなかった。
- パラメータ調整つらい
- 時間調整つらい(80 * 80で落ちないように調整したけど、どうだろ）
- 8割台に乗るまで10sampleで進めるつもりだったので、100すら通してない、絶対システムテストでスコア落ちる
- Eマスつらい（計算量的に）
終戦準備中
使ってない変数とか関数消して終わろう
— イカID: simanman (@_simanman) 2015, 10月 26使ってないコード消したらポイント0.01減った。最適化コワ
— イカID: simanman (@_simanman) 2015, 10月 26