本番の解法+本番後の解法メモ

各解法の簡易説明とScore、提出、本番での順位相当を記載した。本番での順位相当は見間違えていたらすみません。

本番での解法

1投目

Score: 120000 何もしない 本番947位相当

2投目

Score: 341006 提出 本番788位相当
ある操作を福を出さない範囲で連続して行い、最も福を追い出すことのできる連続操作を行う貪欲。 これを鬼がいなくなるまで繰り返す。 鬼が四方を福に阻まれている場合は諦める。

3投目

Score: 451706 提出 本番433位相当
鬼が四方を福に阻まれている場合の処理の追加。 鬼のいる行、列に対して福を追い出さないLRUDいずれかの操作を1回行い貪欲を続行。 もし鬼のいる行、列の全ての両端に福がいたら諦める。

4投目

Score: 456411 提出 本番389位
貪欲の評価をtrunあたりに減らせる鬼の数に変更。

本番後の解法

(ビームサーチの前に)

Score: 458356 提出 本番356位相当
本番での貪欲では、取り出せる最大個数の場合のみを考慮していたが、全ての候補を考える。 例えば最大\(n\)個取り出せる場合は、\(1, 2, \ldots, n\)個取り出す場合の全てを考慮する。

ビームサーチ

Score: 465788 提出 本番80位相当
遷移の候補としては上記のものプラスして鬼のことを考えず1回操作するものを加える。 評価値は盤面の鬼の数。
ビームサーチはrhoo19937さんのbeam-search-libraryにあるnormal_beam_multiを使って実装した。重複除去は行っていない。
ビーム幅5000。時間の余裕はあったがメモリが足りなかった。

ビームサーチ+hash

Score: 466757 提出 本番36位相当
zobrist hashを用いて重複を除去した。 ビーム幅10000
[追記] 重複除去した後に残った(採用された)盤面が seed0で最大3500程度であったため、幅3500相当であったのかもしれない。