simanのブログ

ゆるふわプログラマー。競技プログラミングやってます。Ruby好き

MM89参加日記

競技プログラミング

初日

問題文公開、お題は「迷路が与えられるので、セルを修正してたくさん探索しような！」です

とりあえず、まず迷路の盤面から'U'を別の要素に置き換えてみるテスト。Uターンマスはその時点で探索失敗してしまうので（盤面の外側だと大丈夫だけど1pt)
邪魔以外の何者でもないのでとりあえず消してみる。


次に、ランダムじゃなくて貪欲にしてみる。（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氏が作った便利ツールを今回どんどん使っていくぞ！

Generic Grid Editor


ひたすらSを増やして遊んでる

今日はここまで、適当にSを追加するだけではだめそう

2日目

ある任意の点から探索をはじめて、最初の方角と反対の方向を向いた時に、セルを修正するようにしてみる。

色々やって6割ぐらいはとれそうな感じ。

4日目

いままでは経路を作ることを考えてたけど、盤面を一回Sで埋め尽くしてそこから、一部の盤面を元に復元していく戦略でいってみるか

1つのセルを通る方法は「上、右、左、下」の4方向あって、これが例えば正方形の盤面を全て埋め尽くした場合は各セルは4の値をもっていて、
これを元の盤面に戻すとこの値が各セルで減っていく訳だな、各セルで4つの状態を持っている

Eが存在している場合は、4つより大きくなることがある。

Uを設置すると隣接するセルの状態の数が最初は2減る、2つ目はSの場合は2減ってこのセルへの到達は不可能

Sのセルの回りにL字型にUを設置されるとそのセルへの到達ができなくなる。

5日目

色々あって、とりあず適当に盤面を生成してから、そこから山登りで盤面を更新していく方針にしてみた。

72.65

やっと7割台

最終日

日記が毎日続かないのはご愛嬌

結局5日目から方針をコロコロ変えて元に戻ってきた感じ。

戦略としては、まず山登りを始める前に初期盤面を生成します。


こんな盤面があったとして

f:id:simanman:20151026231918p:plain

探索ポイントがこうあるとする

f:id:simanman:20151027002245p:plain

例として、一番下側から探索を始めるとして

f:id:simanman:20151027002307p:plain

一歩目、いきなりUにぶつかってEND

f:id:simanman:20151027002333p:plain

だと、経路ができないのでここでSに置き換える

f:id:simanman:20151027002431p:plain

再度進める

f:id:simanman:20151027002455p:plain

今度はUでは無いが、Lを連続で踏んでしまった。この場合Uターンすると生存率が低めなので、Rに置き換えて方向を修正する

f:id:simanman:20151027002606p:plain

再度、探索。

f:id:simanman:20151027002628p:plain

ゴールすることができたので、これで1つの経路が完成。これを全ての探索ポイントから行い一番良さそうな奴を採用する。
これが1セットの作業。確定した経路のマスは次のターンから更新ができなくなる（更新したら経路が破壊されるので）

これをF（マスを修正出来る数）が0になるか、どの探索ポイントからもゴールにたどり着けなくなるまで進める。

ここまでが初期盤面作成処理。（この段階だと7割）

ここから余った時間で山登りで点数を地道に稼ぐ

実際に何するかというと、現在の盤面からEとWとSを除いたセルをランダムで2点選びこれをランダムな値に変更する。
変更後にスコア計算。スコアが上昇していたら採用。これを時間が切れるまで延々と繰り返す。（これで75点辺り）

あとはゴニョゴニョとパラメータをいじって3点伸ばす(78点）

ビジュアライザの編集

  • クエリの数が多くても表示するように
  • どのマスを変更したかがわかるように色づけ

f:id:simanman:20151027010802p:plain:w400

今後はこの辺りもっと力を入れていこう

感想

  • 見た目良さそうな問題だったけど、実際やってみると後半の伸びが無くて結講つらかった
  • スコア計算の計算量が重すぎて、盤面が大きいと初期盤面の生成段階で大分時間を使ってしまう。スコア計算の実装を軽くする方法がサッパリだった
  • 本当は焼きなましとかが良さそうな気がしてたけど、良い近傍が思いつかなかった。
  • パラメータ調整つらい
  • 時間調整つらい(80 * 80で落ちないように調整したけど、どうだろ）
  • 8割台に乗るまで10sampleで進めるつもりだったので、100すら通してない、絶対システムテストでスコア落ちる
  • Eマスつらい（計算量的に）

パラメータ調整時のテンション


終戦準備中