27575


大学で行っているプログラミングの問題で「連続する整数値の中に出現する「7」がいくつあるかを数えてください。」という問題が出題されました。

例えば`[7, 99]`なら、「1,2,3,4,5,6,7」 と
「1,2,3,...,97,98,99」の数字の中にいくつ`7`が出現するかというもので、7なら1、99なら20という答えになります。  
（`77`は`7`が2個出現するので2個とカウントする。）  
よって答えは`[1, 20]`という結果を1秒以内に表示しないといけないというのが課題です。

しかし、`[99, 77777, 23678947, 732465890,
1912478368]`この桁になると、処理速度が遅くて1秒を超えてしまい不可となってしまいます。  
処理速度を早くするためにはどうすればよいでしょうか？Pythonでは限界があるのでしょうか？  
コツとかがあれば是非教えてください！

[code]

    import re
    v = [99,77777,23678947,732465890,1912478368]
    try:
        while True:
            v.append(input())
    except EOFError:
        pass
    
    for o in range(len(v)):
        x = v[o]
        z = []
        b = []
        d = 0
        w = int(x)
    
        for s in range(1,w+1):
            matchOB = re.findall("7",str(s))
            if matchOB:
                d += len(matchOB)
    
    print(d)
    
[/code]


CC BY-SA 3.0
2016-07-12T11:49:43.050
27568
2016-07-22T09:00:03.563
2016-07-12T15:42:46.200
3068
15627
question
python アルゴリズム
連続する整数値の中に「7」がいくつ出現するか数えるプログラムの高速化


そもそも正規表現を用いた文字列の問題ではなく、数値を用いた数学的な問題だと思います。  
例えば`17 % 10`（10で割った剰余）を計算すれば１の位が`7`であることがわかります。


CC BY-SA 3.0
2016-07-12T13:23:50.223
27569
2016-07-12T13:23:50.223
4236
27568
answer


そのまま文字列として数えても遅いです。10進数における桁ごとに考える必要があります。

例えば、0000 から 9999 を考えて見ます。1から3の位までについて、000 から 999 のパターンが 10回現れます。つまり、000 から 999
で現れる7の数に10をかければ1から3の位について7がいくつあったかがわかり、再帰的に計算できます。あとは4の位ですが、7000 から 7999
までありますので、1000個足せばいいとなります。これは0から10^kまで(10^kを含まず)において、同じように言えることなので、k回で計算可能です。なお、念のためメモ化しておくと良いような気がします。

次に abbbb と言う風になっていると考えます。0 から (a-1)9999 と a0000 から abbbb にわけます。0 から (a-1)9999
も先ほどと同じ考えて 0000 から 9999 のパターンがa回あるとなります。これは先ほど求め方を見たパターンでした。のこりは 0 から bbbb
について数えれば良いとなりますが、同じように再帰的に求められます。ここまで計算したのは1から4桁目なので、aの数に応じて5桁目の7をどれだけ足す必要があるかを考えます。桁が何桁だろう同じ考えで再帰でいけます。

よって最終的に計算量はO(log
n)でいけるようになるかなと。適当に書いたので間違ってそうなところがありそうですが、下のコードのコメントも参考にしてください。

[code]

    # Python3前提。Python2の場合は print や // について書き換え等行うこと。
    
    # 稚拙だけどメモ化
    count7keta_memo = [0]
    def count7keta(k):
        '''
        0 から 10^k まで(終端含まず)について 7 の個数 f(k) を考える。
        0 から 10^(k-1) まで(終端含まず)について 7 が f(k-1) 個となる。
        0 から k-1 の位で現れる 7 の数は k の位が 0..9 の 10 パターンあるから、
        f(k-1) * 10 個現れることになる。
        あとは k の位が 7 になる場合であり、10^(k-1) 個である。
        つまり、f(k-1) * 10 + 10^(k-1) 個の 7 が現れる。
        '''
        # 既に計算済みならそれを返す。
        if k < len(count7keta_memo):
            return count7keta_memo[k]
        # 一つ少ない桁から今の桁を導きだす。
        count = count7keta(k - 1) * 10 + 10 ** (k - 1)
        # 必ず足りないのは最後になるはずなので、メモに追加して記録。
        count7keta_memo.append(count)
        return count
    
    def count7(n):
        '''
        0 から n まで(終端含む)について 7 の個数 g(n) を考える。
        なお、f(k) は 10^k の 7 の数と定義する。
        まず、n = a * 10 ^ k + b と分解する。(k >= 0, 1 <= a <= 9, b < 10 ^ k)
        a が 1 から 6 の場合は f(k) * a + g(b)
        a が 7 の場合は、終わりが全て k 桁目が 7 なので f(k) * a + g(b) + b + 1
            0 から b なので b + 1 であることに注意
        a が 8 から 9 の場合は 7 の所を考えて f(k) * a + g(b) + 10 ^ k
        最初の 0 はカウントの対象にならないため、1 から n までと考えてもよい。
        '''
        # 0 以下は 0
        if n <= 0:
            return 0
        # a, b, k を計算する
        a = n
        k = 0
        while a > 9:
            k += 1
            a //= 10
        b = n - a * (10 ** k)
        # 一応テスト用のアサーション
        assert(k >= 0)
        assert(0 < a < 10)
        assert(0 <= b < 10 ** k)
        # a で条件分岐し、a, b, k から算出する。
        if a < 7:
            return count7keta(k) * a + count7(b)
        elif a == 7:
            return count7keta(k) * a + count7(b) + b + 1
        else:
            return count7keta(k) * a + count7(b) + 10 ** k
    
    list = [99, 77777, 23678947, 732465890, 1912478368]
    result = [count7(n) for n in list]
    print(result)
    
[/code]


CC BY-SA 3.0
2016-07-12T15:03:05.857
27574
2016-07-12T15:03:05.857
7347
27568
answer


ものごとは分けて考えましょう。

「1からnまでの連続する整数値」のうち(以下A)、1の位には `7` はいくつでてくるでしょうか? n が 10 以上ならば、少なくとも `int(n /
10)` 回はでてきますよね? さらに `n % 10` が 7 以上であれば、それに +1 回加えて登場するはずです。つまり n = 30 までなら
`7`, `17`, `27` の 3回ですが、n = 37 ならば前の 3 つに `37` を加えて 4 回でてくるはずです。

では次に A のうち 10 の位には `7` はいくつでてくるでしょうか? n が 100 以上ならば、間違いなく `int(n / 100) * 10`
回はでてきます。`n % 100` が 70 から 78 の時は、`1の位の数字 +1` 回が追加されますね。 `n % 100` が 79 以上の時は
+10 回となるでしょう。

同様に A のうち 1000 の位はどうなるでしょう? 10000 の位はどうでしょう? そうして一般化していけば、目的のプログラムができるでしょう。

[code]

    def cnt7(v):
        return cnt7b(v, 1)
    
    def cnt7b(v, b):
        if v < b:
            return 0
        bn = b * 10
        n = int(v / bn) * b
        m = int(v / b) % 10
        if m == 7:
            n += (v % b) + 1
        elif m > 7:
            n += b
        return n + cnt7b(v, bn)
    
    def calc(v):
        print("%d -> %d" % (v, cnt7(v)))
    
    for v in [99, 77777, 23678947, 732465890, 1912478368]:
        calc(v)
    
[/code]


CC BY-SA 3.0
2016-07-12T15:08:59.327
27575
2016-07-12T15:29:21.543
2016-07-12T15:29:21.543
208
208
27568
answer


連続する整数ということであれば、1〜99なら20回、1〜999なら300回、1〜9999なら400回と出現回数に規則性がある（桁数をmとすると、10 **
(m - 2) * (m - 1)）ので、それほど処理能力を使わずに出せそうです。

それぞれの桁にある7の数は等しく、9999であれば1桁目に1000回、2桁目も1000回、3桁目も4桁目も1000回（10 ** (m -
2)）出現します。

これに7777等の桁の途中で終了してしまう際の回数を加味してあげれば答えが出ます。

[code]

    import numpy as np
    
    def count7(n):
        cnt = 0
        # 桁数
        m = int(np.log10(n) + 1)
        # 桁ごとに出現回数をカウントする
        for i in range(m):
            # 桁数から考えて必ず出現する回数
            cnt += int(n / 10 ** (i + 1)) * 10 ** i
            # 桁の途中で出現している回数
            cnt += np.clip((n % 10 ** (i + 1) - 7 * 10 ** i + 1), 0, 10 ** i)
        return cnt
    
    for n in [99, 77777, 23678947, 732465890, 1912478368]:
        print(count7(n))
    
[/code]

ワンライナーで書いた場合。

[code]

    count7 = lambda n : sum(int(n / 10 ** (i + 1)) * 10 ** i + np.clip((n % 10 ** (i + 1) - 7 * 10 ** i + 1), 0, 10 ** i) for i in range(int(np.log10(n) + 1)))
    
[/code]

このコードだと0以下の整数の場合は動かないので、負も計算する必要がある場合は、負の部分を切り分けてabsして出す形になるかと思います。


CC BY-SA 3.0
2016-07-22T09:00:03.563
27812
2016-07-22T09:00:03.563
17262
27568
answer