概要
Heuristic contest タイプの問題です。
現時点（2021/02/25）で、1 位のスコアが出ています。しかも、（解説 PDF と比べても）かなり少ない実装量です。
というわけで、書いておきます。
アルゴリズム
「掛け算・割り算ばかりで目標数を作る」というのが基本方針です。例えば、目標数が $1234$ ならば、$$4 * 5 * 5 / 3 * 3 * 5 / 2 * 5 / 2 * 2$$ というような式を探します。
目標数から遡っていくことで、探索します。例えば、$1234$ ならば、 最終手は
- $677 * 2$
- $2468/2$, $2469/2$
- $3702/3$, $3703/3$, $3704/3$
- $4936/4, \ldots$
など。直前の時点で「$677, 2468, 2469, 3702, \ldots$」などが可能です。これらは簡単に全列挙できます。
そこで、目標数から、可能な直前の点へと探索を進める幅優先探索を行います。ゴールは $1, 2, 3, 4, 5$ のどれかです。
当然、これだけだと、状態数はどんどん巨大になってしまいます。そこで、最適解につながりにくそうなものを枝狩りします。
単純に、巨大整数を枝狩りして、小さな整数を残すことにします。
- maxsize を固定する。
- 目標数 $n$ 手前の状態を列挙したとする。$n+1$ 手前の状態が列挙できる。
- それらをソートして、小さい方から maxsize 個残す。
maxsize を $n$ に応じて変化させることも考えられそうですが、私は単に定数として実装しました。
141.98 点
maxsize = 100 として → 141.98 点（https://atcoder.jp/contests/pakencamp-2018-day3/submissions/15217464）
これで 1 位スコアです。かなりあっさり。
143.59 点
maxsize = 500 として → 143.59 点（https://atcoder.jp/contests/pakencamp-2018-day3/submissions/15217590）
実行時間ぎりぎりまで。手元ランダムケース実行で maxsize を大きくしても、ほとんど得点の増加は見込み目内ようです。
144.19 点
$1234 = 5 * 5 * 5 / 3 * 2 * 3 * 5 + 4$ というように、最後にすこし足し算をするパターンも解の候補に含めます。
実装の複雑化はほとんど起こりません。$1$ 手目からの探索状態に $1229, 1230, 1231, 1232, 1233$ を追加。 $2$ 手目の状態に$1224, 1225, 1226, 1227, 1228$ を追加。といった要領です。144.19 点が実現できました（https://atcoder.jp/contests/pakencamp-2018-day3/submissions/15218616）
コメント
ランダムケースで確認した限りは、同じ方針で探索回数などの計算コストを増やしても、スコア改善は難しいようです。
かなりロジックも簡単だし実装も軽い解法での圧勝スコアという感じでびっくりしました。多倍長整数の使用が前提で、取り組んでいる人が少ない問題という点もあるかもしれません。
（2021/04 追記）これ多分「ビームサーチ」ってやつですね。
