TopCoder SRM618: LongWordsDiv2

全探索しても間に合う。計算量は、\(O(|word|^4)\)

public class LongWordsDiv2 {
    public string find(string word) {
        int n = word.Length;
        for (int p1 = 0; p1 < n - 1; p1++) {
            if (word[p1] == word[p1 + 1])
                return "Dislikes";
        }

        if ((from p1 in E.Range(0, n)
             from p2 in E.Range(0, n)
             from p3 in E.Range(0, n)
             from p4 in E.Range(0, n)
             where p1 < p2 && p2 < p3 && p3 < p4 && word[p1] == word[p3] && word[p2] == word[p4]
             select 1).Any()) return "Dislikes";

        return "Likes";
    }
}

別の解法としては、xyxy のパターンは \(26^2\) 通りしかないため、これらのパターンが部分系列として含まれているかをチェックすればよい。この場合の計算量は \(26^2 * O(|word|)\) になる。

public class LongWordsDiv2 {
    public string find(string word) {
        int n = word.Length;
        if (word.Zip(word.Skip(1), (c1, c2) => c1 == c2 ? 1 : 0).Sum() > 0)
            return "Dislikes";

        for (var c1 = 'A'; c1 <= 'Z'; c1++) {
            for (var c2 = 'A'; c2 <= 'Z'; c2++) {
                int cur = 0;
                var cs = new[] { c1, c2 };
                foreach (var c in word) if (c == cs[cur % 2]) cur++;
                if (cur >= 4) return "Dislikes";
            }
        }

        return "Likes";
    }
}