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?

100万記事ありがとう！2025年もたくさんアウトプットしよう
@o_chan_t(おー ちゃん)

【競技プログラミング】AtCoder Beginner Contest 313_C問題

Posted at

問題

要約

  1. 整数列A = (A1, A2, ..., AN)が与えられる。

  2. 以下の操作を任意の回数（0回も含む）行うことができる：

    • 1 ≤ i, j ≤ N を満たす整数 i, j を選ぶ。
    • Ai を1減らし、Aj を1増やす。

  3. 目標は、Aの最小値と最大値の差を1以下にすることである。

  4. この目標を達成するために必要な最小の操作回数を求める。

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

一覧ページ

解法手順1

アプローチ

  1. 整数列Aをソートし、最小値と最大値を効率的に取得する。
  2. 整数列Aの合計値を求め、理想的な平均値（目標とする均等な状態）を計算する。
  3. 各要素を理想的な平均値に近づけるために必要な操作回数を計算する。
  4. 全体の操作回数を2で割ることで、最小の操作回数を求める。

具体的手順

  1. 入力を受け取り、整数列Aを作成する。
  2. 要素数が1の場合は、操作が不要なので0を出力して終了する。
  3. 整数列Aをソートする。
  4. Aの合計値を計算する。
  5. 理想的な平均値を計算し、average_aリストを作成する。
  6. 余りがある場合、大きい方から順に1ずつ加算して分配する。
  7. 各要素について、現在の値と理想的な平均値との差の絶対値を計算し、合計する。
  8. 合計した差を2で割った値（切り捨て）を最小操作回数として出力する。

ACコード1

ac.py
def io_func():
    # 入力を受け取る
    n = int(input())  # 整数列Aの要素数
    A = list(map(int, input().split()))  # 整数列A
    return n, A

def solve(n, A):
    # 要素数が1の場合は操作不要
    if n == 1:
        return 0

    # 整数列Aをソート
    A.sort()

    # Aの合計値を計算
    suma = sum(A)

    # 理想的な平均値を計算し、average_aリストを作成
    average_a = [suma // n for _ in range(n)]

    # 余りを大きい方から順に1ずつ加算して分配
    for i in range(suma % n):
        average_a[n-1-i] += 1

    # 各要素について、現在の値と理想的な平均値との差の絶対値を計算し、合計
    ans = 0
    for a, avg in zip(A, average_a):
        ans += abs(a - avg)

    # 合計した差を2で割った値（切り捨て）を返す
    return ans // 2

# メイン処理
n, A = io_func()
result = solve(n, A)
print(result)

###
# n: 整数列Aの要素数
# A: 整数列A
# suma: 整数列Aの合計値
# average_a: 理想的な平均値のリスト
# ans: 操作回数の合計
# result: 最小操作回数

# 1. io_func関数で入力を受け取る
# 2. solve関数で主な処理を行う
#   2.1 要素数が1の場合は0を返す
#   2.2 整数列Aをソートする
#   2.3 Aの合計値を計算する
#   2.4 理想的な平均値を計算し、average_aリストを作成する
#   2.5 余りを大きい方から順に1ずつ加算して分配する
#   2.6 各要素について、現在の値と理想的な平均値との差の絶対値を計算し、合計する
#   2.7 合計した差を2で割った値（切り捨て）を返す
# 3. メイン処理で入力を受け取り、solve関数を呼び出し、結果を出力する

オブジェクト指向版1

ac_object.py
from abc import ABC, abstractmethod
from typing import List

# Single Responsibility Principle: 入力処理を担当するクラス
class InputHandler:
    @staticmethod
    def get_input() -> tuple:
        """入力を受け取るメソッド"""
        n = int(input())  # 整数列Aの要素数
        A = list(map(int, input().split()))  # 整数列A
        return n, A

# Open/Closed Principle: 抽象クラスを定義
class Solver(ABC):
    @abstractmethod
    def solve(self, n: int, A: List[int]) -> int:
        """問題を解くメソッド"""
        pass

# Liskov Substitution Principle: Solverを継承した具体的なソルバークラス
class EqualizeArraySolver(Solver):
    def solve(self, n: int, A: List[int]) -> int:
        """整数列を均等化するための最小操作回数を計算"""
        if n == 1:
            return 0

        A.sort()  # 整数列Aをソート
        suma = sum(A)  # Aの合計値を計算

        # 理想的な平均値を計算し、average_aリストを作成
        average_a = [suma // n for _ in range(n)]

        # 余りを大きい方から順に1ずつ加算して分配
        for i in range(suma % n):
            average_a[n-1-i] += 1

        # 各要素について、現在の値と理想的な平均値との差の絶対値を計算し、合計
        ans = sum(abs(a - avg) for a, avg in zip(A, average_a))

        return ans // 2  # 合計した差を2で割った値（切り捨て）を返す

# Dependency Inversion Principle: 高レベルのモジュールが低レベルのモジュールに依存しないようにする
class ProblemSolver:
    def __init__(self, input_handler: InputHandler, solver: Solver):
        self.input_handler = input_handler
        self.solver = solver

    def solve(self) -> int:
        """問題を解くメソッド"""
        n, A = self.input_handler.get_input()
        return self.solver.solve(n, A)

# Interface Segregation Principle: 使用するインターフェースのみを実装
class ResultPrinter:
    @staticmethod
    def print_result(result: int):
        """結果を出力するメソッド"""
        print(result)

# メイン処理
if __name__ == "__main__":
    input_handler = InputHandler()
    solver = EqualizeArraySolver()
    problem_solver = ProblemSolver(input_handler, solver)
    result = problem_solver.solve()
    ResultPrinter.print_result(result)

# n: 整数列Aの要素数
# A: 整数列A
# suma: 整数列Aの合計値
# average_a: 理想的な平均値のリスト
# ans: 操作回数の合計
# result: 最小操作回数

# 1. InputHandlerクラスで入力を受け取る
# 2. EqualizeArraySolverクラスで主な処理を行う
#   2.1 要素数が1の場合は0を返す
#   2.2 整数列Aをソートする
#   2.3 Aの合計値を計算する
#   2.4 理想的な平均値を計算し、average_aリストを作成する
#   2.5 余りを大きい方から順に1ずつ加算して分配する
#   2.6 各要素について、現在の値と理想的な平均値との差の絶対値を計算し、合計する
#   2.7 合計した差を2で割った値（切り捨て）を返す
# 3. ProblemSolverクラスで入力処理とソルバーを組み合わせる
# 4. ResultPrinterクラスで結果を出力する
# 5. メイン処理で各クラスのインスタンスを作成し、問題を解いて結果を出力する

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

拡張性と再利用性

ac_object.py

import logging

class LoggingSolver(Solver):
   def __init__(self, solver: Solver):
       self.solver = solver
       self.logger = logging.getLogger(__name__)

   def solve(self, n: int, A: List[int]) -> int:
       self.logger.info(f"Solving problem with n={n}, A={A}")
       result = self.solver.solve(n, A)
       self.logger.info(f"Problem solved. Result: {result}")
       return result

# 使用例
if __name__ == "__main__":
   logging.basicConfig(level=logging.INFO)
   input_handler = InputHandler()
   solver = LoggingSolver(EqualizeArraySolver())
   problem_solver = ProblemSolver(input_handler, solver)
   result = problem_solver.solve()
   ResultPrinter.print_result(result)

テスト容易性

ac_object.py
import unittest

class TestEqualizeArraySolver(unittest.TestCase):
   def setUp(self):
       self.solver = EqualizeArraySolver()

   def test_solve_single_element(self):
       self.assertEqual(self.solver.solve(1, [5]), 0)

   def test_solve_two_elements(self):
       self.assertEqual(self.solver.solve(2, [1, 5]), 2)

   def test_solve_multiple_elements(self):
       self.assertEqual(self.solver.solve(5, [1, 2, 3, 4, 5]), 3)

   def test_solve_all_same_elements(self):
       self.assertEqual(self.solver.solve(3, [3, 3, 3]), 0)

柔軟性

ac_object.py
class FileInputHandler(InputHandler):
   def get_input(self) -> tuple:
       with open('input.txt', 'r') as f:
           n = int(f.readline())
           A = list(map(int, f.readline().split()))
       return n, A

# 使用例
if __name__ == "__main__":
   input_handler = FileInputHandler()
   solver = EqualizeArraySolver()
   problem_solver = ProblemSolver(input_handler, solver)
   result = problem_solver.solve()
   ResultPrinter.print_result(result)

トレースロジック

ac_object.py
import logging
from typing import List

class EqualizeArraySolver(Solver):
    def __init__(self, debug=False):
        self.debug = debug
        if self.debug:
            # デバッグモードの場合、ロガーを設定
            logging.basicConfig(filename='debug_log.txt', level=logging.DEBUG,
                                format='%(asctime)s - %(levelname)s - %(message)s')
            self.logger = logging.getLogger(__name__)

    def solve(self, n: int, A: List[int]) -> int:
        """整数列を均等化するための最小操作回数を計算"""
        if self.debug:
            self.logger.debug(f"Input: n={n}, A={A}")

        if n == 1:
            if self.debug:
                self.logger.debug("n=1, returning 0")
            return 0

        A.sort()  # 整数列Aをソート
        if self.debug:
            self.logger.debug(f"Sorted A: {A}")

        suma = sum(A)  # Aの合計値を計算
        if self.debug:
            self.logger.debug(f"Sum of A: {suma}")

        # 理想的な平均値を計算し、average_aリストを作成
        average_a = [suma // n for _ in range(n)]
        if self.debug:
            self.logger.debug(f"Initial average_a: {average_a}")

        # 余りを大きい方から順に1ずつ加算して分配
        for i in range(suma % n):
            average_a[n-1-i] += 1
        if self.debug:
            self.logger.debug(f"Final average_a: {average_a}")

        # 各要素について、現在の値と理想的な平均値との差の絶対値を計算し、合計
        ans = sum(abs(a - avg) for a, avg in zip(A, average_a))
        if self.debug:
            self.logger.debug(f"Sum of absolute differences: {ans}")

        result = ans // 2
        if self.debug:
            self.logger.debug(f"Final result: {result}")

        return result  # 合計した差を2で割った値（切り捨て）を返す
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?