参加してきました。予選は残念ながら勝ち進めなかったのでオープンコンテストでの参加です。 順位は本戦・オープン合わせた提出者217人中、11位（スコアは3,100,833点）でした。 まさかここまで上がれるとは思っていなかったので、自分でもびっくりしています。
問題概要
- 50x50マスの山を掘って鉱石を採掘する
- 採掘にはコストがかかる
- あるマスを採掘するとき、周りのマスの採掘状態によってコストが変動する（周りが採掘済みだとコストが安くなる）
- （鉱石の価値）－（コスト）を最大化せよ
HTTF恒例のビジュアライザも付いているので、そちらを貼った方が分かりやすいですね。だいたいこんな感じで無駄を出さないようにうまく鉱脈を掘りましょう、という問題です。下手に掘るとすぐにコストが膨れ上がるので、最初のうちは入力例の盤面で正の得点を出すのも結構難しかったです。
考えたこと
焼きなまし大好きおじさんなので、焼きなましに落とし込めないか考えました。
- 坑道みたいになると1マスあたりの採掘コストが高くなりがちなので、露天掘りっぽく掘れると嬉しい。
- 掘らないなら大きな塊ごと掘らないと決めた方が良いので、1点Flipの焼きなましはあまりよくなさそう。
- どのマスを掘るか決めてしまえば掘る順番はBFSでよさそう（厳密解を出すかどうかは未証明だけど、少なくとも大きく悪くなることはなさそう）。
- コスト差分計算が難しそう。あるマスをFlipしたとき、それが原因で到達できなくなるマスがないか効率的に求める手段が思い浮かばない。
差分計算が重そうなこと、解空間があまり滑らかでなさそう（連結か非連結かでスコアが大きく変わる、坑道を繋ぐためには一旦コストが高くなる解を経由しないといけない）なことからあまり焼きなまし向きではないような気もしましたが、他に良い方針も思い浮かばなかったのでそのまま進めました。
やったこと
上を踏まえて、（紆余曲折の後に）以下のような実装にしました。
- 「どのマスを掘るか？」を焼きなまし。掘る順番は適当にBFSで決める。
- 「全部のマスを掘る」を初期解とする。
- 変形操作は「ランダムな矩形領域を選んで、『全て掘る』か『全て埋める』にセット」とする。
- スコア計算は毎回愚直BFSでシミュレーション。
- BFS時にたどり着けないマスは完全に無視。
- シミュレーションでの掘る順番をそのまま解として出力。
どう考えてもスコア計算が激重で、 回くらいしか回ってくれませんでした。ただ実行時間を延ばしてみてもあまり改善しないので、これ以上スコアを伸ばすには変形をもっと上手くやる等の方針の方が良いかもしれません。
HTTF本戦お疲れ様でした！310万点でオープン2位。
— TERRY (@terry_u16) 2020年12月12日
やったことは、
・どのマスを掘るか焼きなまし。掘る順番は適当に多点スタートBFS。
・変形操作は適当な長方形領域を選んで壁か穴に変更。
・スコア計算は愚直にシミュレーション。
という感じ。そこから先が続かなかったなあ……。 #HTTF pic.twitter.com/5HFMEMMhgQ
コンテスト中で一番スコアが高かった解答はこんな感じ。単純なことしかやっていないので実装は200行ちょっとで、そんなに重くなかったです。*1
Rustについて
焼きなましは試行回数が命ということで、今回C#に代えてRustを初めて実戦で使いました。Borrow checkerにもっと怒られるかと思いましたが、練習の甲斐あってかスムーズに書けて一安心。 ただ何も問題がなかったかというとそうでもなく、以下のような箇所で悩んだりもしました。
dbg!マクロ（変数の値の出力）がReleaseでも動作することに気付かず、最初全然試行回数が稼げず悩みました（毎回BFSしているのでそのせいかと勘違いしていた）。コメントアウトすると試行回数が50倍くらいになってビビるなど。- Releaseだとなぜかコンソールから入力を受け取ってくれず、しばらくDebugモードでテストしていました……。
どちらも無事解決したので、次からはもっとスムーズに書けそうです。
感想
11位を取れるなんて全く思っていなかったので、とても満足です。なんですが、焼きなましに固執してしまった感があるのは反省点ですね。Writer解はフロー+ビームサーチだそうで、自分の10%増しくらいのスコアを取っていて震えました。もっと使える手札を増やしていきたいところです。
あと相変わらずビジュアライザを見るのが楽しくて、ついつい眺めてしまいました。自分の書いたコードがちゃんと動いてそこそこ良い解を出してくれているのを見るとなんとなく嬉しくなっちゃいますね。もちろん考察する上でもとても助けられました。ただビジュアライザのないコンテストも多いので、自分でも作れるようになった方がいいかもなあ、とは感じました。
最後に。
あの、今からでもratedになりませんか？
*1:実は焼きなましではなくただの山登りになってしまっているのですが、それはまた別のお話……。
