C - Secret Number

問題内容

0000~9999までの4桁の暗証番号について，どの文字が使われていたかを10文字の文字列で与えられるので，ありえるパターンの数を答える問題
例えばo?xx?oxoxxでが与えられれば，左から順に 0,1,2..9 と見ていって，

o : 確実に1回以上使われる( 0,5,7 は 1~4 個)
? : 使われたかもしれない( 1,4 は 0~4 個)
x : 使われない( 2,3,6,8,9 は 0 個)

この条件でありえる暗証番号のパターン数は84通りなので，84を出力すればよいです。

本番で提出したコード

ABC201_C.rb

str = gets.chomp.split('')
o = 0
q = 0

10.times do |i|
    o += 1 if str[i] == 'o'
    q += 1 if str[i] == '?'
end

if o >= 5
    puts 0
elsif o == 4
    puts 24
elsif o == 3
    puts 24 * q + 36
elsif o == 2
    puts 12 * q * q + 24 * q + 14
elsif o == 1
    puts 4 * q * q * q + 6 * q * q + 4 * q + 1
else
    puts q * q * q * q
end

最初のtimes文のところまでで，oと?の個数を数えて,変数o,qに入れています。あとから見直すと，結構直したくなってくる...

配列にしてるのに変数名strなのは違和感
文字列のままcountで数えたほうがスマート

if文で，変数oの値によって，条件分岐させながら，計算しました。
(高校数学でこんなのやったなあと思い出しながら...)

o が 5 個以上

4桁の暗証番号なので，これはありえない！
$0$ 通り

o が 4 個

4個全てをパターンしかないので
$4! = 24$ 通り

o が 3 個

oの3種類のみで考えられるパターン

$4!$に対し，同じ数字が2個あるので$2$で割って，どの数字を2個使うかで3パターンあるので$3$をかけます。
$ \frac{4!}{2}×3 = 36 $ 通り

oの3種類に?から1個使うパターン

どこに?を使うかで$4$通り,oの並べ方で$3!$通り，さらに?の個数分だけ$q$通りあるので
$ 4 × 3! × q = 24q $ 通り

合計は

$ 24q + 36 $ 通り

o が 2 個

oの2種類を2個ずつ使うパターン

$4!$ に対し，同じ数字が2個ずつあるので $2×2$ で割ります。
$ \frac{4!}{2×2} = 6 $ 通り

oの2種類を1個,3個で使うパターン

どちらを1個にするかで $2$ 通りに，1個のほうがどこに来るかで $4$ をかけます。
$ 2 × 4 = 8 $ 通り

oの2種類を1個,2個で使い，?から1個使うパターン

どこに?を使うかで $4$ 通り,oの並べ方(どこに1個のほうがくるかで3通り，どっちを1個にするかで2通り)で $ 3 × 2 $ 通り，さらに?の個数分だけ$q$通りあるので
$ 4 × 3 × 2 × q = 24q $ 通り

oの2種類を1個ずつ使い，?から2個使うパターン

どこに?を使うかで $_4 C _2 = 6$ 通り,oの並べ方(どこに1個のほうがくるかで3通り，どっちを1個にするかで2通り)で $ 3 × 2 = 6 $ 通り，さらに?の個数分だけ $q^2$ 通りあるので
$ 6 × 6 × q^2 = 36q^2 $

合計は

$ 36q^2 + 24q + 14 $ 通り

o が 1 個

oを4回使うパターン

$1$ 通りしかないです。

oを3回,?を1回使うパターン

どこに?を使うかで $4$ 通り，さらに?の個数分だけ $q$ 通りあるので
$4q$ 通り

oを2回,?を2回使うパターン

どこに?を使うかで $_4 C _2 = 6$ 通り，さらに?の個数分だけ $q^2$ 通りあるので
$6q^2$ 通り

oを1回,?を3回使うパターン

どこにoを使うかで $ 4 $ 通り，さらに?の個数分だけ $q^3$ 通りあるので
$4q^3$ 通り

合計は

$ 4q^3 + 6q^2 + 4q + 1 $ 通り

o が 0 個

?の個数を4回かければよいので
$ q^4 $ 通り

解説記事

公式解説

$10^4$ 通りなので，全部数えるようにしてもできそうですね。

ユーザー解説

こちらは場合分けしていますね。

感想

今回はC問題までを45分で解くことができました。

D問題は解けなかったので，次回こそチャレンジ！