0. はじめに
就活が終わった24歳、学生です。
AtCoderの過去問をやっていくにあたって、以下のような素晴らしいサービスがありました:
とりあえずここに載っている問題をやっていきます。
コンテスト形式なので、気軽にコンテストさながらの緊張感で問題を解いていけそう。初参加。備忘録として、詰まった問題や、解けたけど時間がかかり過ぎた問題などを記していこうと思います。コンテストは「まよコン」というものに参加させていただきました。
1. 詰まった問題など
その1 : ABC 148 E - Double Factorial (500 点)
【問題概要】
$0$以上の整数$n$に対し、$f(n)$を次のように定義します。
- $f(n)=1$ ($n<2$のとき)
- $f(n)=nf(n-2)$ ($n\geq2$のとき)
整数$N$が与えられます。$f(N)$を$10$進法で表記した時に末尾に何個の$0$が続くかを求めてください。
【制約】
- $0 \le N \le 10^{18}$
- $N$ は整数
【数値例】
1)
$N = 12$
答え: 1
$f(12)=12×10×8×6×4×2=46080$ なので、末尾の$0$の個数は$1$個。
【考えていたこと】
- 問題文の関数を愚直に実装すると、Nが大きすぎる時に計算時間がエグいことになる
- $f(n)=n!!$であることに気づいた
- $n$が奇数なら0だし、偶数なら素因数$5$の個数が答えになる？。高校数学かな？
数学的な発想は至ったが、コードにする前にタイムオーバーになってしまった。難しい。
【ポイント】
- あ
【他の人の提出で通ってたやつ】
n = int(input())
cnt = 0
if n % 2 == 0:
i = 1
while n // 5 ** i > 0:
cnt += (n // 5 ** i)//2
i += 1
print(cnt)
$5^1$の倍数, $5^2$の倍数, $5^3$の倍数, ...の数を数えて行って総和を求めている。
2. おわりに
初めてのバチャコンでしたが、思いのほか集中できて楽しかったです。他の人も同時に解いているというのは思いの外モチベになりますね。当分は、バチャコンに参加しながら解放パターンを増やしていきたいです。
この記事を書く際、markdownの書き方は以下のリンクを参考にしました。
https://mathlandscape.com/latex-equal/