SRM 648 Div. 1 Easy: AB (動的計画法)

問題

TopCoder Statistics - Problem Statement

evimaさん

解法

動的計画法を使う。dp[i][j][p]に「i文字目まででAをj文字使った時にペアpに到達可能かどうか」を記録しておく。

if (!dp[i][j][p]) {
	dp[i + 1][j + 1][p] = true;// i+1文字目をAにする
	dp[i + 1][j][p + j] = true;// i+1文字目をBにする
}

幅優先探索を用いるとパターンが多すぎて落ちる（誤答コードを後述）。

コード

public class AB {

	public String createString(int N, int K) {
		// dp[i][j][p]:= i文字目まででAをj文字使った時のペアpに到達可能かどうか
		boolean[][][] dp = new boolean[N + 1][N + 1][2001];
		dp[0][0][0] = true;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				for (int p = 0; p <= K; p++) {
					if (!dp[i][j][p]) {
						continue;
					}
					dp[i + 1][j + 1][p] = true;// Aを増やす
					dp[i + 1][j][p + j] = true;// Bを増やす
				}
			}
		}

		int A = -1;
		for (int a = 0; a <= N; a++) {
			System.out.println(a);
			if (dp[N][a][K]) {
				A = a;
				break;
			}
		}
		if (A == -1) {
			return "";
		}

		String ans = "";
		while (N > 0) {
			if (A > 0 && dp[N - 1][A - 1][K]) {
				N--;
				A--;
				ans = "A" + ans;
			} else if (K - A >= 0 && dp[N - 1][A][K - A]) {
				N--;
				K -= A;
				ans = "B" + ans;
			}
		}
		return ans;

	}

	class Seq {
		String seq;
		int numA, pair;

		public Seq(String s, int a, int p) {
			this.seq = s;
			this.numA = a;
			this.pair = p;
		}
	}

}

誤答コード（幅優先探索）

import java.util.ArrayDeque;
import java.util.Deque;

public class AB {

	public String createString(int N, int K) {
		Deque<Seq> deque = new ArrayDeque<>();
		deque.addLast(new Seq("A", 1, 0));
		deque.addLast(new Seq("B", 0, 0));
		while (!deque.isEmpty()) {
			Seq seq = deque.pollFirst();
			if (seq.seq.length() == N) {
				break;
			}

			String aString = seq.seq + "A";
			if (aString.length() == N && seq.pair == K) {
				return aString;
			} else {
				deque.add(new Seq(aString, seq.numA + 1, seq.pair));
			}

			String bString = seq.seq + "B";
			if (bString.length() == N && seq.pair + seq.numA == K) {
				return bString;
			} else {
				deque.add(new Seq(bString, seq.numA, seq.pair + seq.numA));
			}
		}

		return "";
	}

	class Seq {
		String seq;
		int numA, pair;

		public Seq(String s, int a, int p) {
			this.seq = s;
			this.numA = a;
			this.pair = p;
		}
	}

}