Chokudai Contest 003

参加しました。普段の競技プログラミングとはちょっと違う形式でマラソンという種目らしいです。
（恐らく）最適解が誰にも分からない状況でいかにして最適解に近づけていくか、ということを競う種目って感じでしょうか。
実験的なコンテストらしいのでレートは付きませんでしたがいつもと違う感じで楽しかったです。

最高スコア：5634

Chokudai Contest 003 - Chokudai Contest 003 | AtCoder

感想

問題を読み、理解して、さてどうしようかという感じになりました。
この手のコンテストは初めてだったのでどう取り組めばいいのかさっぱり分かりません。
ともあれ解の１つとして「どこも変えない」という自明解があることは確かですから、まずはそれを提出してみようということになりました。
すると1759点がつきました。まだ始まったばかりだったのでこれをするだけで順位表の１ページ目に乗ることができ、嬉しかったです。

これでとりあえず「自明解の点数を超える」という目標が出来ました。
しかし、これからどうしようか、どういう方針で進めばいいのかサッパリ分かりません。
なのでとりあえず「消した後の盤面を描画する関数を作ること」「消した後の盤面からスコアを計算する関数を作ること」を目標とすることにしました。
そうすることで何かヒントが得られるかもしれません。

この後ちょっとGoogle Code JamのPractice Roundに行ってたりしたので間が空きましたが、上の二つの目標は達成することができました。
点数を計算することができると、ある.を+(または-)に変えたとき、点数が上がるかどうかが分かります。だからもし点数が上がるならそこを変えれば自明解より大きくなるはずです。
それを全ての.について見ていけば、最適ではないにしろ、いくらか点数が上がるはずだと思い、やってみたらそれだけで5000点を超えました。
（実際は点数計算の関数にバグがあって上がるはずが何故か下がっておかしいな……とかやってました。幅優先探索が未だにまともに書けないみたいです）

後はそれを改善してみたり、他の方法（ある１列の.を+(-)に変えて、３つ先の列に飛んで……）みたいな方法を試したりしました、こっちはあまり良くなりませんでした。
結局最初の、「右下の.から順番に見て行って一周したらまた右下に戻って……」を時間の限り繰り返して出来るだけスコアを高くするという方法が最高でした。
こういうのって山登り法っていうみたいですね。

一応ソースコード（長いのでリンクします）
Submission #1123063 - Chokudai Contest 003 | AtCoder

最終的には１ページ目に残れなかったですが、自分なりには十分やれたんじゃないかなあと思ってます。
「消した後の盤面描画」「点数計算」この２つがちゃんと出来ただけでそれなりに満足しました。楽しかったです。