AtCoder Beginner Contest 201 C - Secret Number
問題
高橋くんは、暗証番号を忘れてしまいました。暗証番号は0から9までの数字のみからなる4桁の文字列で、0から始まる場合もあります。
0から9までの各数字について、高橋くんは以下のように記憶しています。彼の記憶は長さ10の文字列によって表されます。
- がoのとき:数字iは暗証番号に確実に含まれていた。
- がxのとき:数字iは暗証番号に確実に含まれていなかった。
- が?のとき:数字iは暗証番号に確実に含まれているかわからない。
高橋くんが忘れてしまった暗証番号としてあり得るものは何通りありますか?
制約
- Sはo,x,?のみからなる長さ10の文字列
考えたこと
暗証番号は0000から9999までなので、条件に合うかすべて調べます。どの数字が何回登場したか数え、それと条件と比較します。
oに対する数字が一度も登場していない場合と、xに対する数字が登場していれば条件に合いません。
コード
#define _GIBCXX_DEBUG #include <bits/stdc++.h> using namespace std; #define rep(i, n) for (int i = 0; i < (n); ++i) #define all(v) v.begin(), v.end() using namespace std; using ll = long long; int main(void) { string S; cin >> S; int ans = 0; rep(i, 10) rep(j, 10) rep(k, 10) rep(l, 10) { vector<int> v(10, 0); v[i]++; v[j]++; v[k]++; v[l]++; bool ok = true; rep(m, v.size()) { if (v[m] > 0 && S[m] == 'x') ok = false; if (v[m] == 0 && S[m] == 'o') ok = false; } if (ok) ++ans; } cout << ans << endl; return 0; }
解説を読んで
何回登場したかは必要ない情報でした。暗証番号すべてを調べればよいことに気づくまで時間がかかってしまいました。