AtCoder Heuristic Contest 002(AHC002) -Walking on Tiles- 参加記
問題
結果
4,997,673点で37位。橙パフォ取れたので満足。AHC001は初回だからパフォ低く出てたみたい。
考えたこと
問題見てすぐビームサーチかと思ったが、点数の高いマスを踏むより、できるだけ長いパスを作る方が大事なので、生スコアを評価値にしてビームサーチは上手くないというのは分かる。隙間がないようにパスを作成したいので、パスが空白領域を囲むようにしたらペナルティみたいなことか、と考えるが高速に計算できる気がしない。
提出1(1時間46分): スコア 3,037,491
なのでとりあえず、次に踏むタイルに隣接する使用済みのマスの個数が多い順にDFSする。
提出2(1時間54分): スコア 4,266,096
もっと単純に、中心から先に埋める or 外周から先に埋める、とすれば良いのではと思い、外周からの距離を評価値にしてDFSをする。マス(x, y)の評価値はmin(x, 49-x, y, 49-y)で、外周から埋めた方が良さそうだったので、評価値が低い順に辿る。
提出3(2時間46分): スコア 4,640,617
時間いっぱいDFSしても、おそらくパスの末端を沢山探索することになってスコアが伸びていないと思い、1回のDFSを100msにして、現時点でのベストのパスの途中から別の経路でDFSをやり直す。やり直す地点は、始点からパス長の8割の地点の中からランダムに選択する。
提出4(3時間2分): スコア 4,897,359
パラメータ調整する。1回のDFSに100msもかけなくて良さそうなので、1回3msにする。やり直し地点もパス長の9割からランダムに選択にする(これは適当)。
提出5(3時間14分): スコア 4,921,754
パラメータ調整する。DFSを1回1msにする。
提出6(3時間33分): スコア 4,991,227
パラメータ調整以外に変更できそうなのが、DFSの探索順のための評価値くらいしかないので、そこを変更する。あまり重い計算にすると、探索し直しの回数が稼げないので、O(1)で評価したい。現状min(x, 49-x, y, 49-y)となっているのを、min(x, 49-x) * min(y, 49-y) に変更するとスコアが改善した。O(1)で軽く計算できるのをとりあえず試しただけだったが、辺より隅の方が重要視されて踏み残しが減るということかと思う。
提出7(3時間42分): スコア 4,997,673
評価値を(min(x, 49-x) * min(y, 49-y))2に変更する。
後は乱数のシード変えたり、お祈り提出をするもスコアは上がらずに終了。
反省点
- 最初DFSを時間管理がしやすいようにstackで実装しようとしたが、無限にバグらせて時間を浪費した。結局再帰で実装した。4時間だとアルゴ力必要だよなぁ。。
- パスを部分的に改善は端から無理だと思って考えていなかったけど、それが正解だったらしい。そこら辺の判断ができないと上位行けない。。
