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;
}