問題
ランレングス符号化というものがある。例えば 011100 は 1 3 2 を表す。最初に0が"1"個、次に1が"3"個、最後に0が"2"個、なので、011100 は 1 3 2 となる。同様に、100011 も 1 3 2 を表す。このように、0からスタートするものと、1からスタートするものと、ランレングス符号化のしかたには2種類あることをまず留意しておきたい。
入力は2つの数字列である。入力例1を使って問題を説明する
7 2 1 1 1 0 0 0 0 4 3
この場合、1110000 を、隣同士のビットのスワップだけを使い、4 3 つまり、1111000 または 0000111 を表現したい。そのスワップ回数を求めればよい。1111000 は 1110000 とは、1と0の数が異なるため、スワップだけでは変換できない。そのため、隣同士のスワップだけを用いて、1110000 を 0000111 にする。これに必要なスワップ回数は12回である。
方針
1110000を0000111にすることを考える。- 左のbitから順に見ていく。
- 一番左のbitは異なっている。
- そこより右の部分から、最も近くて反転しているbitと入れ替える
1110000 1101000 1011000 0111000
- これを繰りかえして貪欲にbitを入れ替えていけばおｋ
- 0始まりと1始まり両方試して少ない方を出力するだけ
慣れてないと実装が難しく感じるかもしれないが、実装を見てもらったほうがわかりやすいかもしれない。
実装
class Main extends MyUtil{ public static void main(String[] args) throws Exception{ // 入出力は自作クラスを使って行っている int n = readIntMap(0); int m = readIntMap(1); int[] b = readIntMap(); int[] p = readIntMap(); int[][] rl_p = new int[2][n]; int bit = 0; int index = 0; for(int i = 0; i < m; i++){ for(int j = 0; j < p[i]; j++){ rl_p[bit][index] = 1; index++; } bit = (bit + 1) % 2; } // zero_start_p は、0からスタートしてランレングス符号化したもの // one_start_p は1からスタート int[] zero_start_p = rl_p[1]; int[] one_start_p = rl_p[0]; int ans = 1 << 28; // すくなくとも、1と0の数が等しくないと、swapによって一致させられない if(popupBitCount(b) == popupBitCount(zero_start_p)){ ans = Math.min(ans, solve(b, zero_start_p)); } if(popupBitCount(b) == popupBitCount(one_start_p)){ ans = Math.min(ans, solve(b, one_start_p)); } System.out.println(ans); } /** * ランレングス符号化された2つの配列を入力とし、 * 2つを一致させるために必要なswapの回数を求める * @return swap回数 */ static int solve(int[] b, int[] p){ int len = b.length; int sum = 0; for (int i = 0; i < len; i++) { if(b[i] != p[i]){ sum += searchSwap(p, i); } } return sum; } /** * iより右の位置で、一番近くで入れ替えられる場所を探して入れ替える。 * @return 入れ替えるのに必要なswapの回数 */ static int searchSwap(int[] p, int i){ int len = p.length; for(int j = i + 1; j < len; j++){ if(p[i] != p[j]){ return swap(p, i, j); } } return 0; } /** * iとjを入れ替えるために、隣通しのswapをひたすら行う * @return swapの回数 */ static int swap(int[] p, int i, int j){ int cnt = 0; for(int k = j-1; k >= i; k--){ int tmp = p[k]; p[k] = p[k+1]; p[k+1] = tmp; cnt++; } return cnt; } /** * 配列を入力として、1が立っているbitの数を数える */ static int popupBitCount(int[] arr){ int len = arr.length; int sum = 0; for(int i = 0; i < len; i++){ if(arr[i] != 0) sum++; } return sum; } }
