AtCoderわからん日記_2 ABC148E

はじめに

DができたからEもちょっと覗いてみよかな～と思って、パっと見難しすぎる数式がある感じでもないしいけるかな？　と思ってやってみました。結論から言うと、全くわからなかったです。これがE問題……アルゴリズムの基本をきちんと勉強するまでは、がんばるのはDまででいいかもしれないですね。
問題はABC148のE問題より。以下引用です。

E - Double Factorial

0以上の整数nに対し、f(n)を次のように定義します。
f(n)=1(n<2のとき)
f(n)=nf(n−2)(n≥2のとき)
整数Nが与えられます。
f(N)を10進法で表記した時に末尾に何個の0が続くかを求めてください。

考えたこと

①とりあえず掛けて、末尾の0が何個あるか考えるか
振り返って書いてても恥ずかしくなるぐらい愚かですね。昨日計算量について教えてもらったばっかりなのに……。

1回目

import re
n = int(input())
i=n-2
while i >= 2:
    n *= i
    i -= 2
    ans = re.search('0+$' , str(n))
print(0 if n%10 !=0 or n < 2 else len(str(n))-ans.start())

TLEでした。また同じ間違いをしてしまった……。愚か。無駄にサーバーに負荷をかけちゃって申し訳ない。
わざわざ正規表現の勉強もしたし、こないだ学んだ三項演算子もさっそく使ったんだけど。

2回目

①そもそも奇数から始まったら10もクソもないわ
②5も出てこないから出てくる10の数だけでええわ
今更気づきました。愚かの極みか？

import re
n = int(input())
ans=0
#奇数のときと小さすぎるときはナシ
if n % 2 !=0 or n < 10:
    print(0)
else:
    while n >= 10:
        #とりあえず10の倍数になるまで減らす
        if n % 10 != 0:
            n -= 2
        #10減らして末尾の0を数えて足しまくる
        else:
            z = re.search('0+$' , str(n))
            ans += len(str(n)) - z.start()
            n -= 10


    print(ans)

TLEです。さっきよか減ったけど！　いけるかなと思ったんですけど……確かにもっと短くできそうな気はする。0の数に規則性があることは自明だものな。
全然わからん。カンニングします。

強人（つよびと）の解答

• 2で割って、5で割った商を割り足し続けると答えになる¹

なんで？！　全然わからん。プログラマ、IQが300ある²？？？
そういうなにがしかのアルゴリズムの基本なんだろうな。アルゴリズムの勉強ちゃんとします。

（追記）

• 約数に5が現れてくると、周りの偶数に含まれる2でまた0が増える
• 奇数を除いたため、約数に5が現れるのは2*5ⁱのとき
• なので、2*5ⁱが現れるたびカウントすればよい

→5で割り続ける or n//2*5ⁱをし続ける
なるほどな～！

---

1. 他にもいくつかあったけれど一番脳内で噛み砕けそうなのがこれでした ↩

2. 一行で終わっている強強人（つよつよびと）はたぶんIQ5000ぐらいある ↩