kojingharangの日記

SRM 600 Div1 600 PalindromeMatrix

17:03 |

• W x H のグリッドに 0 か 1 が書いてある。回文である行が R 個以上、列が C 個以上にしたい。最低何箇所書き換える必要があるか？
• 2≦W,H≦14
• 0≦R≦H, 0≦C≦W

• 回文にする行/列を固定(2^28通り)→UnionFindで同じにするセルを結ぶ→各グループに含まれる数字のうち少ない方の個数だけ書き換える必要あり
• しか思いつかない。
• おわり

• Editorial を見る
• 回文にする列(14C7=3432通り)を決めて、あとはDPらしい。

int dp[16][16]; // dp[Y][r] ... y<Y or H-1-Y<y までの範囲に関して r 個以上の行と C 個以上の列が回文であるようにした時の最小コスト

• として、更新するときは今回新たに塗るところ(y=Y, y=H-1-Y)の 2*W マスをどうするか考える。
• 塗り方は4通り (y=Y の行を回文にする/しない, y=H-1-Y の行を回文にする/しない)
• 固定した列は回文にするとして、必要に応じて行を回文にするために同じにならないといけないマスを union find でくっつけていく
• みたいな。

• 最内ループの最大処理回数は 3432*7*14*4*2*14 = 37,669,632

• accepted in practice

#define f(x, y) ((x)+(y)*W)

const int inf = 1<<30;
int dp[16][16]; // dp[Y][r] ... y<Y or H-1-Y<y までの範囲に関して r 個以上の行と C 個以上の列が回文であるようにした時の最小コスト
int co[32][2]; // [CellID][value] ... CellID を代表とするグループのセルのうち value であるものの個数 (value in {0, 1})
class PalindromeMatrix {
	public:
	int minChange(vector <string> A, int R, int C) {
		int W=A[0].size(), H=A.size();
		VI wcc(W);
		REP(i, C) wcc[i]=1;
		sort(ALL(wcc));
		int ans = inf;
		do {
			REP(y, H/2+1) REP(r, R+1) dp[y][r]=inf;
			dp[0][0] = 0;
			REP(y, H/2) REP(r, R+1) {
				if(dp[y][r]==inf) continue;
				int Y[] = {y, H-1-y}; // upper/lower
				REP(pat, 4) {
					bool upper = pat&1, lower = pat&2; // is upper/lower row palindrome?
					int new_r = r+upper+lower;
					if(new_r<=R) {
						int add = 0;
						UnionFind uf(W*2); // x in [0, W), y in Y, index==y*W+x
						REP(x, W) if(wcc[x]) uf.Union(f(x, 0), f(x, 1)); // 選ばれた C 列は必ず回文にする
						if(upper) REP(x, W) uf.Union(f(x, 0), f(W-1-x, 0)); // 必要なら行を回文にする
						if(lower) REP(x, W) uf.Union(f(x, 1), f(W-1-x, 1));
						CLEAR(co, 0);
						REP(y, 2) REP(x, W) co[uf.root(f(x, y))][A[Y[y]][x]-'0']++;
						REP(y, 2) REP(x, W) if(uf.root(f(x, y))==f(x, y)) add += min(co[f(x, y)][0], co[f(x, y)][1]);
						dp[y+1][new_r] = min(dp[y+1][new_r], dp[y][r] + add);
					}
				}
			}
			ans = min(ans, dp[H/2][R]);
		} while(next_permutation(ALL(wcc)));
		return ans;
	}
};

ツイートする