連続する整数値の中に「7」がいくつ出現するか数えるプログラムの高速化


大学で行っているプログラミングの問題で「連続する整数値の中に出現する「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]




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

「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]




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

「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]

