AtCoder:ABC114-C(755)を解いた-ぐぐりらにっき

こんにちは、ぐぐりら(<a href="https://twitter.com/guglilac">@guglilac</a>)です。

与えられたN以下の753数の個数を求める問題。

753数は、3,5,7以外の数字が入ってないかつ3,5,7が一回は必ず入っている数字のこと。

Nが$10^9$のオーダーなので全部調べると間に合わない。

ポイントは、解説で準753数と呼んでいる「3,5,7以外の数字が入ってない数字」を先に列挙して、その中で「3,5,7が一回は必ず入っているかどうか」という条件をcheckするという考え方ができるかどうか、でした。

準753数の個数が少なく、かつN個の数字を全て舐めなくても準753数のリストが得られることに気づけるかどうかが大事な問題な気がします。

準753数の個数の見積もりですが、$p$桁の準753数の個数が$3^p$個である(重複順列)であることを考えれば準753数の個数は等比数列の和になるので、$3^a$($a$は大きくても9とか10ぐらい)しかなくて、これは数万ぐらい。

準753数のリストの作り方は、解説PDFには再帰関数を用いるものが紹介されていました。

後ろに3,5,7をつけていくという感じです。

自分は直積を使うものを先に思いついたのでそっちで書いてしまいました。

準753数を求めることと753数かcheckする部分を分けて書いたのでこれいけましたが、

解説コードのように再帰関数を使えばこの二つはまとめて同時に処理できるので、そっちの方がコード量が少なくていいですね。

せっかく書いたので直積を使うバージョンを載せます。

pythonの`itertools.product`を使います。
重複順列が作れます。
repeatで長さを指定できるので、今回は桁数ごとに重複順列を生成して、頑張ります。

```python
def get_A_product(digits, N):
    A = []
    flag = False
    p = 3
    while True:
        for tup in itertools.product(digits, repeat=p):
            a = int("".join(list(map(str, tup))))
            if a > N:
                flag = True
                break
            A.append(a)
        if flag:
            break
        p += 1
    return A

digits=[3,5,7]
A = get_A_product(digits, N)  
```

こんなかんじで準753数を求めて、一個ずつもう一つの条件の方をcheckするようにしました。

準753数の桁数は10も行かないぐらいなので、checkにもそこまで計算量がかかりません。

```python
if "3" in str(a) and "5" in str(a) and "7" in str(a):
  count+=1
```

解説のをみてこの方がかっこいいなと思いました。
勉強になります。
```python
if all(str(a).count(c) > 0 for c in "753"):
        count += 1
```

AtCoder:ABC114-C(755)を解いた

0 件のコメント:

コメントを投稿

このブログを検索

POPULAR POSTS

SPONSORED LINK

RECENT POSTS

TWEETS

ARCHIVES

LABEL

CONTACT