AtCoder Beginner Contest (ABC) 201 PythonでC問題解いてみた
前回解いたやつ
こんにちは。メリーです。
最近お腹の調子がやばめです。
ご飯を食べた後に寝っ転がると、胃もたれが半端ないです。
だいぶ気持ち悪い・・・
前までは食後に寝っ転がってもなんともなかったのに・・・・
というわけで元気いっぱいでは無いけどAtCoder Beginner Contest (ABC) 201 C問題解いていきます。
言語はPython、提出はPyPyです。
目次
C問題 方針編
問題文
暗証番号忘れちゃったどうしよう問題。
0〜9までの各番号について、「確実に含まれていた」、「覚えていた」、「確実に含まれてない」の3パターンが用意されている。
ありえる暗証番号のパターンは何個かという問題。
また、記憶がだいぶ曖昧なため、彼の言葉を鵜呑みにすると、暗証番号が存在しないこともある。
あるあるですね。
暗証番号を再設定できれば一番速いのでしょうが、だめならありえる番号を全部試さなければならないという面倒くさい設定。
というわけで、ありえる可能性を全探索するのが手っ取り早いですね。
一応、他の方針としては、順列の問題として考えて、「確実に含まれていた」の数で場合分けしていく方法もあり。
順列の総数の計算方法があやふやだし、パターンの数え漏れが怖かったので、 今回は全探索でやりました。
暗証番号の全パターンにおいて、条件に合致するか否かをチェックしていきました。
ループ回数も104なので問題ないですね。
というわけで、方針は
1. 暗証番号「0000」から「9999」まで全探索。
2. 条件のチェックを行う。
3. 条件に合致していればカウントを+1
4. また、「o」の数が5つ以上であれば、ありえる可能性が存在しない。
5. 最後に総数を出力。
という感じでやってきました。
C問題 実装編
実装したコードがこちら。
s = input()
maru = []
batu = []
flg = 1
for i in range(10):
if s[i] == 'o':
maru.append(i)
elif s[i] == 'x':
batu.append(i)
if len(maru) > 4:
flg = 0
ans = 0
for i in range(10):
for j in range(10):
for k in range(10):
for l in range(10):
num = str(i) + str(j) + str(k) + str(l)
num2 = [i,j,k,l]
# oが全部含まれていて、xが含まれていないかの確認
if set(maru) <= set(num2) and set(num2).isdisjoint(set(batu)):
ans += 1
if flg:
print(ans)
else:
print(0)
ここからはコードの解説を。
maru、batuでそれぞれマルバツの付いた番号の管理をしてます。
のちのちの条件チェックのときに役に立ちます。
flgで管理しているのは、丸が５つ以上ある場合の暗証番号が存在しないパターンか否かです。
for i in range(10):
if s[i] == 'o':
maru.append(i)
elif s[i] == 'x':
batu.append(i)
によってmaru、batuのリストに数字を格納していきます。
丸とバツがわかれば「?」は問題にはなりません。「?」は含まれていようがいまいがどちらでも良いので。
if len(maru) > 4:
flg = 0
で、丸の数が５つ以上のときは暗証番号が存在し得ないので、フラグを折っておきます。
for i in range(10):
for j in range(10):
for k in range(10):
for l in range(10):
num = str(i) + str(j) + str(k) + str(l)
num2 = [i,j,k,l]
# oが全部含まれていて、xが含まれていないかの確認
if set(maru) <= set(num2) and set(num2).isdisjoint(set(batu)):
ans += 1
計算量問題ないのか怖くなる四重ループを回して暗証番号を「000」から「9999」まで全探索します。
計算量は104なので間に合います。
※atcoderでは108くらいまでなら間に合う。
なお、公式解説では、leading zero云々の話があります。
それをやればループが四重ではなくrange(10000)までのループ1つで済むのでしょうが、実装の方法とかわからなかったので、コードが簡単で読みやすい四重ループでやりました。
if文でチェックしていることは以下の２つを同時に満たすか否かです。
1. 作った暗証番号(num)に丸が付いた数字が全て含まれている。
2. 作った暗証番号(num)にバツが付いた数字が1個も含まれていない。
これら2つの条件は共に集合で確認できます。
べ、別に、inをたくさんの要素に行う良い方法が分からなかったから「Python in」でググったわけじゃないんだからねっ！！！
まず、条件1はこのコードで確認してます。
set(maru) <= set(num2)
ここで、setの大小比較について。
set(a) <= set(b)では、集合aが集合bの部分集合である場合にTrueを返す。
具体的には
s1 = [0,1,2] s2 = [1,2] s3 = [2,3] s4 = [5,6]
このような配列が用意されているとする。
この場合に、
set(s2) <= set(s1)はTrueを返す。
s2の要素全てがs1に含まれているからだ。
また、set(s3) <= set(s1)はFalseを返す。
s3の要素の3がs1に含まれていないからだ。
よって、
set(maru) <= set(num2)
では、maruの要素全てがnum2に含まれている場合にTrueを返す。
次に、２つ目の条件である暗証番号(num)にバツが付いた数字が1つも含まれていない、についてはこちらのコードで確認してある。
set(num2).isdisjoint(set(batu))
ここで、.isdisjointについて確認しておく。
指定した2つの集合において、共通する要素が1つも無い場合にTrueを返す。
先程の例において、
set(s1).isdisjoint(set(s4))はTrueを返す。
共通する要素が1つも存在しないからである。
よって、これらを組み合わせることで、2つの条件を同時にクリアした場合にのみansが増えるのである。
if flg:
print(ans)
else:
print(0)
最後にflgで場合分けして出力して終了である。
flg = 1の時、すなわち丸が4つ以下の時は通常どおりにansを出力して終了である。
それ以外の時には答えが存在し得ないので、0を出力して終了である。
正直、丸が５つ以上ある場合は四重ループ中のif文で全てハネられるので普通にansを出力するだけで問題ないと思うのだが・・・。
まあ、一応念のため。
という感じで終了です。
また明日もがんばります。
それでは
