productでn進数数え上げ(Rubyで競プロ ABC114 C)

## はじめに
この記事は、Arrayにproductメソッドを使ってみたいので、
productを使ってABC114Cを解くという記事です。

https://beta.atcoder.jp/contests/abc114/tasks/abc114_c

## product って何？
こちらを御覧ください。(丸投げ)
https://ref.xaio.jp/ruby/classes/array/product

実際に使うとこんな感じです。
(こういうのをデカルト積と言うそうです)

```Ruby
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のデカルト積を計算してくれます。

```Ruby
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利用して解いてみる
###問題
https://beta.atcoder.jp/contests/abc114/tasks/abc114_c

###問題要約
n以下の自然数のうち、3,5,7を１個以上ずつ含むもの(*)はいくつある？

```math
1 < n < 10^9
```

###方針
3,5,7だけでできている10^9未満の整数を全部並べて、
3,5,7が１個ずつ以上あるn以下のものの数を数えればよくね？

###実際の実装

####例えば、3桁のものをすべて列挙するなら

```Ruby
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以下

ということでこのように書けますね。

```Ruby
ary1.product(ary1,ary1).count {
  |a| p a[0]*100+a[1]*10+a[2] <= n && a.uniq.size == 3 
}
```

ところで、3つの要素を3桁の整数にするのがめんどくさいので、文字列として結合することにしましょう

```Ruby
ary1 = ['3','5','7']
ary1.product(ary1,ary1).count {
  |a| a.inject(:+).to_i <= n && a.uniq.size == 3 
}
```

さて、3桁の場合を考えられたので、あとは4桁...9桁を考えれば勝ちです。

ということを前提に、最終的な答えとして提出した以下のコードを御覧ください。

####答え(この答えはカスなので、追追記やコメントを御覧ください)

```Ruby
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](https://docs.ruby-lang.org/ja/2.5.0/method/Array/i/repeated_permutation.html) を使うともっと簡潔にできそうですね。

こちらのメソッドを利用して、以下のように書き直すことができました。

```Ruby
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なんていらなかったんや...)