CODE FESTIVAL 2016 qual C - D: Friction
問題
D: Friction - CODE FESTIVAL 2016 qual C | AtCoder
のブロックがある。各ブロックは赤、緑、青のいずれかである。1度の操作で、一番下の行あるブロックのうち1つを消すことができる。消すときにかかるコストは、消した列の各ブロックの横に隣り合うブロックのうち色が同じ物の数のぶんだけかかる。全てのブロックを消すためのコストを最小化せよ。部分点はの場合である。
解法
各列について消した数(or 高さ)を状態として持ってDPすることを考える。であれば、
となる。コストは別計算できないか考える。(0, 1)列目のペアと、(1, 2)列目のペアとで別々に計算する。消した数(or 高さ)を状態に持ち、そのブロックの状態でかかるコストを計算する。
などとすればよい。あとは先程のDPの計算に組み込めばよい。ここまでで部分点が取れる。
ある列に対してかかるコストは隣接する列の状態のみに影響するので、列ごとに左から順に独立にコストを計算すれば十分であることが分かる。つまり、の状態のみ応えられるようにして、これを左から順に足し合わせれば良い。このときコスト計算はDPする必要がある。コスト計算のDPは単純で「高さa, bで一致したら高さを両方進める」というように書く(LCSのように片方だけ進めるという式は不要)。隣接している列のどちらかが高さ0であれば0なので、これを初期状態とする。これにより、2列の高さのズレが考慮される。これで満点が取れる。
// 部分点解法(抜粋) static int h1[303][303]; static int h2[303][303]; rep(a, H) rep(b, H) { // a[, b] := 0[, 1]列目を既に削った個数 rep(k, H - max(a, b)) { // k := 下から数えてk番目 h1[a][b] += (G[H-1-a-k][0] == G[H-1-b-k][1]); h2[a][b] += (G[H-1-a-k][1] == G[H-1-b-k][2]); } } static int dp[303][303][303]; rep(i, 303) rep(j, 303) rep(k, 303) dp[i][j][k] = inf; dp[0][0][0] = 0; rep(i, H + 1) rep(j, H + 1) rep(k, H + 1) { dp[i+1][j][k] = min(dp[i+1][j][k], dp[i][j][k] + h1[i][j]); dp[i][j+1][k] = min(dp[i][j+1][k], dp[i][j][k] + h1[i][j] + h2[j][k]); dp[i][j][k+1] = min(dp[i][j][k+1], dp[i][j][k] + h2[j][k]); }
// 満点解法 int main() { int H, W; cin >> H >> W; vector<string> G(H); rep(i, H) cin >> G[i]; ll ans = 0; rep(C, W - 1) { static int dp[303][303]; static int h[303][303]; rep(i, 303) rep(j, 303) h[i][j] = dp[i][j] = inf; rep(i, 303) h[0][i] = h[i][0] = 0; dp[0][0] = 0; rep(a, H) rep(b, H) { h[a+1][b+1] = min(h[a+1][b+1], h[a][b] + (G[a][C] == G[b][C+1])); } rep(i, H + 1) rep(j, H + 1) { dp[i+1][j] = min(dp[i+1][j], dp[i][j] + h[H - i][H - j]); dp[i][j+1] = min(dp[i][j+1], dp[i][j] + h[H - i][H - j]); } ans += dp[H][H]; ans %= MOD; } cout << ans << endl; return 0; }