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