以下のようなDPで解くことができます。

• \(dp[i][j] = i\) 番目のお店を訪れた後、魔法の財布に \(j\) 円が入っているときの買った商品の最大数

この DP は以下のような手順で解くことができます。(\(x = \max(x,y)\) を \(x \leftarrow y\) と表記します)

• はじめ \(dp[i][j] = -\infty\) とする
• 最初のお店に入る時点での魔法の財布に入っている金額の候補は \(X\) 円とその並び替えなので、任意の \(X\) の並び替え \(x\) について \(dp[0][x]=0\) とする
• \(i\) 番目のお店で買い物をする場合としない場合それぞれについて遷移を行う
  • 買う場合は \(dp[i+1][j-A[i]] \leftarrow dp[i][j]+1\)
  • 買わない場合は \(dp[i+1][j] \leftarrow dp[i][j]\)
• 魔法を使う遷移を行う
  • 任意の \(j\) の並び替え \(s\) に対し、 \(dp[i][s] \leftarrow dp[i][j]\)
  • 以下の \(2\) 通りの遷移のさせ方がある

遷移1

並び替え \(s\) を全列挙する

• next_permutation(C++)やitertools.permutations(Python)などを用いると実装することができます

実装例(C++)

遷移2

互いに並べ替えられるものを一箇所に集め、それを遷移先に配る

• たとえば並べ替えの最大値( \(1123\) では \(3211\) )に集めることで達成できます
• 数式を用いて述べると、\(S[j] :=\) (魔法を使って \(j\) 円から並べ替えられる金額の最大値) として、 \(dp[i][S[j]] \leftarrow dp[i][j]\) とした上で \(dp[i][j] = \max(dp[i][S[j]],dp[i][10 \times S[j]],dp[i][10^2 \times S[j]],\cdots)\) とします

実装例(C++)

以上の手順を終えたのちの \(\max_{0 \leq j < 10^L}\{dp[N][j]\}\) が答えとなります(\(L\) は \(X,A_i < 10^L\) を満たす整数の最小値)。

以下、 \(M := \max\{X,A_i\}\) とします。

遷移1を使う場合は \(dp[i][j]\) が全部で \(O(NM)\) 個あり、それぞれの遷移が \((\lfloor\log_{10} (10^L)\rfloor)!\) 個あるため、時間計算量は\(O(NM (\lceil \log_{10} M \rceil) !)\) です。

遷移2を使う場合は遷移の個数は全体で \(O(NM)\) 個となりますが \(S[j]\) を求めるために \(O(M (\log M)^2)\) 時間かかるため、時間計算量は \(O(NM + M (\log M)^2)\) となります。