こんにちは。競技プログラミングをしているssaattooと申します。AHCをみんなで解く会（皆解会）というコミュニティで「第２回日本橋ハーフマラソン 予選 A ゲーム実況者Xの挑戦」のバーチャルコンテストが開催されていたので参加して，１位でした．
反省、または誰かの為になることを期待して参加記録を残します。
問題概要
50×50のマップが与えられ，各マスは壁・罠・コイン・空（カラ）・プレイヤーのいずれかに属しています．プレイヤーは１ターンに上下左右に１マス移動できます．壁のマスには侵入できず，罠にかかるとそのターン以降プレイヤーは行動できず，コインのマスに入るとコインを１枚獲得でき，そのマスは空のマスになります．
マップが100個与えられるので，その内８個を選択してください．各マップのプレイヤーは同一のコマンドで操作されます．2500ターンの操作を決定してコインをできるだけ多く獲得してください．
解法
解法の概要
壁と罠の個数の和が小さい順にマップを８個選択しました．各深さで状態をコピーするナイーブなビームサーチを行いました．ビーム幅は2200でした．
解法の詳細
問題固有の性質：マップの選択について
最初に壁と罠の個数の和が小さい順にマップを８個選択しました．マップは100個与えられますが，全てをコピー・シミュレーションした場合に計算量が最大で25倍になること，また複数の状態を保持していたとしても始めの数百ターンで上位８マップと大きな差が開くことから最初に８個のマップに絞りました．
移動の自由度が大きくなることを期待して，壁と罠の個数を小さい順に選択しました．他にもプレイヤーの初期位置が近いマップを選択する方法などを試しましたが，これが一番良くて10000点ほど伸びました．
ビームサーチ一般の性質：高速化・多様性
ビーム幅は2200確保できました．そのために工夫した高速化点を列挙します．
- 状態のコピーは次の深さの起点となるビーム幅個分のみ行う：今回は１つの状態から４つの状態が生み出されるため，４倍の高速化が期待されます．
- 一般的に deque を使用する部分を２本の配列を持ち，深さの偶奇で使いまわす．
- 盤面の状態を bitset で保持してコピーコストを削減する．
- 上下左右の操作列を bitset で保持してコピーコストを削減する．
- priority_queueなどを使う部分をnth_elementに変更する．
ビームサーチでは同じ点数であっても，似たような状態より違う親から生成された状態を保持することが重要です．状態の多様性を保つために行った点として，コイン２～６枚程度の乱数で生成したペナルティをスコアに加えました．また，nth_elementもきちんとしたソートでないため，多様性に貢献したかもしれません．
終わりに
ビームサーチを久しぶりにさわれてよかった．コピー方式のものだけでなく，シミュレーション方式のビームサーチも理解したい．
