LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@o_chan_t(おー ちゃん)

【競技プログラミング】AtCoder Beginner Contest 148_E問題

Posted at

問題

要約

  1. 関数f(n)の定義

    • n < 2 のとき、f(n) = 1
    • n ≥ 2 のとき、f(n) = n * f(n-2)

  2. 変数

    • N: 与えられる整数

  3. 求めるもの
    f(N)を10進法で表記したときに、末尾に連続して現れる0の個数

既存投稿一覧ページへのリンク

一覧ページ

解法手順

f(N)の末尾の0の個数を効率的に求めるために、直接f(N)を計算するのではなく、数学的な性質を利用する。
末尾の0の個数は、その数の素因数に含まれる2と5の対の数に等しい。
f(N)の定義から、2の因子は常に十分にあるため、5の因子の数が重要になります。

  1. 入力されたNが奇数の場合、f(N)は必ず奇数になるため、末尾の0の個数は0となる。
    この場合、即座に0を出力して終了する。

  2. Nが偶数の場合、f(N)に含まれる5の因子の数を数える必要がある。

  3. f(N)の5の因子の数を効率的に数えるために、Nを2で割った値（N//2）を新たなNとして扱う。
    これは、f(N)の計算過程で偶数の項のみが5の因子を提供するためである。

  4. 新たなNに対して、以下の操作を繰り返す：
    a. N を 5 で割った商（N//5）を答えに加算する。
    これは、現在のNまでの数に含まれる5の因子の数を表す。
    b. N を 5 で割った商で更新する（N = N//5）。
    これは、25, 125, ...といった5の累乗の寄与を考慮するためである。

  5. N が 0 になるまで上記の操作を繰り返し、最終的な答えを出力する。

ACコード

ac.py
def io_func():
    # 標準入力からNを整数として読み込む
    N = int(input())
    return N

def solve(N):
    # Nが奇数の場合、末尾の0の個数は0
    if N % 2 == 1:
        print(0)
        return

    # 末尾の0の個数（5の因子の数）を格納する変数
    zero_count = 0

    # Nを2で割る（偶数の項のみが5の因子を提供するため）
    N //= 2

    # Nが0になるまでループ
    while N:
        # 現在のNまでの数に含まれる5の因子の数を加算
        zero_count += N // 5
        # Nを5で割って更新（5の累乗の寄与を考慮）
        N //= 5

    # 最終的な末尾の0の個数を出力
    print(zero_count)

# メイン処理
N = io_func()
solve(N)

###
# N: 入力された整数値
# zero_count: f(N)の末尾の0の個数（5の因子の数）

# 1. io_func関数で標準入力からNを読み込む
# 2. solve関数でf(N)の末尾の0の個数を計算する
#    2.1 Nが奇数の場合、即座に0を出力して終了
#    2.2 Nが偶数の場合、以下の処理を行う
#        - Nを2で割る
#        - Nが0になるまで以下を繰り返す
#          * N//5を答えに加算
#          * Nを5で割る
#    2.3 最終的な答えを出力する
# 3. メイン処理でio_func関数とsolve関数を呼び出す

オブジェクト指向版1

ac.py
from abc import ABC, abstractmethod

class InputReader(ABC):
    @abstractmethod
    def read_input(self):
        pass

class ConsoleInputReader(InputReader):
    def read_input(self):
        # 標準入力からNを整数として読み込む
        return int(input())

class ZeroCounter(ABC):
    @abstractmethod
    def count_zeros(self, n):
        pass

class FactorialZeroCounter(ZeroCounter):
    def count_zeros(self, n):
        # Nが奇数の場合、末尾の0の個数は0
        if n % 2 == 1:
            return 0

        # 末尾の0の個数（5の因子の数）を格納する変数
        zero_count = 0

        # Nを2で割る（偶数の項のみが5の因子を提供するため）
        n //= 2

        # Nが0になるまでループ
        while n:
            # 現在のNまでの数に含まれる5の因子の数を加算
            zero_count += n // 5
            # Nを5で割って更新（5の累乗の寄与を考慮）
            n //= 5

        return zero_count

class ResultPrinter(ABC):
    @abstractmethod
    def print_result(self, result):
        pass

class ConsoleResultPrinter(ResultPrinter):
    def print_result(self, result):
        # 結果を標準出力に出力
        print(result)

class FactorialZeroCounterApp:
    def __init__(self, input_reader: InputReader, zero_counter: ZeroCounter, result_printer: ResultPrinter):
        self.input_reader = input_reader
        self.zero_counter = zero_counter
        self.result_printer = result_printer

    def run(self):
        # 入力を読み込む
        n = self.input_reader.read_input()
        # 0の個数を計算
        result = self.zero_counter.count_zeros(n)
        # 結果を出力
        self.result_printer.print_result(result)

# メイン処理
if __name__ == "__main__":
    input_reader = ConsoleInputReader()
    zero_counter = FactorialZeroCounter()
    result_printer = ConsoleResultPrinter()
    
    app = FactorialZeroCounterApp(input_reader, zero_counter, result_printer)
    app.run()

###
# n: 入力された整数値
# zero_count: f(N)の末尾の0の個数（5の因子の数）

# InputReader: 入力を読み込むための抽象基底クラス
# ConsoleInputReader: 標準入力から整数を読み込むクラス
# ZeroCounter: 0の個数を数えるための抽象基底クラス
# FactorialZeroCounter: 階乗の末尾の0の個数を数えるクラス
# ResultPrinter: 結果を出力するための抽象基底クラス
# ConsoleResultPrinter: 結果を標準出力に出力するクラス
# FactorialZeroCounterApp: アプリケーションのメインロジックを含むクラス

オブジェクト指向で書くメリット

1. 高い拡張性と柔軟性

現在のコードはコンソールからの入力と出力を扱っていますが、将来的にファイルからの入力や、データベースへの出力に変更したい場合、新しいクラスを追加するだけで対応できます。

ac_object.py
class FileInputReader(InputReader):
    def read_input(self):
        with open('input.txt', 'r') as f:
            return int(f.read().strip())

class DatabaseResultPrinter(ResultPrinter):
    def print_result(self, result):
        # データベースに結果を保存する処理
        pass

# 使用例
app = FactorialZeroCounterApp(FileInputReader(), zero_counter, DatabaseResultPrinter())

2. テストの容易さ

ZeroCounterクラスのテストを書く場合、入力や出力の処理を気にせずにロジックのみをテストできます。

ac_object.py
import unittest

class TestFactorialZeroCounter(unittest.TestCase):
    def setUp(self):
        self.counter = FactorialZeroCounter()

    def test_count_zeros(self):
        self.assertEqual(self.counter.count_zeros(5), 1)
        self.assertEqual(self.counter.count_zeros(10), 2)
        self.assertEqual(self.counter.count_zeros(25), 6)
        self.assertEqual(self.counter.count_zeros(125), 31)

3. 関心の分離

アルゴリズムの変更が必要な場合、FactorialZeroCounterクラスのみを修正すれば良く、入力や出力の処理を変更する必要はありません。

ac_object.py
class OptimizedFactorialZeroCounter(ZeroCounter):
    def count_zeros(self, n):
        # より効率的なアルゴリズムを実装
        pass

# 使用例
app = FactorialZeroCounterApp(input_reader, OptimizedFactorialZeroCounter(), result_printer)

4. コードの再利用性

InputReaderやResultPrinterのインターフェースは、他の数学的問題を解くアプリケーションでも使用できます。

ac_object.py
class PrimeFactorizationApp:
    def __init__(self, input_reader: InputReader, factorizer: Factorizer, result_printer: ResultPrinter):
        self.input_reader = input_reader
        self.factorizer = factorizer
        self.result_printer = result_printer

    def run(self):
        n = self.input_reader.read_input()
        result = self.factorizer.factorize(n)
        self.result_printer.print_result(result)
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?