はじめに
この記事は、Arrayにproductメソッドを使ってみたいので、
productを使ってABC114Cを解くという記事です。
product って何？
こちらを御覧ください。(丸投げ)
https://ref.xaio.jp/ruby/classes/array/product
実際に使うとこんな感じです。
(こういうのをデカルト積と言うそうです)
ary1 = [1,2,3]
ary2 = [4,5,6]
ary1.product(ary2)
#=> [[1, 4], [1, 5], [1, 6], [2, 4], [2, 5], [2, 6], [3, 4], [3, 5], [3, 6]]
ary1.product(ary2).size
#=> 9
ary1とary2のデカルト積を計算してくれます。
ary1 = [1,2,3]
ary2 = [[4,5,6],[7,8,9]]
ary1.product(*ary2)
#=> [[1, 4, 7], [1, 4, 8], [1, 4, 9], [1, 5, 7], [1, 5, 8], [1, 5, 9], [1, 6, 7], [1, 6, 8], [1, 6, 9], [2, 4, 7], [2, 4, 8], [2, 4, 9], [2, 5, 7], [2, 5, 8], [2, 5, 9], [2, 6, 7], [2, 6, 8], [2, 6, 9], [3, 4, 7], [3, 4, 8], [3, 4, 9], [3, 5, 7], [3, 5, 8], [3, 5, 9], [3, 6, 7], [3, 6, 8], [3, 6, 9]]
ary1.product(*ary2).size
#=> 27
このように、複数の配列を渡すこともできます。
こう話してもあんまり有り難みがないかもしれないので、
実際にABC114 Cを解いてみましょう。
ABC114 Cをproduct利用して解いてみる
問題
問題要約
n以下の自然数のうち、3,5,7を１個以上ずつ含むもの(*)はいくつある？
1 < n < 10^9
方針
3,5,7だけでできている10^9未満の整数を全部並べて、
3,5,7が１個ずつ以上あるn以下のものの数を数えればよくね？
実際の実装
例えば、3桁のものをすべて列挙するなら
ary1 = [3,5,7]
ary1.product(ary1,ary1)
#=> => [[3, 3, 3], [3, 3, 5], [3, 3, 7], [3, 5, 3], [3, 5, 5], [3, 5, 7], [3, 7, 3], [3, 7, 5], [3, 7, 7], [5, 3, 3], [5, 3, 5], [5, 3, 7], [5, 5, 3], [5, 5, 5], [5, 5, 7], [5, 7, 3], [5, 7, 5], [5, 7, 7], [7, 3, 3], [7, 3, 5], [7, 3, 7], [7, 5, 3], [7, 5, 5], [7, 5, 7], [7, 7, 3], [7, 7, 5], [7, 7, 7]]
このように書けます。
次に
3,5,7が１個ずつ以上あるn以下
はどのようにかけるでしょうか？
→配列から重複要素を取り除き(=uniq)、そのsizeが3 && 要素をくっつけたやつがn以下
ということでこのように書けますね。
ary1.product(ary1,ary1).count {
|a| p a[0]*100+a[1]*10+a[2] <= n && a.uniq.size == 3
}
ところで、3つの要素を3桁の整数にするのがめんどくさいので、文字列として結合することにしましょう
ary1 = ['3','5','7']
ary1.product(ary1,ary1).count {
|a| a.inject(:+).to_i <= n && a.uniq.size == 3
}
さて、3桁の場合を考えられたので、あとは4桁...9桁を考えれば勝ちです。
ということを前提に、最終的な答えとして提出した以下のコードを御覧ください。
答え(この答えはカスなので、追追記やコメントを御覧ください)
n = gets.chomp.to_i
ans = 0
ary357 = ['3','5','7']
# 3...9桁を考える上で、iとaryに対して、
# aryがi個入った配列を返してくれるメソッドが欲しくなりました
def retarys(int, ary)
retary = []
int.times {retary << ary}
retary
end
# ３桁と同じことを繰り返すだけです。*で配列を展開して渡せることを利用して、
# retarysという自家製メソッドでi個ary357を渡してます。
2.step(8){|i|
# ary357.product(*retarys(i,ary357)) でi+1桁の3,5,7からなる整数を全て列挙してます
# count は trueの数を返してくれる便利な子です。
ans += ary357.product(*retarys(i,ary357)).count {
|aa| (aa.uniq.size == 3) && (aa.inject(:+).to_i <= n)
}
}
puts ans
と、product(デカルト積を計算するメソッド)でABC114のCが解けました！！
やったね！！
最後に
Rubyは競プロ入門に良い言語なんじゃないかと最近思い始めてます。
ABCに限って言えば、時間がきつい問題はあんまり見かけないので、
C++はちょっとダルいなという方にRubyで競プロかじってもらえたらなと思います。
なぜこの記事を書いたのか
２ヶ月ぶりぐらいに昨日ABCへ参加したのですが、やることが分かってたのに、
上記実装ができなくてつらい思いをしたので、この記事を書きました。
今度はcombinationやrepeated_permutationを使った記事が書けたらなと思っています。
(思っているだけで書くとは言っていない)
追記
なんかぐぐったら全列挙は意味が違うらしいので修正しました。
追追記
@scivola さんから教えていただきました。
でもって，Array#repeated_permutation を使うともっと簡潔にできそうですね。
こちらのメソッドを利用して、以下のように書き直すことができました。
n = gets.chomp.to_i
a = ['3','5','7']
ans = 0
3.step(9) {|i| ans += a.repeated_permutation(i).count {
|aa| aa.uniq.size == 3 && aa.join.to_i <= n}
}
p ans
@scivola さんありがとうございます。(productなんていらなかったんや...)