TopCoder SRM 517 Div1 Medium: AdjacentSwaps

解法

mayokoex.hatenablog.com

個人的にはこれと一緒だと思った。

kenkoooo.hatenablog.com

コード

import java.util.Arrays;

public class AdjacentSwaps {
	private final int MOD = (int) 1e9 + 7;
	private long[][] dp, nCm;
	private int[] p;

	public int theCount(int[] permutation) {
		int N = permutation.length;
		this.p = permutation;

		// パスカルの三角形を作る
		nCm = new long[N][N];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j <= i; j++) {
				nCm[i][j] = (j == 0 || j == i) ? 1
						: (nCm[i - 1][j - 1] + nCm[i - 1][j]) % MOD;
			}
		}

		dp = new long[N][N];
		for (int i = 0; i < permutation.length; i++) {
			Arrays.fill(dp[i], -1);
		}
		return dp(0, N - 1);
	}

	// p[left]からp[right]までをソートする方法の数
	private int dp(int left, int right) {
		if (right == left) {
			return 1;
		}
		if (dp[left][right] >= 0) {
			return (int) dp[left][right];
		}

		dp[left][right] = 0;
		outer: for (int i = left; i < right; i++) {
			int[] pLeftRight = Arrays.copyOfRange(p, left, right + 1);
			int[] pHalfLeft = Arrays.copyOfRange(p, left, i + 1);
			Arrays.sort(pLeftRight);
			Arrays.sort(pHalfLeft);

			/*
			 * p[left]〜p[right]をソートしてもp[left]〜p[i-1]までの数字が
			 * p[left]〜p[i-1]の中に含まれているかを調べる
			 */
			for (int j = left; j <= i - 1; j++) {
				if (pLeftRight[j - left] != pHalfLeft[j - left]) {
					continue outer;
				}
			}
			// p[i]とp[i+1]を入れ替える予定なので、それらが欲しい位置に居るかを確認する
			if (pLeftRight[i + 1 - left] != pHalfLeft[i - left]) {
				continue outer;
			}

			long pattern = ((long) dp(left, i) * dp(i + 1, right)) % MOD;
			pattern = (pattern * nCm[right - left - 1][i - left]) % MOD;
			dp[left][right] = (dp[left][right] + pattern) % MOD;
		}

		return (int) dp[left][right];
	}
}