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)$ (で合ってますか?) が通るとは思わなかった.まあこれがわかっても解けなかったんだけど…….