[Codeforces] Round #531 D. Balanced Ternary String

Balanced Ternary String

文字列の問題です。

考え方

題意

“0”, “1”, “2” からなる長さ\( 3n \) の文字列 s が与えられます。ここで、バランスの取れた文字列を定義します。”0″, “1”, “2”の出現する回数がそれぞれ \( n\) であるような文字列をバランスの取れた文字列と呼びます。s をバランスの取れた文字列にするために必要な最小の文字の置き換え回数でできる文字列の中で、辞書式順列で最小のものを出力します。

方針

バランスの取れた文字列は”0″, “1”, “2” の個数が \( n \) なので、sの出現する数字の個数をカウントすればこの問題を解くことができます。\( c_i\) を \( i \) の出現回数とします。

\( c_i = n \) であれば \(i\) を置き換える必要はありません。\( c_i > n \) であれば、\(n – c_i\) 回 \( i \) を別の数字で置き換える必要があります。

まず初めに、\( c_0 < n \) のとき、s を先頭から調べていき、\(c_i > n\) となる文字 \(i\) を \( 0 \) に置き換え、\( c_i = c_i – 1\) 、\( c_0 = c_0 + 1 \) とします。これを \( c_0 = n \) となるまで続けます。

次に、\( c_2 < n \) のとき、s を末尾から調べていき、\(c_i > n\) となる文字 \(i\) を \( 2 \) に置き換え、\( c_i = c_i – 1\) 、\( c_2 = c_2 + 1 \) とします。これを \( c_2 = n \) となるまで続けます。

最後に、\( c_1 <  n\) であるときは注意が必要です。\( c_0 > n\) であるときは、末尾から調べていき、\( 0 \) を \( 1 \) に置き換えます。\( c_2 > n\) であるとき、s を先頭から調べていき、 \( 2 \) を \( 1 \) に置き換えます。

コード

シェアする

  • このエントリーをはてなブックマークに追加

フォローする