NoiminのNoise

競技プログラミング (多め) とWeb (たまに) ,自然言語処理 (ブログではまだ)。

Educational Codeforces Round 74 E. Keyboard Purchase

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

問題概要

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

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

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

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

解法概要

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

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

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

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

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

変形後のコスト計算式を用いれば, {\displaystyle i } 文字目を決めたときのその文字の寄与は, {\displaystyle \mathit{cnt}_{i, j} } を事前計算しておけば {\displaystyle 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 は全く読んでなかった.

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