SRM 618 Div2 Medium LongWordsDiv2

問題

SRM 618 - TopCoder Wiki

次の性質を満たす文字列が好き. 与えられた文字列が好きかどうかを判定する問題.

  • 全て大文字
  • 同じ文字が連続しない
  • 同じサブシーケンスが出現しない,xyxyとならない.

解答

入力長が100なのでサブシーケンスとなりえるペアを全て考えても十分時間に間に合う. 全探索.

公式の解法はもっと単純でエレガント.面白い.

class LongWordsDiv2
{
public:
  string find(string word)
    {
      int n = word.size();
      int i, j, k, l;
      for (i = 1; i < n; i++) {
        if (word[i] == word[i-1]) return "Dislikes";
      }
      for (i = 0; i < n; i++){
        for (j = i+1; j < n; j++){
          for (k = j + 1; k < n; k++){
            for (l = k + 1; l < n; l++){
              if (word[i] == word[k] && word[j] == word[l]) return "Dislikes";
            }
          }
        }
      }
      return "Likes";
    }
};