Rubyで解くAtCoder ABC 201 (C問題 Rubyでは最短実行時間)
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
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問題は解けなかったので,次回こそチャレンジ!
Author And Source
この問題について(Rubyで解くAtCoder ABC 201 (C問題 Rubyでは最短実行時間)), 我々は、より多くの情報をここで見つけました https://qiita.com/AmaiOmikan/items/f8b1d48c7e7d05627aee著者帰属:元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Content is automatically searched and collected through network algorithms . If there is a violation . Please contact us . We will adjust (correct author information ,or delete content ) as soon as possible .