AtCoder Regular Contest 043 C: 転倒距離

問題

arc043.contest.atcoder.jp

解法

最初に転倒数を求めて、それの1/2だけ転倒するようにバブルソートする。バブルソートに一部は Binary Indexed Tree を使うと高速化できる。

コード

import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public void solve() {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int[] a = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = scanner.nextInt() - 1;
		}
		int[] b = new int[n];
		for (int i = 0; i < n; i++) {
			b[i] = scanner.nextInt() - 1;
		}
		scanner.close();

		int[] ia = new int[n];
		for (int i = 0; i < n; i++) {
			ia[a[i]] = i;
		}
		int[] iab = new int[n];
		for (int i = 0; i < n; i++) {
			iab[i] = ia[b[i]];
		}

		// iabをソートする問題に帰着する

		// 最初に反転数を求める
		long inverse = 0;
		FenwickTree fenwickTree = new FenwickTree(n);
		for (int i = 0; i < n; i++) {
			inverse += i - fenwickTree.sum(iab[i]);
			fenwickTree.add(iab[i], 1);
		}
		// 反点数が奇数なら終了
		if (inverse % 2 == 1) {
			System.out.println(-1);
			return;
		}

		FenwickTree bubbleTree = new FenwickTree(n);
		int[] where = new int[n];
		for (int i = 0; i < n; i++) {
			where[iab[i]] = i;
		}

		// バブルソートでinverse/2回ソートする
		inverse /= 2;
		for (int i = 0; i < n; i++) {
			// where[i]に居るiをiまで戻すのに必要なバブルソートの数
			int bubbleSort = where[i] - bubbleTree.sum(where[i]);
			bubbleTree.add(where[i], 1);

			if (inverse < bubbleSort) {
				// これ以上Fenwick Treeを使ったバブルソートが出来ない場合、普通にバブルソートする

				// 0〜i-1まではソート済み
				int[] halfSorted = new int[n];
				for (int j = 0; j < i; j++) {
					halfSorted[j] = j;
				}

				// 反転しすぎた数（iをiまでバブルソートして移動させた時）
				int over = (int) (bubbleSort - inverse);
				int cur = i;
				for (int j = 0; j < n; j++) {
					if (iab[j] > i) {
						if (over == 0) {
							halfSorted[cur] = i;
							cur++;
						}
						over--;
						halfSorted[cur] = iab[j];
						cur++;
					}
				}

				// 出力
				StringBuilder builder = new StringBuilder();
				for (int j = 0; j < n; j++) {
					if (j > 0) {
						builder.append(" ");
					}
					builder.append(a[halfSorted[j]] + 1);
				}
				System.out.println(builder.toString());
				return;
			}
			inverse -= bubbleSort;
		}

		// もともと反転してなかった時
		StringBuilder builder = new StringBuilder();
		for (int j = 0; j < n; j++) {
			if (j > 0) {
				builder.append(" ");
			}
			builder.append(a[j] + 1);
		}
		System.out.println(builder.toString());
	}

	public static void main(String[] args) {
		new Main().solve();
	}

}

// Binary Indexed Tree のクラス
class FenwickTree {
	int[] tree;

	public FenwickTree(int N) {
		tree = new int[N + 2];
	}

	// indexまでの合計を返す
	public int sum(int index) {
		int sum = 0;
		for (index++; index > 0; index -= index & -index) {
			sum += tree[index];
		}
		return sum;
	}

	public void add(int index, int value) {
		if (value == 0 || index < 0) {
			return;
		}
		int n = tree.length;
		for (index++; index < n; index += index & -index)
			tree[index] += value;
	}

	public int findGFenwick(int v) {
		int i = 0;
		int n = tree.length;
		for (int b = Integer.highestOneBit(n); b != 0 && i < n; b >>= 1) {
			if (i + b < n) {
				int t = i + b;
				if (v >= tree[t]) {
					i = t;
					v -= tree[t];
				}
			}
		}
		return v != 0 ? -(i + 1) : i - 1;
	}

	public int valFenwick(int i) {
		return sum(i) - sum(i - 1);
	}

	public int[] restoreFenwick(int[] ft) {
		int n = ft.length - 1;
		int[] ret = new int[n];
		for (int i = 0; i < n; i++)
			ret[i] = sum(i);
		for (int i = n - 1; i >= 1; i--)
			ret[i] -= ret[i - 1];
		return ret;
	}

	public int before(int x) {
		int u = sum(x - 1);
		if (u == 0)
			return -1;
		return findGFenwick(u - 1) + 1;
	}

	public int after(int x) {
		int u = sum(x);
		int f = findGFenwick(u);
		if (f + 1 >= tree.length - 1)
			return -1;
		return f + 1;
	}

	public int[] buildFenwick(int[] a) {
		int n = a.length;
		int[] ft = new int[n + 1];
		System.arraycopy(a, 0, ft, 1, n);
		for (int k = 2, h = 1; k <= n; k *= 2, h *= 2) {
			for (int i = k; i <= n; i += k) {
				ft[i] += ft[i - h];
			}
		}
		return ft;
	}

	public int[] buildFenwick(int n, int v) {
		int[] ft = new int[n + 1];
		Arrays.fill(ft, 1, n + 1, v);
		for (int k = 2, h = 1; k <= n; k *= 2, h *= 2) {
			for (int i = k; i <= n; i += k) {
				ft[i] += ft[i - h];
			}
		}
		return ft;
	}
}