Codeforces Round #302 Div2 E: Remembering Strings
解法
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の小さい方から順番に処理していけば良く、計算量はとなる。
コード
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(); } }