エンジニアの競馬情報収集ブログ

最近は5割が競馬の話、3割がLoL/LJLの話、2割が技術的な話な感じ。たまにその他の話。

AOJ 1345: Bit String Reordering

問題

ランレングス符号化というものがある。例えば 0111001 3 2 を表す。最初に0が"1"個、次に1が"3"個、最後に0が"2"個、なので、0111001 3 2 となる。同様に、1000111 3 2 を表す。このように、0からスタートするものと、1からスタートするものと、ランレングス符号化のしかたには2種類あることをまず留意しておきたい。

入力は2つの数字列である。入力例1を使って問題を説明する

7 2 
1 1 1 0 0 0 0 
4 3

この場合、1110000 を、隣同士のビットのスワップだけを使い、4 3 つまり、1111000 または 0000111 を表現したい。そのスワップ回数を求めればよい。11110001110000 とは、1と0の数が異なるため、スワップだけでは変換できない。そのため、隣同士のスワップだけを用いて、11100000000111 にする。これに必要なスワップ回数は12回である。

方針

  • 11100000000111 にすることを考える。
  • 左のbitから順に見ていく。
  • 一番左のbitは異なっている。
  • そこより右の部分から、最も近くて反転しているbitと入れ替える
1110000
1101000
1011000
0111000
  • これを繰りかえして貪欲にbitを入れ替えていけばおk
  • 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;
    }
}