AOJ 1345: Bit String Reordering 文字列の並べ替え

問題

Bit String Reordering | Aizu Online Judge

というデータが与えられる。は0または1で、は整数である。を並び替えて、「だけ同じ文字列が並んだ後、だけ同じ文字列が並び……」という文字列を作り、その際に入れ替えた回数の最小値を返す。入れ替えは隣接した数字同士しかできないことに注意する必要がある。例えば、

7 2
1 1 1 0 0 0 0
4 3

は、「1110000を入れ替えて、0000111を作るのに必要な入れ替え回数の最小値はいくつか」という問題であり、答えは12である。

解法

最終的に完成させたい文字列を、0から始まるものと1から始まるものの2種類作り、与えられた文字列を入れ替えてそれらを作った時の最小の入れ替え回数をそれぞれ出す。上記の例では0000111と1111000をそれぞれ作り、これらを作る際にかかる入れ替え回数を求める。（ただしこの場合1111000を作るのは不可能であるため、前者の場合のみ考える）

解答コード

import java.io.IOException;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int M = sc.nextInt();

        int[] seq = new int[N];
        int[] run = new int[M];

        for (int i = 0; i < seq.length; i++) {
            seq[i] = sc.nextInt();
        }

        for (int i = 0; i < run.length; i++) {
            run[i] = sc.nextInt();
        }
        sc.close();

        int zero = swap(seq.clone(), run, 0);
        int one = swap(seq.clone(), run, 1);
        System.out.println(Math.min(zero, one));

    }

    static int swap(int[] clone, int[] run, int now) {
        int swapNum = 0;
        int k = 0;
        for (int i = 0; i < run.length; i++) {
            for (int j = 0; j < run[i]; j++) {
                if (clone[k] != now) {
                    if (k == clone.length - 1) {
                        return Integer.MAX_VALUE;
                    }
                    for (int l = k + 1; l < clone.length; l++) {
                        if (clone[l] == now) {
                            int tmp = clone[l];
                            clone[l] = clone[k];
                            clone[k] = tmp;

                            swapNum += l - k;
                            break;
                        }
                        if (l == clone.length - 1) {
                            return Integer.MAX_VALUE;
                        }
                    }
                }

                k++;
            }
            now = (now + 1) % 2;
        }
        return swapNum;
    }
}