\(k=1,2,\ldots,9\) に対し \(C_k\) を \(T\) の中で文字 \(k\) が出てくる回数とします。

操作を逆から考えることで、一連の操作は以下のように言い換えることができます。

• \(x=1,2,\ldots,9\) に対し、 \(S\) の好きな箇所を \(x\) に置き換える操作を \(C_x\) 回以下行うことができる。 … \(\text{(A)}\)
• ただし、 \(T_M\) に置き換える操作は \(1\) 回以上行う必要がある。 … \(\text{(B)}\)

まず、条件 \(\text{(B)}\) を無視し、条件 \(\text{(A)}\) のみを考えた際の最大値を考えます。

すると、以下のような貪欲が最適であることが分かります。

• \(k=1,2,\ldots,N\) に対し、以下の操作を行う。
  • \(S_k < x\le 9\) と \(C_x \geq 1\) を満たす \(x\) の最大値を \(X\) とすると、 \(S_k\) を \(X\) で置き換え、 \(C_X\) から \(1\) 引く。そのような \(x\) が存在しない場合は何もしない。

この手順で得られる \(S\) を \(S'\) とします。条件 \(\text{(B)}\) を追加で考えた際に、答えが \(S'\) からどれだけ小さくなるかを考えます。

まず、\(S'\) の中に文字 \(T_M\) が含まれる場合は

• 既に \(T_M\) を操作として使っている場合は条件 \(\text{(B)}\) を満たしている。
• \(T_M\) を使っていない場合はその箇所に操作をすることで条件 \(\text{(B)}\) を満たすことができる。

ので答えは \(S'\) となります。

逆に、\(S'\) の中に文字 \(T_M\) が含まれない場合は \(S'\) のどこかの箇所に \(T_M\) を上書きする必要がありますが、減る値が最も小さくなるのは \(S'_N\) への上書きです。

以上を適切に実装することでこの問題に正答することができます。計算量は \(O(N+M)\) です。

実装例(Python3)

n, m = map(int, input().split())
S = [int(c) for c in input()]
T = [int(c) for c in input()]
cnt = [T.count(i) for i in range(10)]
for i in range(n):
    for j in range(9, S[i], -1):
        if cnt[j] > 0:
            cnt[j] -= 1
            S[i] = j
            break
if not T[-1] in S:
    S[-1] = T[-1]
print("".join(map(str, S)))