モノグサプログラミングコンテスト（AtCoder Heuristic Contest 009）お疲れ様でした。7,547,834,181点で1位です。ratedコンテストで1位を取ったのは初めてなのでとても嬉しいです。

いつものように解説記事を書きます。

f:id:terry_u16:20220327125528p:plain — ビジュアライザ (seed=0)

問題概要
前提知識
方針
解説
- 初期解の生成
- 焼きなましによる改善
考えたこと・やったこと
感想

問題概要

忘れっぽい高橋くんをできるだけ高確率で出社させてね。

説明のため、以下の語句・文字を定義しておきます。

語句・文字	意味
操作列	解として出力する文字列
$N$	地図の一辺の長さ $(N=20)$
$T$	操作列の最大長 $(T=200)$
$t$	ターン数 $(1\le t \le T)$
$i$	マップの縦方向座標 $(0\le i \le N-1)$
$j$	マップの横方向座標 $(0\le j \le N-1)$
$p$	高橋くんが操作列の $t$ 文字目を忘れる確率 $(0.1\le p \le 0.5)$

前提知識

ダイクストラ法
期待値DP
焼きなまし

方針

焼けるので焼きます。*1

こういう手順を構築する系の問題は解の一部を変更するとその後の動きがガラッと変わるため焼くのが困難なことが多いのですが、今回の問題はビジュアライザを見ても分かるように高橋くんがどんどんぼやけていくため、評価関数が滑らかになって意外と焼けます。

$p$ が大きいほどぼやけやすいため、そういうケースだと焼きなましが比較的強かったのではないでしょうか。逆に $p$ が小さいケースだとぼやけづらく評価関数がガタガタになるため、そういうケースだと貪欲やビームサーチの方が強かったかもしれません。

解法の流れは以下の通りです。

初期解を生成する。
1. スタートからゴールまでダイクストラ法で最短経路を求め、操作列を構築する。このとき、辺の重みはランダムに決定する。
2. 操作列のうちいくつかの文字をランダムにダブらせる。
3. a.～b.を複数回繰り返し、最も良かったものを初期解とする。
焼きなましで解を改善する。

f:id:terry_u16:20220327182124g:plain — ビジュアライザ (seed=1 : 68,441,516点)

解説

初期解の生成

焼きなましをするにしてもまっさらな状態から操作列を構築していくのは絶望的なので、まずは初期解を作ります。

今回の問題は焼きなましの結果が初期解に大きく左右される*2ので、できるだけ良い初期解を作りたいです。そのためランダム性を入れて初期解を多数構築し、最も良いものを選ぶことにします。

一旦「高橋くんは確率 $p$ で $t$ 文字目を忘れる」という点を無視し、ダイクストラ法でスタートからゴールまでの最短経路を求めます。この時、多様性を持たせるために辺の重みは $[10,30]$ から毎回ランダムに決定します。最短経路が求められたら復元を行い、ひとまずの操作列とします。

操作列が求められましたが、高橋くんがこの操作列の通りに動く確率は、操作列の長さを $L$ として $(1-p)^L$ しかありません。そのため、いくつかの文字をダブらせることでより高確率でオフィスにたどり着けるようにします。例えば高橋くんが確率 $0.5$ で文字を忘れてしまう場合、全ての文字を $2$ 個ずつダブらせればそこそこ良い感じになりそうです。*3 この考え方を拡張し、操作列の長さが $\mathrm{round}(L/(1-p))$ となるように文字をダブらせることにします。ダブらせる文字はとりあえずランダムに選びます。