CODE FESTIVAL 2017: A - AKIBA

問題

A - AKIBA

賢くない解説

足りないAの数を数えて、Aがあるべき場所にあるかどうかで入力文字列と"AKIHABARA"とで比較していく。

void No() {
  cout << "NO\n";
  exit(0);
}

int main() {
  string t = "AKIHABARA";
  vector<int> posA; rep(i, t.size()) if (t[i] == 'A') posA.push_back(i);

  string s; cin >> s;
  if (s.size() > t.size()) No();

  int needA = posA.size() - accumulate(s.begin(), s.end(), 0, [](int a, char x) {
    return x == 'A' ? a + 1 : a;
  });
  if (s.size() + needA != t.size()) No();

  int posAIdx = 0;
  int spos = 0;
  rep(i, t.size()) {
    if (t[i] != s[spos] && posA[posAIdx] == i) {
      // s[spos] == null もある
      needA--;
    } else if (t[i] != s[spos]) {
      No();
    } else {
      spos++;
    }
    if (t[i] == 'A') posAIdx++;
  }
  cout << "YES\n";
}

公式の賢い解説

"AKIHABARA"から'A'を取り除いた文字列を全列挙し、入力の文字列がその中に含まれるか判定する。

set<string> st;
const string t = "AKIHABARA";
void dfs(string const& currstr, int curr) {
  if (t.size() == curr) {
    st.insert(currstr);
    return;
  }
  if (t[curr] == 'A') dfs(currstr, curr + 1);
  dfs(currstr + t[curr], curr + 1);
}

int main() {
  dfs("", 0);
  string s; cin >> s;
  cout << (st.count(s) ? "YES\n" : "NO\n");
}