KEYENCE String

• KEYENCE String

コンテスト中の考察

• 「一度だけ取り除く」を読めてなくて、ただの部分文字列判定を提出してWA
• 全探索で「一部分だけ切り取る」をやりたかったけど方法が思いつかなかった。なので他の方法を考えた
• 次は、不要な部分を取り出した回数をカウントする方針をやった。ただ、これも失敗
• 次は、最初のkから最後のeまでの範囲を見つけて探索する方法をとった。ただ、これも失敗。
• 先ほど間違えたのは、最初のkから始めるのが最善とは限らないからだと考えた。なので、全てのk始まりを考えるコードを書いた。けどこれもバグった
• 次は、パターンに分けて考えることにした。KEYENCE Stringにできるのは、「〇〇keyence」「k...〇〇...e」「keyence〇〇」「keyence」の4パターンである。この方針で通った。
• 合計7WA。これはひどい

コンテスト中のコード

• これはひどい

# include <bits/stdc++.h>
using namespace std;

# define int long long

string s;
string t = "keyence";

// keyence
void check1() {
  if (s == "keyence") {
    puts("YES");
    exit(0);
  }
}

// ...keyence
void check2() {
  int first = 0;
  for (int i = s.size() - 1; i >= 0; i--) {
    if (s[i] == 'k') {
      first = i;
      break;
    }
  }

  if (s.substr(first, 7) == t)  {
    puts("YES");
    exit(0);
  }
}

// keyence...
void check3() {
  if (s.substr(0, 7) == "keyence") {
    puts("YES");
    exit(0);
  }
}

// ke...ce
void check4() {
  string sr = s;
  reverse(sr.begin(), sr.end());
  string tr = t;
  reverse(tr.begin(), tr.end());

  if (s.substr(0, 1) == "k" && sr.substr(0, 6) == "ecneye") {
    puts("YES");
    exit(0);
    return;
  }
  if (s.substr(0, 2) == "ke" && sr.substr(0, 5) == "ecney") {
    puts("YES");
    exit(0);
    return;
  }
  if (s.substr(0, 3) == "key" && sr.substr(0, 4) == "ecne") {
    puts("YES");
    exit(0);
    return;
  }
  if (s.substr(0, 4) == "keye" && sr.substr(0, 3) == "ecn") {
    puts("YES");
    exit(0);
    return;
  }
  if (s.substr(0, 5) == "keyen" && sr.substr(0, 2) == "ec") {
    puts("YES");
    exit(0);
    return;
  }
  if (s.substr(0, 6) == "keyenc" && sr.substr(0, 1) == "e") {
    puts("YES");
    exit(0);
    return;
  }
}

signed main() {
  cin >> s;

  check1();
  check2();
  check3();
  check4();

  puts("NO");

  return 0;
}

理想の考察

• 取り除く部分を全探索すればいい。
• 取り除く部分はひとかたまりなので、２重ループで開始と終了を定めればよい。

コード

# include <bits/stdc++.h>
using namespace std;

# define int long long

signed main() {
  string s;
  cin >> s;

  int n = s.size();
  for (int begin = 0; begin < n; begin++) {
    for (int end = 0; end <= n; end++) {
      string t = "";
      // [begin, end)の区間を切り取る
      for (int k = 0; k < n; k++) {
        if (begin <= k && k < end) {
          continue;
        } else {
          t.push_back(s[k]);
        }
      }

      if (t == "keyence") {
        puts("YES");
        return 0;
      }
    }
  }

  puts("NO");

  return 0;
}

正規表現を使って実装する

コード

# include <bits/stdc++.h>
using namespace std;

int main() {
  string S;
  cin >> S;
  vector<regex> Re(8);
  Re[0] = (".*keyence");
  Re[1] = ("k.*eyence");
  Re[2] = ("ke.*yence");
  Re[3] = ("key.*ence");
  Re[4] = ("keye.*nce");
  Re[5] = ("keyen.*ce");
  Re[6] = ("keyenc.*e");
  Re[7] = ("keyence.*");
  bool ans = false;
  for(auto r : Re) ans |= regex_match(S, r);
  cout << (ans ? "YES" : "NO") << endl;

  return 0;
}

• main関数の返り値signedにするとWAになるんだけどなんでだろう。このコード。
• WAの原因はA問題に提出していたことでした。おしまい
• 正規表現便利すぐる

メモ

• だんだん難しく考える方に行ってしまった。
• もっとシンプルに考えるべきだった。どうせ難しいことは考えられないので