CODE FESTIVAL 2017: 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"); }