AtCoder / Python エラーコードの反例が見当たらない

Question

#問題

AtCoder ABC157 C問題より

#方針
1.各桁の「箱」をリスト型として辞書の値に空の状態から生成。
2.とりあえず入力から値をリストにappendする。
3.重複を剥ぎ取ってもなおリストに複数値が埋め込まれている場合、この時点で-1を出力
4.3でない場合、出来上がった辞書になお空リストが存在する場合、'0'を入れてあげることで最小値を与えるようにする。
5.'0'という一桁の文字列という例外を除いて、'007'などという文字列はstr(int())とすることで桁数が変わることから、ansがこの条件に合うものであれば-1を出力
6.それ以外の場合、int(ans)を出力

#コード

N, M = map(int, input().split())

num_dic = {}
for i in range(1, N + 1):
	num_dic[i] = []

for _ in range(M):
	s, c = map(int, input().split())
	num_dic[s].append(str(c))

if any(len(list(set(num_dic[i]))) >= 2 for i in range(1, N + 1)):

	print(-1)

else:

	ans = ''
	for i in range(1, N + 1):
		if len(num_dic[i]) == 0:
			num_dic[i].append('0')

		num_dic[i] = list(set(num_dic[i]))

		ans += num_dic[i][0]


	if len(str(int(ans))) != len(ans) and ans != '0':
		print(-1)

	else:
		print(int(ans))

#質問
本来であれば、Nの制約が非常に小さいことから全探索を行うところなのですが、先にNという数の各桁に何を埋め込むかという戦法を取りました。いくつかの情報を検索して集めたところ、このやり方はどうやら0の扱いなどで穴が空きやすいとのことでしたが、上記のエラーコードで言うとどういったところが抜け目になってしまっているのでしょうか。またあるとしたらどのような入力の反例がありますでしょうか。雑な質問とはなってしまいましたが、お力添え頂ける箇所がございましたら、ご教授のほどどうかよろしくお願い申し上げます。

Answer 1

2 0や3 0など、Nが2以上でMが0の時にWAとなる

Comments

[kay_ventris4]

なるほど、例えばN, M = 2, 0で出力を受けた時私のプログラムで出力されるのは-1ですが、本来であれば10が出力されるべきですものね。これからは制約を与えられた時は両端の極端な例をしっかりと検証するようにしたいと思います。そしてやはり実装のコストを考えると、この問題の場合全探索が良さそうな感じはしますね…

Answer 2

結局上のやり方はだいぶ厳しい（現在の私の実力にとっては）ので、全探索を試したところ、驚くほどあっさりできました：

N, M = map(int, input().split())

digit = [
    [str(_) for _ in range(0, 10)],
    [str(_) for _ in range(10, 100)],
    [str(_) for _ in range(100, 1000)]
]

obj = digit[N - 1]

for _ in range(M):
    s, c = map(int, input().split())
    obj = [el for el in obj if el[s - 1] == str(c)]

if len(obj) >= 1:
    print(min(obj))

else:
    print(-1)