paizaオンラインハッカソン Vol.7「プログラミングで彼女をつくる」 水着問題 [python]
これを受けて、水着問題の回答が思ったのと違ったので上げておきます。
問題
POH 「水着」ゲットチャレンジ!
階乗とは数学の演算の一つで、N の階乗をN! と書きます。N が自然数であるとき、階乗は次のように計算できます。
N! = N * (N - 1) * ... * 2 * 1
N が与えられたとき、N! のすべての桁の代わりに、N! の最下位桁から続く0 をすべて除いた値の下位9桁を求めるプログラムを作成してください。 9桁ではあるが先頭が0であるような場合は先頭の0を取り除いた値を出力してください。先頭に0のついた値を出力すると誤答となります。
例えば N = 38 の時は以下のようになります。 ※画像は問題のサイトより
コード
必要な桁だけを計算するように最適化しました(桁数をカットしながらやらないと制限時間を超えてしまう…)
import re #from functools import * from time import sleep #from math import factorial pattern = re.compile("(\d{9})0*$") def _format(n): t = str(n) if len(t) < 9: t = str(int(t[::-1]))[::-1] else: t = pattern.search(t).group(1) return int(t) #@lru_cache(maxsize=None) def factorial(n): ret = 1 for i in range(1, n+1): if i % 10 == 0: ret = _format(ret * i) else: ret *= i return _format(ret) i = input() n = int(i) try: print(factorial(n)) except: sleep(10) # 実行エラーが起きたことを分かるようにするため
実行結果
桁上げに着目すればpythonでも水着ゲットできるな pic.twitter.com/mGUsvp1uIZ
— 友利奈緒 (@K_atc) 2016, 1月 1
杏ちゃんは茶髪の制服姿が一番かわいいと思う