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

問題

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

一覧ページ

解法手順1

1. 入力から部署の数Nと各部署の人数Kiを受け取る。
2. 部署の人数のリストを昇順にソートする。
3. 全ての部署の人数の合計を計算する。
4. 1からNまでの各数iについて、以下の処理を行う：
   a. 部署のリストからi個の部署を選ぶ全ての組み合わせを生成する。
   b. 各組み合わせについて：
   • 選んだ部署の人数の合計（グループA）を計算する。
   • 残りの部署の人数の合計（グループB）を計算する。
   • グループAとグループBの人数の差の絶対値を計算する。
   • この差が今までの最小値より小さければ、最小値を更新する。
   • 同時に、グループAとグループBの人数の大きい方を答えの候補として記録する。
5. 最終的に記録された答えの候補を出力する。

ACコード1

ac.py

import itertools  # 組み合わせを生成するためのモジュールをインポート

def io_func():
    # 入力を受け取る関数
    n = int(input())  # 部署の数を入力
    k = input()  # 各部署の人数を文字列として入力
    return n, k

def solve(n, k):
    # メインの処理を行う関数
    lst = list(map(int, k.split()))  # 文字列を整数のリストに変換
    lst.sort()  # リストを昇順にソート
    total = sum(lst)  # 全部署の人数の合計を計算
    min_diff = float('inf')  # 最小の差を初期化（無限大で初期化）
    ans = 0  # 答えを格納する変数を初期化

    for i in range(n):
        # 1からNまでの各数iについて処理
        for team in itertools.combinations(lst, i+1):
            # i+1個の部署を選ぶ全ての組み合わせを生成
            team_sum = sum(team)  # 選んだ部署の人数の合計（グループA）
            other_sum = total - team_sum  # 残りの部署の人数の合計（グループB）
            diff = abs(other_sum - team_sum)  # グループAとBの人数の差の絶対値
            if min_diff > diff:
                # 差が今までの最小値より小さければ更新
                min_diff = diff
                ans = max(other_sum, team_sum)  # グループAとBの人数の大きい方を記録

    return ans  # 最終的な答えを返す

# メイン処理
n, k = io_func()  # 入力を受け取る
result = solve(n, k)  # 問題を解く
print(result)  # 結果を出力

###
# n: 部署の数
# k: 各部署の人数を表す文字列
# lst: 各部署の人数を整数で格納したリスト
# total: 全部署の人数の合計
# min_diff: グループAとグループBの人数の差の最小値
# ans: 同時に昼休みをとる最大人数の最小値（最終的な答え）
# team: 選ばれた部署の組み合わせ
# team_sum: 選ばれた部署の人数の合計（グループA）
# other_sum: 選ばれなかった部署の人数の合計（グループB）
# diff: グループAとグループBの人数の差の絶対値

# 1. io_func関数で入力を受け取る
# 2. solve関数で主な処理を行う
#    a. 入力された部署の人数をリストに変換し、ソートする
#    b. 全部署の人数の合計を計算する
#    c. 1からNまでの各数iについて、i個の部署を選ぶ全ての組み合わせを生成
#    d. 各組み合わせについて、選んだ部署と選ばなかった部署の人数の差を計算
#    e. 差が最小になる組み合わせを見つけ、そのときの大きい方のグループの人数を記録
# 3. 最終的な答えを出力する

オブジェクト指向版1

ac_object.py

import itertools
import logging
from abc import ABC, abstractmethod

def setup_logger(debug_mode):
    logger = logging.getLogger(__name__)
    if not logger.handlers:  # ハンドラが存在しない場合のみ追加
        logger.setLevel(logging.DEBUG if debug_mode else logging.INFO)
        formatter = logging.Formatter('%(asctime)s - %(name)s - %(levelname)s - %(message)s')
        
        file_handler = logging.FileHandler('program_trace.log', encoding="utf8")
        file_handler.setFormatter(formatter)
        logger.addHandler(file_handler)
    
    return logger

class InputHandler(ABC):
    @abstractmethod
    def get_input(self):
        pass

class OutputHandler(ABC):
    @abstractmethod
    def output_result(self, result):
        pass

class StandardInputHandler(InputHandler):
    def get_input(self):
        n = int(input())  # 部署の数を入力
        k = input()  # 各部署の人数を文字列として入力
        return n, k

class StandardOutputHandler(OutputHandler):
    def output_result(self, result):
        print(result)  # 結果を出力

class LunchBreakOptimizer:
    def __init__(self, debug_mode=False):
        self.logger = setup_logger(debug_mode)

    def solve(self, n, k):
        self.logger.debug("solve関数を開始")
        lst = list(map(int, k.split()))  # 文字列を整数のリストに変換
        lst.sort()  # リストを昇順にソート
        self.logger.debug(f"ソート後のリスト: {lst}")
        
        total = sum(lst)  # 全部署の人数の合計を計算
        self.logger.debug(f"全部署の人数の合計: {total}")
        
        min_diff = float('inf')  # 最小の差を初期化（無限大で初期化）
        ans = 0  # 答えを格納する変数を初期化

        for i in range(n):
            self.logger.debug(f"{i+1}個の部署を選ぶ組み合わせを生成")
            for team in itertools.combinations(lst, i+1):
                team_sum = sum(team)  # 選んだ部署の人数の合計（グループA）
                other_sum = total - team_sum  # 残りの部署の人数の合計（グループB）
                diff = abs(other_sum - team_sum)  # グループAとBの人数の差の絶対値
                self.logger.debug(f"チーム: {team}, チーム合計: {team_sum}, 他の合計: {other_sum}, 差: {diff}")
                if min_diff > diff:
                    min_diff = diff
                    ans = max(other_sum, team_sum)
                    self.logger.debug(f"新しい最小差: {min_diff}, 新しい答え: {ans}")

        self.logger.debug(f"solve関数終了。最終的な答え: {ans}")
        return ans  # 最終的な答えを返す

class LunchBreakManager:
    def __init__(self, input_handler: InputHandler, output_handler: OutputHandler, optimizer: LunchBreakOptimizer):
        self.input_handler = input_handler
        self.output_handler = output_handler
        self.optimizer = optimizer

    def run(self):
        n, k = self.input_handler.get_input()
        result = self.optimizer.solve(n, k)
        self.output_handler.output_result(result)

# メイン処理
if __name__ == "__main__":
    debug_mode = True  # デバッグモードを有効にする場合はTrueに設定
    input_handler = StandardInputHandler()
    output_handler = StandardOutputHandler()
    optimizer = LunchBreakOptimizer(debug_mode)
    manager = LunchBreakManager(input_handler, output_handler, optimizer)
    manager.run()

オブジェクト図