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