ABC201 C 解答

C - Secret Number（439）

問題

C - Secret Number

問題文

高橋くんは、暗証番号を忘れてしまいました。暗証番号は 0 から 9 までの数字のみからなる 4 桁の文字列で、0 から始まる場合もあります。
0 から 9 までの各数字について、高橋くんは以下のように記憶しています。彼の記憶は長さ 10 の文字列 S0S1 … S9 によって表されます。
・Si が o のとき : 数字 i は暗証番号に確実に含まれていた。
・Si が x のとき : 数字 i は暗証番号に確実に含まれていなかった。
・Si が ? のとき : 数字 i が暗証番号に含まれているか分からない。
高橋くんが忘れてしまった暗証番号としてあり得るものは何通りありますか？

制約

S は o, x, ? のみからなる長さ 10 の文字列

考察

まずは、条件を整理します。３つありますね。

１）Si が o のとき : 数字 i は暗証番号に確実に含まれていた。
２）Si が x のとき : 数字 i は暗証番号に確実に含まれていなかった。
３）Si が ? のとき : 数字 i が暗証番号に含まれているか分からない。

書いてあるままといえばその通りなのですが、言い換えをしてみます。

１）

その数字は確実に含まれていたということは、もしもその暗証番号に１）に該当する数字が

「一つでも抜けている」

場合にその暗証番号は間違いということになります。

２）

その数字が確実に含まれていない、ですので暗証番号に２）に該当する数字が

「一つでも含まれている」

場合にその暗証番号は間違いということになります。

３）

その数字が含まれていたかわからない、ということはそういうことです。わからないんです。ですので、この条件は特に暗証番号を絞る手掛かりになりません。

条件は以上です。さて、次は暗証番号の取りうる範囲を考えてみます。暗証番号はどうやら４桁らしいです。ということで、その範囲は

0000~9999

までですね、先頭に 0 がくる処理が少し面倒ですが、for文を 0 から 9999まで回せば、すべての数字を試すことができます。この数字のうち上記の条件を満たすものを数え上げてあげましょう。それを出力すればACとなります。

考え方としては以上です。実装に関して少し説明をします。

数値を0~9999まで調べるのですが、このままだと判定がしにくいのでこちらをstringに変換します。そして、0~999までは4桁に満ちませんので、0を追加してあげます。このときに、正確には先頭に0を追加しなければいけないのですが、条件は「その数が含まれている、いない」ですので、あまり順番は関係ありません。ですので、0 を４桁になるまで末尾に追加すれば４桁の番号が作れます。

あとはソースコードにて補足します。

実装

 #include <bits/stdc++.h> #define  rep(i,n) for(int i=0;i<n;++i) #define  reps(i,s,n) for(int i=s;i<n;++i)
using namespace std;
using ll = long long;
using P = pair<ll, ll>;

int main()
{
	string s;
	cin >> s;
    //含まれていなければならない数（MUSTとするのが正確かも）
	vector<char> OK;
    //含まれていてはいけない数
	vector<char> NG;
	rep(i, 10)
	{
        //i +'0'とすることで文字型になる
		if (s[i] == 'o') OK.emplace_back(i+'0');
		else if (s[i] == 'x') NG.emplace_back(i+'0');
	}

	int ans = 0;
	for (int i = 0; i <= 9999; ++i)
	{
        //to_stringで文字列に変換
		string t = to_string(i);
        //4桁になるまで0を追加する
		while (t.size() < 4) t += '0';
		bool ok = true;
        //OKとなる数がすべて含まれているか確認
		for (auto o : OK)
		{
			bool tok = false;
			for (auto ti : t) if (ti == o) tok = true;
			if (!tok) ok = false;
		}
        //NGとなる数が含まれていないか確認
		for (auto n : NG)
		{
			for (auto ti : t) if (ti == n) ok = false;
		}
        //条件を満たすものを数える
		if (ok) ++ans;
	}
	cout << ans << endl;

	return 0;
}

あとがき

「含まれている」「含まれていない」を判定する問題でした。「含まれていない」の判定は簡単なのですが、「含まれている」の判定は少し面倒ですね。各数字に対して４桁を見て、その数が含まれているかを調べる必要があります。

for文にて判定してもいいのですが文字列には find というメソッドがあります。含まれていたらtrue、いなかったらfalseというようなシンプルなものではありませんが、「含まれていない」ものを判断するのは簡単にできそうですね。

pythonでしたら in という方法もあるのですが、C++だとどうするのが良いのでしょうかね。