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

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

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

気持ち良く詰められた

問題へのリンク

問題概要

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

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

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

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

f:id:drken1215:20200128233800p:plain

制約

  •  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;
}