実はこの問題は、適切な言い換えによりヒューリスティック問題に帰着される問題です。

値 \(X\) が push されるたびに、

• キュー \(\lbrace2,3,4,5 \rbrace\) の部分集合 \(S\) を取ってきて \(\lbrace X \rbrace+ (S 内の要素)\) をソートしてキュー \(1\) 以外の空いているキューに突っ込む

という操作しかしないことにします。(これは \(1+(S 内の要素数)\) 回の移動操作が必要です。)

\(i\) 回目の push において選ぶ \(S\) を \(S_i\) とします。操作列 \(S_1, S_2, \dots, S_Q\) を固定することにします。すると、最悪ケースは push が \(Q\) 回来た後に pop が \(Q\) 回来るケースになり、操作列ごとの移動操作回数の最悪ケースが確定します。そのため、

• 最悪ケースで移動操作の回数が \(100000\) 回以下である \(S_1, S_2, \dots, S_Q\)

を発見すれば今回の問題を解くことが出来ます。つまり、言い換えにより今回の問題は \(S_1, S_2, \dots, S_Q\) のコストを最小化する output only 問題に帰着されました。

\(S\) の選び方でビームサーチをすることにします。スコア関数は \(\mathrm{pow}\) を選んでみました。具体的には、定数 \(c_1, c_2\) を取って

\[\left(\sum_{i = 2, 3, 4, 5} \mathrm{pow}(|Q_i|, c_1) \times c_2\right) - (これまでの移動操作の回数)\]

としてみました。(\(|Q_i|\) はキュー \(i\) の要素数)

これで \(c_1, c_2\) を適当に乱択して適当なビーム幅でビームを何回か打てば容易に \(100000\) 回を切って AC することができました。

optuna を使って最適化したところ \(68000\) 回程度まで減らせてこれがこの方針の限界のようでした。(以下は optuna の出力)

minimum = 68571.0
c1 = 1.0403696360082844
c2 = 31.680117436613344

もっとより良い評価関数を使えば回数をさらに減らせると思うので興味がある方は試してみてください。あるいはこれは試していませんが、実コストで焼きなました方がはるかに低い操作回数が可能かもしれません。