並び替えが決まっているときの、コスト計算

アルファベット全体の集合を \(\Sigma\) と置きます。長さがともに \(\sigma\) である文字列 \(s, \ t\) に対し、

\[ \mathtt { demand } ( s, t, \sigma ) = \# \lbrace j \in [ n ] \vert s _ j = \sigma, t _ j \neq \sigma \rbrace \\ \mathtt { supply} ( s, t, \sigma ) = \# \lbrace j \in [ n ] \vert s _ j \neq \sigma, t _ j = \sigma \rbrace \]

と定めます。すると文字列 \(s\) とその並び替え \(t\) に対し、コストは

\[ \sum _ { \sigma \in \Sigma } \mathtt { demand } ( s, t, \sigma ) \]

で与えられます。また、\(\mathtt { demand } ( s, t, \sigma ) = \mathtt { supply } ( s, t, \sigma )\) が成り立ちます。

並び替えが途中まで決まっているときの、コスト最小化問題の解き方

\(t\) の先頭 \(i\) 文字である、\(t [ 0, i [\) が決まっており、かつ各アルファベットについて、\(s\) に登場する回数よりも \(t [ 0, i [\) に登場する回数のほうが大きくないとします。このとき \(t [ i, n [\) を決めて \(s\) の並び替えにすることが可能です。そのようなやり方のうち最もコストの少ないもののコストは

\[ \sum _ { \sigma \in \Sigma } \mathop { \mathrm { max } } ( \mathtt { demand } ( s, t, \sigma ), \mathtt { supply } ( s, t, \sigma ) ) \]

で下から抑えられます。一方この下界を達成する並び替えを構成することも可能ですから、最小コストはこれになります。

もとの問題の答え

前から順に決めていくことで、文字を使いすぎないかつ上記のコストが \(k\) 以下である状態を保ってなるべく小さな文字を選んでいくことで解けます。

現在のコストと \(\mathtt { demand }, \mathtt { supply }\)とその max、そして残り使える文字の重複度付き集合を管理することで定数時間で判定できますから、全体で \(\Theta ( N \vert \Sigma \vert )\) で解けます。