ABC084 D - 2017-like Numberを解いた-ぐぐりらにっき

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

復習記事です。
結局解けたけどTLE一回してしまったので、復習。

## 問題

Nが素数で、(N+1)/2も素数であるN(=2017に似た数)の個数を求める問題。

クエリがQ個与えられる。

ある区間に入っている2017に似た数の個数を求めるクエリが投げられるので、これに答えていく

## 解法

まず、素数のリストを得る必要がある。

クエリの区間の最大(右端)は問題設定から$10^5$なので、$10^5$以下の素数のリストが得られればよい。

愚直に素数かを判定して素数ならリストにいれるというのでは遅いので、エラトステネスの篩を使う。

```python
def eratosthenes(n):
    """n以下の素数をエラトステネスの篩によって求める.リストをかえす"""
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]
```

これで素数のリストが得られる。

次に2017に似た数を列挙して個数を数える。判定は定義の通りやればいいけれど、うっかりすると計算量が多くなるので注意しないといけない。

というのは

```python
primes=eratosthenes(10**5)
like_2017=[p for p in primes if (p+1)//2 in primes]

```
とかすると、毎回primesを全部見て素数であるかを調べてしまう。

$10^5$だと素数のリストは10000個ぐらいあったので、$10^8$ぐらいになってしまって間に合わない。

ので、自然数$x$が素数かどうかをO(1)で調べられるようにフラグで管理する。

```python
_primes = eratosthenes(N)

primes = [False] * (10**5 + 1)

for p in _primes:
    primes[p] = True

like_2017 = [False] * (10**5 + 1)

for p in _primes:
    if primes[(p + 1) // 2]:
        like_2017[p] = True

```

こういうかんじ。

こういう書き方がすぐできるようになりたい。どうしても特にpythonだと`if a in list:`みたいな書き方が簡単だし見やすいから書いてしまう。反省。(一回TLEして気づいて書き直した)

こうして、ある数$x$が2017に似た数かを判定できるようになったので、最後の区間のクエリに答える部分を書けばよくて、これはすぐに思いつけた

累積和を先に計算しておいて、左端を右端から引けばいい、みたいなやつです。区間といわれるとこれかな？となるようになってきました。

```python
c = 0
C = [0]
for i in range(1, 10**5 + 1):
    if like_2017[i]:
        c += 1
    C.append(c)

```

`C[x]`を$x$以下の2017に似た数の個数として求めていきます。

で、ラスト

```python

for _ in range(Q):
    left, right = map(int, input().split())
    print(C[right] - C[left - 1])

```

## まとめ

教訓は

* 素数のリストを求めるならエラトステネスの篩
* ある要素がリストに入っているかのチェックはフラグで管理すれば高速化できる
* 区間は累積和を計算しておいて後でその都度引き算する

ですかね。

ABC084 D - 2017-like Numberを解いた

0 件のコメント:

コメントを投稿

このブログを検索

POPULAR POSTS

SPONSORED LINK

RECENT POSTS

TWEETS

ARCHIVES

LABEL

CONTACT