文字の定義等は解説pdfに準拠します。

python等の多倍長整数が使える言語なら、

\(dp_{i} :=\) ちょうど \(i\)本のマッチ棒を使って、条件を満たす整数を作るときの最大値

として公式解説の解法より軽実装な解法で直接解を求めることができます。

遷移は\(dp_{i} = max_{j}(dp_{i−num(A_{j})}×10+A_{j})\)です。

初期値は、\(i=0\)の時\(0\),\(i<=-1\)の時\(-∞\)です。

dpの値の桁数がiに比例して大きくなっていくので、計算量は\(O(N^{2}M)\)ですが、そのうち\(O(N)\)部分は\(O(N)\)桁の整数同士の比較や計算ですので定数倍が非常に軽いため十分間に合います。

実装例(python,メモ化再帰)