Codeforces Round #135 (Div. 2) C : Color Stripe
問題概要
AからK文字のアルファベットを使用した長さN(<5e5)の文字列が与えられる。文字を書き換えることで隣り合う文字が異なるようにしたい。最小何文字書き換える必要があるか復元付きで求める問題。
解法
多分貪欲でも行けるはず。何だけどコンテスト中はDPに走った。dp[i][j]={i-1文字目がjであるときのそれまでの最適値}とすればよい。なぜか愚直なDPの計算量O(N*K)だと勘違いして、書いてる途中でO(N*K^2)だと気づいて焦った。多分ちょっと工夫したらO(N*K)で行けるんじゃないかとは思ったけど、どうせ間に合うだろうと信じてそのまま書いたが問題なく通った(カスタムテストで確認はしていた)。
acceptされたコード
#include <cstdio> #include <algorithm> using namespace std; template<typename numType> inline bool updateMin(numType& old, const numType& test) { if (old > test) { old = test; return true; } return false; } const int MAX_N = int(5e5); const int MAX_K = 26; const int INF = (int)(1.05e9); int N, K; char buf[MAX_N + 1]; int opt[MAX_N + 1][MAX_K]; int prev[MAX_N + 1][MAX_K]; void init() { scanf("%d%d", &N, &K); scanf(" %s ", buf); } void solve() { for (int i = 0; i <= N; ++i) { fill(opt[i], opt[i] + MAX_K, INF); } opt[0][0] = 0; for (int i = 0; i < N; ++i) { for (int j = 0; j < K; ++j) { for (int k = 0; k < K; ++k) if (i == 0 || j != k) { int add = (buf[i] == char('A' + k) ? 0 : 1); if (updateMin(opt[i+1][k], opt[i][j] + add)) { prev[i+1][k] = j; } } } } int start = -1, mini = INF; for (int i = 0; i < K; ++i) { if (updateMin(mini, opt[N][i])) { start = i; } } for (int i = N; i >= 1; --i) { buf[i-1] = char('A' + start); start = prev[i][start]; } printf("%d\n", mini); puts(buf); } int main() { init(); solve(); return 0; }