読者です 読者をやめる 読者になる 読者になる

ヾノ*>ㅅ<)ノシ帳

技術ブログに見せかけて、ジャンル制限のないふりーだむなブログです。

paizaオンラインハッカソン Vol.7「プログラミングで彼女をつくる」 水着問題 [python]

競技プログラミング

paiza.hatenablog.com

これを受けて、水着問題の回答が思ったのと違ったので上げておきます。

問題

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) # 実行エラーが起きたことを分かるようにするため

実行結果


杏ちゃんは茶髪の制服姿が一番かわいいと思う