この問題はDP(メモ化再帰)により解くことができます。

\(f(k,S)\) を「あと \(k\) 回ダイスを振ることができる時点でキープしているダイスの出目の多重集合が \(S\) であるときの、ゲーム終了時の得点の期待値の最大値」と定めます。

\(f(k,S)\) を求める際には、キープしていないサイコロの出目の多重集合 \(P\) 及びそれらのうちキープするものの多重集合 \(T\) を考えることで、

\(f(k,S)=\begin{cases} \sum_P \mathrm{prob}(P)\max_{T\subset P}f(k-1,S\cup T) & \text{if } k>1\\ \sum_P \mathrm{prob}(P)\mathrm{Score}(S\cup P)& \text{if } k=1 \end{cases}\)

となります。ここで、\(\mathrm{Prob}(P)\) は出目の多重集合が \(P\) になる確率、\(\mathrm{Score}(S)\) は出目の多重集合が \(S\) でゲームを終了したときの得点を表します。

求める値は \(f(3,\emptyset)\) です。

\(f(k,S)\) が \(f\) を呼び出す回数は \((P,T)\) の組の個数なので明らかに \(6^{5-|S|}\times 2^{5-|S|}\) 回以下であり、メモ化再帰で \(f(3,\emptyset)\) を求めるための \(f\) の再帰呼び出し回数は \(2\sum_S 12^{5-|S|}\leq 10^6\) となります。

\(\mathrm{prob},\mathrm{Score}\) は \(6^5\) 通りを全列挙する前計算により \(O(1)\) で求まるとしてよいため、これにより十分高速にこの問題を解くことができます。

以下の実装例では、\(P,T\) の列挙を多重集合としてではなく単に列としてそれぞれ \(6^{5-|S|}, 2^{5-|S|}\) 通り列挙しており、\(\mathrm{Score}\) の前計算も行わず、さらに全ての計算を有理数クラスを用いて行っていますが、実行時間には十分余裕を持ってACすることができます。

writer解(Python)