6,493,441,713点で 109位/799人 でした。
提出コードがこちらで、 Submission #30422442 - Monoxer Programming Contest 2022（AtCoder Heuristic Contest 009）
Seed1のビジュアライズ結果が以下になります*1。
— gobi (@gobi_503) 2022年3月26日
解法とコンテスト中の流れについて書いていきます。
解法
ビームサーチをしました。 設定は、
- 遷移: 移動全パターンを１回実行
- 評価値: 各マスについての
(そのマスに居る確率) * (ゴールからの距離)の合算値（小さい方が優位） - ビーム幅: 400
としています。
コンテスト中の思考・行動の流れ
- とりあえず空文字を出力する。0点。
"UDLR"を繰り返し出力。88K点。- 入力制限的に、、必ず自宅の右下にオフィスがあることが分かったので、
"DR"を繰り返し出力。393M点。 - ビジュアライザから、詰まってしまうケースが多いことに気づいたので、たまに上左への移動を交えた、
"DRDRURDRDL"を繰り返し出力して 1.9G点。ここまでで30分くらい。 - 一旦問題文をじっくり読む。
- 入力生成は別段特徴は無さそうだなと思った。
- 得点計算式は、早くゴールできる加点よりも、オフィスに到達できないケースの減点の方がウェイトが大きいように見えた。けどだからどうすればいいのかは浮かばず。
- ビジュアライザの赤色情報(そのマスに居る確率)は、解法作る上でもかなり役立ちそうだなあとかを思う。
- ローカルビジュアライザから、そのマスに居る確率の計算コードを移植する。バグったりもあって、ここまでで2時間くらい。
- 貪欲法を組む。移動方向ごとに、
(移動による各マスのゴールからの距離の変動) * (移動元のマスに居る確率)を合算し、最もスコアが良かった方向に移動するというもの*2。4.3G点。バグり散らかしてここまでで3時間15分くらい。順位も218位と微妙で焦る。 - 「残り45分で試せそうな方法って何かな」「がっつり残してる実行時間を使えると良さそうだな」とかを考えて、解法章で説明したビームサーチを試した。幸い当たりで、スコアが伸び6.49G点。これが最終スコアになる。
- 評価値
(そのマスに居る確率) * (ゴールからの距離)の(ゴールからの距離)を1.2乗倍する、を試していたが、TLEを踏んでコンテスト終了*3。
所感
まずまず自分的には良い順位が取れたので、満足感は高かったです。
移動結果が確率的に扱われる問題をマラソンで触れたのは、個人的には初な気がしました。 あんまりセオリー的なところも分からず、理詰めでどうこうってよりは、まあこうすれば良くなるはずだよなって感覚のところを試し打っていく方針になって た気がします。 ただ、実装を結構バグらせてしまい、試行よりもそこの修正に時間を取られてしまったのがやや残念でした。
TLを眺めてた感じだと上位陣は焼きなまし解が多そうに見えましたが、遷移とかどうしているのでしょうか。 じっくり読んでいこうと思います。
