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を出力すればよいです。
本番で提出したコード
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問題は解けなかったので，次回こそチャレンジ！