ACM-ICPC 模擬地区予選 2012 J: Ancient Scrolls [Licence: NYSL Version 0.9982

Main.java

import java.util.*;
import static java.lang.Math.*;

public class Main {
  private static final int n = 3; // future work n != 3

  public static void main(String... args) {
		final Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			final int l = sc.nextInt();
			final int d = sc.nextInt();
			if (l == 0 && d == 0)
				break;

			final char[][] strs = new char[n + 1][];
			for (int i = 0; i < n; i++)
				strs[i] = sc.next().toCharArray();
			strs[n] = new char[l];
			for (int i = 0; i < l; i++)
				strs[n][i] = 'A';
			System.out.println(new Main(d, l, strs).solve());
		}
	}

	private final int d, l;
	private final char[][] strs;

	private Main(int d, int l, char[][] strs) {
		this.d = d;
		this.l = l;
		this.strs = new char[l][n + 1];
		for (int i = 0; i < l; i++)
			for (int j = 0; j <= n; j++)
				this.strs[i][j] = strs[j][i];
	}

	private String solve() {
		final int[] type = new int[l];
		for (int i = 0; i < l; i++)
			for (int j = 0; j < n; j++)
				for (int k = 0; k < j; k++)
					type[i] |= strs[i][j] == strs[i][k] ? 1 << j | 1 << k : 0;
		final int[] cnt = new int[1 << n];
		for (int i = 0; i < l; i++)
			cnt[type[i]]++;
		final int[] dd = new int[n];
		Arrays.fill(dd, d);

		if (!check(cnt, dd))
			return "-1";

		final char[] ret = new char[l];
		for (int i = 0; i < l; i++) {
			cnt[type[i]]--;
			ret[i] = assign(cnt, dd, strs[i]);
		}
		return new String(ret);
	}

	private char assign(final int[] cnt, final int[] dd, final char[] cs) {
		char min = '~';
		for (int i = 0; i <= n; i++)
			if (cs[i] < min) {
				for (int j = 0; j < n; j++)
					if (cs[j] != cs[i])
						dd[j]--;
				if (check(cnt, dd))
					min = cs[i];
				for (int j = 0; j < n; j++)
					if (cs[j] != cs[i])
						dd[j]++;
			}
		if (min == '~')
			throw null;
		for (int i = 0; i < n; i++)
			if (cs[i] != min)
				dd[i]--;
		return min;
	}

	private boolean check(final int[] cnt, final int[] dd) {
		for (int i = 0; i < n; i++)
			if (dd[i] < 0)
				return false;
		final int[] greedy = new int[n];
		for (int i = 0; i < n; i++)
			greedy[i] = max(0, cnt[0] - dd[i] + cnt[(1 << n) - 1 ^ 1 << i]);
		{
			int sum = 0;
			for (int i = 0; i < n; i++)
				sum += greedy[i];
			if (sum <= cnt[0])
				return true;
		}
		{
			int nonzero = -1;
			for (int i = 0; i < n; i++)
				if (greedy[i] > 0)
					if (nonzero >= 0)
						return false;
					else
						nonzero = i;
			final int extrusion = greedy[nonzero] - cnt[0];
			int margin = cnt[(1 << n) - 1 ^ 1 << nonzero];
			for (int i = 0; i < n; i++)
				if (greedy[i] == 0)
					margin = min(margin, dd[i] - cnt[0] - cnt[(1 << n) - 1 ^ 1 << i]);
			return margin >= extrusion;
		}
	}
}