Codeforces Round #302 Div2 E: Remembering Strings

問題

codeforces.com

解法

codeforces.com

strings[i][j]に注目した時に、2つの操作を考える。

  • strings[i][j]だけを変える。この時はcost[i][j]がかかり、少なくともstrings[i]が覚えやすい文字列となる。
  • 全てのkについてstrings[i][j]と同じstrings[k][j]を変える。この時変える文字の数がp個だとすると、p-1個だけ変えれば良い。そのようなp-1個の組み合わせの中で最も小さいコストがかかり、p個のstrings[k]が覚えやすい文字列となる。

これを繰り返していく。どれが覚えやすい文字列となったかどうかはbitで管理すれば良い。覚えやすい文字列の数は減ることはないので、bit間の遷移は常に大きい方へ遷移する。よってbitの小さい方から順番に処理していけば良く、計算量は O(m2^{n})となる。

コード

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

public class Main {
	private final int MAX_COST = 1000000000;

	public void solve() {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		char[][] strings = new char[N][];
		for (int i = 0; i < N; i++) {
			strings[i] = sc.next().toCharArray();
		}
		int[][] cost = new int[N][M];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				cost[i][j] = sc.nextInt();
			}
		}
		sc.close();

		int[][] othersCost = new int[M][(1 << N)];// 自分以外の自分と同じ文字を変化させた場合の最小のコスト
		for (int i = 0; i < M; i++) {
			Arrays.fill(othersCost[i], MAX_COST);
		}
		int[][] otherChangeBit = new int[N][M];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				int changeCost = 0;
				int changeBit = (1 << i);
				for (int k = 0; k < N; k++) {
					if (i != k && strings[i][j] == strings[k][j]) {
						changeCost += cost[k][j];
						changeBit |= (1 << k);
					}
				}
				otherChangeBit[i][j] = changeBit;
				othersCost[j][changeBit] = Math.min(othersCost[j][changeBit], changeCost);
			}
		}

		int[][] oneChangeCost = new int[N][M];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				for (int k = 0; k < N; k++) {
					if (i != k && strings[i][j] == strings[k][j]) {
						oneChangeCost[i][j] += cost[i][j];
						break;
					}
				}
			}
		}

		// minCost[bit]:= bitとなるための最小のコスト
		int[] minCost = new int[(1 << N)];
		Arrays.fill(minCost, MAX_COST);
		minCost[0] = 0;

		for (int bit = 0; bit < (1 << N) - 1; bit++) {
			for (int m = 0; m < M; m++) {
				int i = 0;
				while ((bit & (1 << i)) != 0) {
					i++;
				}

				int oneBit = bit | (1 << i);
				minCost[oneBit] = Math.min(minCost[oneBit], minCost[bit] + oneChangeCost[i][m]);

				int othersBit = bit | otherChangeBit[i][m];
				minCost[othersBit] = Math.min(minCost[othersBit], minCost[bit] + othersCost[m][otherChangeBit[i][m]]);

			}
		}
		System.out.println(minCost[(1 << N) - 1]);

	}

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

}