SRM 551 250pt : ColorfulChocolates

問題概要

文字列Sが与えられる。隣接する文字を高々M回までswapできるとき、連続する同じ文字の長さの最大値を求める問題。

解法

最長なswap後の文字列を考えると、どれか一文字は動いていないと思ってよい。そうでないものも作れるが、固定した場合よりもよくはならないことが分かる。なので、固定する文字を全探索して、左側と右側に同じ文字列をk個つなげるのに必要なコストを求め、左右の和がMを越えないような最長の結合を調べればよい。

acceptされたコード

#include <string>
#include <vector>
#include <numeric>
#include <algorithm>
using namespace std;

const int INF = (int)(1.05e9);

const int MAX_L = 50;
int cost[2][MAX_L+1]; //(left or right, length)

struct ColorfulChocolates {

	int maximumSpread(string chocolates, int maxSwaps) {
		int ans = 1;
		const int n = chocolates.length();
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j <= MAX_L; ++j) {
				cost[0][j] = calcLeft(chocolates, 0, i, j, chocolates[i]);
			}
			for (int j = 0; j <= MAX_L; ++j) {
				cost[1][j] = calcRight(chocolates, i+1, n, j, chocolates[i]);
			}
			for (int j = 0; j <= MAX_L; ++j) {
				for (int k = 0; k <= MAX_L; ++k) {
					if (cost[0][j] + cost[1][k] <= maxSwaps) {
						ans = max( ans, 1 + j + k );
					}
				}
			}
		}
		return ans;
	}

	int calcLeft(const string& chocolates, int from, int to, int length, char ch) {
		if (length == 0) {
			return 0;
		}
		vector<int> cnts;
		int p = 0;
		for (int i = to - 1; i >= from; --i) {
			if (chocolates[i] == ch) {
				cnts.push_back(to - i - 1 - p);
				++p;
			}
		}
		if ((int)cnts.size() < length) {
			return INF;
		}
		sort(cnts.begin(), cnts.end());
		return accumulate(cnts.begin(), cnts.begin() + length, 0);
	}

	int calcRight(const string& chocolates, int from, int to, int length, char ch) {
		if (length == 0) {
			return 0;
		}
		vector<int> cnts;
		int p = 0;
		for (int i = from; i < to; ++i) {
			if (chocolates[i] == ch) {
				cnts.push_back(i - from - p);
				++p;
			}
		}
		if ((int)cnts.size() < length) {
			return INF;
		}
		sort(cnts.begin(), cnts.end());
		return accumulate(cnts.begin(), cnts.begin() + length, 0);
	}

};