SRM 551 div1 easy: ColorfulChocolates
問題
TopCoder Statistics - Problem Statement
n 文字の文字列が与えられる。maxSwap 回以内の隣り合った文字の交換を許すとき, 「同じ文字が連続して p 個並んでいる」という性質を満たす最長の部分文字列の長さを求めよ。
解法
真ん中の文字を決めます。で, 左右から何文字くっつけてくるかで場合分けです。
下のコードではさらに左からくっつけてくる文字でも場合分けしてますが, もっと賢く, 左から文字を持ってくるのと 右から文字を持ってくるのの距離を配列に入れてソートする, という解法のほうがオーダーもそんな変わらないし実装が超楽です。
hamko さんがその方法でやってて「なるほど天才」と思いました。
int cnt[55][26]; class ColorfulChocolates { public: int maximumSpread(string chocolates, int maxSwaps) { int n = chocolates.size(); memset(cnt, 0, sizeof(cnt)); for (int i = 0; i < n; i++) { for (int j = 0; j < 26; j++) { cnt[i+1][j] = cnt[i][j]; } cnt[i+1][chocolates[i]-'A']++; } int ans = 1; for (int i = 0; i < n; i++) { for (int l = 0; l <= cnt[i][chocolates[i]-'A']; l++) { int c = 0; int rest = maxSwaps; for (int j = i-1; j >= 0 && c < l; j--) { if (chocolates[j] == chocolates[i]) { rest -= (i-1-j-c); if (rest < 0) { break; } c++; } } if (c < l) continue; int tmp = 1+l; c = 0; for (int j = i+1; j < n; j++) { if (chocolates[j] == chocolates[i]) { rest -= j-i-c-1; if (rest >= 0) { tmp++; c++; } else { break; } } } ans = max(ans, tmp); } } return ans; } };