NoiminのNoise

競技プログラミング (多め) とWeb (たまに) ,自然言語処理 (ブログではまだ)。数式の書き方を一気に KaTeX に変えようとして記事を全削除してインポートし直すなどしたので,過去にブックマークされた記事は URL が変わってしまっている可能性があります…….

Educational Codeforces Round 74 E. Keyboard Purchase

問題: https://codeforces.com/contest/1238/problem/E

問題概要

小文字のアルファベットのうち最初の m 文字のみ (例えば$m = 3$ なら a と b と c のみ) からなり$\left| s \right| \leq 10^5$ を満たす文字列 s が与えられる.

ここで,小文字のアルファベットのうち最初の m 文字の順列 t を作る.

任意の $i \lt \left| s \right|$ について,$s_{i}$ と $s_{i+1}$ が t 上で d 文字ぶん離れているとき,コストが d かかるとする.

s 全体での合計コストが最小になるように t を作るときの, s 全体での合計コストを求めよ.

解法概要

s において,文字 iと 文字 j が隣り合っている回数を $\mathit{cnt}_{i, j}$ と置く.

t を完成させてから全体のコストの合計を求める式は,$|t| = \mathit{m}$ であることから

$$\sum_{i=0}^{m-2} \sum_{j=i+1}^{\mathit{m}-1} \mathit{cnt}_{i, j} (j-i)$$

これを,全体のコストの合計に対する $t_i$ の寄与に着目して変形すると

$$\sum_{i=0}^{\mathit{m}-1} i (\sum_{j=0}^{i-1} \mathit{cnt}_{i, j} - \sum_{j=i+1}^{\mathit{m}-1} \mathit{cnt}_{i, j})$$

変形後のコスト計算式を用いれば, $i$ 文字目を決めたときのその文字の寄与は, $\mathit{cnt}_{i, j}$ を事前計算しておけば $O(m)$ で求められる.したがって,1文字目から順に決めていく bitDP で最小コストを求めることができる.

ソースコード

#include <iostream>
#include <vector>
#include <string>

using namespace std;

using ll =  long long;

constexpr ll INF = 1LL<<60;

/*
 * こちらのページの,ビットを数えるアルゴリズムのバージョン5をお借りしました
 * http://www.nminoru.jp/~nminoru/programming/bitcount.html
 */
inline int count_bit(unsigned  int n) {
    n = (n &  0x55555555) + (n >>  1  &  0x55555555);
    n = (n &  0x33333333) + (n >>  2  &  0x33333333);
    n = (n &  0x0f0f0f0f) + (n >>  4  &  0x0f0f0f0f);
    n = (n &  0x00ff00ff) + (n >>  8  &  0x00ff00ff);
    return (n &  0x0000ffff) + (n >>  16  &  0x0000ffff);
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    string s;
    cin >> s;
    vector<vector<ll>> a(m, vector<ll>(m, 0));
    for(int i=0;i<n-1;++i) {
        ++a[s[i]-'a'][s[i+1]-'a'];
        ++a[s[i+1]-'a'][s[i]-'a'];
    }

    vector<ll> dp(1<<m, INF);
    dp[0] = 0;
    for(unsigned int i=0;i<(1<<m);++i) {
        if(dp[i] == INF) continue;
        // 立っているビットの数
        int set_bit_cnt = count_bit(i);
        // これだと TLE でした……こっちの方が速いと思っていたのに
        // int set_bit_cnt = __builtin_popcount(i);

        for(int j=0;j<m;++j) {
            if(i & (1<<j)) continue;
            // 集合 i に文字 j を追加する
            ll new_cost = dp[i];
            for(int k=0;k<m;++k) {
                if(j == k) continue;
                if(i & (1<<k)) new_cost += a[k][j] * set_bit_cnt;
                else new_cost -= a[k][j] * set_bit_cnt;
            }
            dp[i|(1<<j)] = min(dp[i|(1<<j)], new_cost);
        }
    }

    cout << dp[(1<<m) - 1] << endl;
}

所感

C の読解で破滅していたので E は全く読んでなかった.

制約的に,$O(n^2 2^m)$ (で合ってますか?) が通るとは思わなかった.まあこれがわかっても解けなかったんだけど…….