気持ち良く詰められた

問題概要

$H \times W$ のオブジェに対し

いずれかの列を選び、その列を一段沈める (このとき最下段ブロックは消える)

という操作を $H \times W$ 回繰り返してオブジェを完全に消し去りたい。1 回の操作に要するコストは、そのブロックがその時点で左右に隣接している「マス目の色」が等しい箇所の個数である。

オブジェを消し去るのに必要な最小コストを求めよ。

制約

$1 \le H \le 300$
$2 \le W \le 300$

考えたこと

全探索では間に合わない。きっと何かしらの考察に基づいて、いい感じの順序を見出せるはず。たとえば「列を選んだら、一旦それを全消ししてよい」とかそういう考察が生えないかなと。。。でもそれは余裕で反例がある。

さて、王道に戻って、こういう問題はとりあえず $W = 2$ の場合について考えて、それから一般の場合を考察するとよいことが多いと思う。そこで $W = 2$ の考察を...と思った瞬間、そもそもこの問題は

それぞれの隣接列について独立に解いて合計すればよい

ということがわかった。というのも、たとえば列 (a, b, c) があって、列 (a, b) についての最適順序と、列 (b, c) についての最適順序がわかっていたら、これらを上手く入れ子状に織り混ぜることで、双方の最適順序を達成できるからだ。

W = 2 に帰着

というわけで、問題は $W = 2$ の場合に帰着された。そうはいっても、この時点ですでに $O(W)$ の計算量がかかることになるから、せいぜい $O(H^{2})$ で解かなければならない。そのことを念頭において考察を進める。まず 2 つの文字列を $S, T$ とする。

とりあえずこんな DP を組みたくなる

dp[ i ][ j ] := S が長さ i だけ残っていて、T が長さ j だけ残っている状態から出発して、最後まで埋めきるまでの最小コスト

こうしておくと、自然に次のような遷移が作れる

chmin(dp[ i ][ j ], dp[ i - 1 ][ j ] + cost[ i ][ j ])
chmin(dp[ i ][ j ], dp[ i ][ j - 1 ] + cost[ i ][ j ])

ここで cost[ i ][ j ] とは、S の長さ i の分と、T の長さ j の分とで、同じ要素が隣接している箇所の個数である。これは前処理で、累積和の要領であらかじめ求めてしまう。

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL<<60;

vector<vector<int>> calcsame(string S, string T) {
    int N = S.size();
    vector<vector<int>> res(N+1, vector<int>(N+1, 0));
    for (int i = 0; i <= N; ++i) {
        res[i][0] = 0;
        for (int j = 0; i + j < N; ++j) {
            if (S[i+j] == T[j]) res[i+j+1][j+1] = res[i+j][j]+1;
            else res[i+j+1][j+1] = res[i+j][j];
        }
        res[0][i] = 0;
        for (int j = 0; i + j < N; ++j) {
            if (S[j] == T[i+j]) res[j+1][i+j+1] = res[j][i+j]+1;
            else res[j+1][i+j+1] = res[j][i+j];
        }
    }
    return res;
}

long long calccost(string S, string T) {
    int N = S.size();
    const auto& cost = calcsame(S, T);

    //COUT(S); COUT(T); COUT(cost);
    
    vector<vector<long long>> dp(N+1, vector<long long>(N+1, INF));
    dp[0][0] = 0;
    for (int l = 0; l <= N; ++l) {
        for (int r = 0; r <= N; ++r) {
            if (l) {
                chmin(dp[l][r], dp[l-1][r] + cost[l][r]);
            }
            if (r) {
                chmin(dp[l][r], dp[l][r-1] + cost[l][r]);
            }
        }
    }
    return dp[N][N];
}

int main() {
    int H, W;
    cin >> H >> W;
    vector<string> fi(W, string(H, 'U'));
    for (int i = 0; i < H; ++i) for (int j = 0; j < W; ++j) cin >> fi[j][i];
    long long res = 0;
    for (int i = 0; i + 1 < fi.size(); ++i) {
        res += calccost(fi[i], fi[i+1]);
    }
    cout << res << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

CODE FESTIVAL 2016 qual C D - Friction (黄色, 800 点)

問題概要

制約

考えたこと

W = 2 に帰着