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

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

Educational Codeforces Round 74 E. Keyboard Purchase (R2200)

こういうのを素早く処理できるようになりたい

問題へのリンク

問題概要

長さ  N M 種類の文字からなる文字列  S が与えられる。いま、 M 種類の文字の順列  p として考えられる  M! 通りの並びのうち最適なものを求めたい。

順列のスコアは、 S 上のすべての連続する 2 文字について、それらの文字の  p における index の差分を合計した値で決まる。

このスコアの最小値を求めよ。

制約

  •  1 \le N \le 10^{5}
  •  1 \le M \le 20

考えたこと

実質的に  M \times M の対称行列  A が与えられて、順列  p_{1}, \dots, p_{M} のうち、

  •  \sum_{i \lt j} A_{i, j} \times |p_{i} - p_{j}|

の最小値を求める問題ということになる。 M \le 20 という制約がいかにも bit DP っぽい。というわけで

  • dp[ S ] := 順列のうち S の部分集合の並びを最初に決めたときの、その部分で発生するスコア

としたくなる。しかしこのままだと上手く遷移できない。S に新たに要素 a を追加するとき、S の内部の並びがわからないと、それらと a との距離がわからないからだ。そこで少しだけ DP の考え方を変えて、


  • S にすでに入っている要素 a について、他の各要素 v に対して、v が S に追加されない限り S の更新において  A_{a, v} を加算し続ける。

という風にする。計算量は  O(M^{2}2^{M} + N) に。

#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;
int K;
string S;

long long solve() {
    vector<vector<long long> > num(K, vector<long long>(K, 0));
    for (int i = 0; i + 1 < S.size(); ++i) {
        if (S[i] == S[i+1]) continue;
        int a = S[i] - 'a';
        int b = S[i+1] - 'a';
        num[a][b]++;
        num[b][a]++;
    }

    vector<long long> dp((1<<K) + 10, INF);
    dp[0] = 0;
    for (int bit = 0; bit < (1<<K); ++bit) {
        int bit2 = (1<<K)-1 - bit;
        long long cost = 0;
        for (int i = 0; i < K; ++i) {
            if (!(bit & (1<<i))) continue;
            for (int j = 0; j < K; ++j) {
                if (bit & (1<<j)) continue;
                cost += num[i][j];
            }
        }
        for (int v = 0; v < K; ++v) {
            if (bit & (1<<v)) continue;
            chmin(dp[bit | (1<<v)], dp[bit] + cost);
        }
    }
    return dp[(1<<K)-1];
}

int main() {
    int SN;
    while (cin >> SN >> K >> S) {
        cout << solve() << endl;
    }
}