【競技プログラミング】AtCoder Beginner Contest 302_D問題

問題

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

一覧ページ

解法手順1

1. 入力値N, M, Dを受け取る。
2. 青木君への贈り物の候補リストAを受け取る。
3. すぬけ君への贈り物の候補リストBを受け取る。
4. リストAとBをそれぞれソートする。
5. 答えを格納する変数ansを-1で初期化する。
6. リストAの各要素aについて以下の処理を行う：
   a. a + Dの値を計算し、tempbとする。
   b. リストBにおいてtempb以下の最大の要素のインデックスを二分探索で求める。
   c. 見つかった要素とaの差がD以下であれば、その和をansと比較し、大きい方をansに更新する。
7. 最終的なansを出力する。ansが-1のままであれば、条件を満たす組み合わせが存在しないことを意味する。

ACコード1

ac.py

import bisect

def io_func():
    # 入力値N, M, Dを受け取る
    N, M, D = map(int, input().split())
    # 青木君への贈り物の候補リストAを受け取る
    A = list(map(int, input().split()))
    # すぬけ君への贈り物の候補リストBを受け取る
    B = list(map(int, input().split()))
    return N, M, D, A, B

def solve(N, M, D, A, B):
    # リストAとBをそれぞれソートする
    A.sort()
    B.sort()

    # 答えを格納する変数ansを-1で初期化する
    ans = -1

    # リストAの各要素aについて処理を行う
    for a in A:
        # a + Dの値を計算し、tempbとする
        tempb = a + D
        # リストBにおいてtempb以下の最大の要素のインデックスを二分探索で求める
        ind = bisect.bisect_right(B, tempb)
        # 見つかった要素とaの差がD以下であれば、その和をansと比較し、大きい方をansに更新する
        if ind > 0 and abs(B[ind-1] - a) <= D:
            ans = max(ans, B[ind-1] + a)

    # 最終的なansを出力する
    print(ans)

# メイン処理
N, M, D, A, B = io_func()
solve(N, M, D, A, B)

###
# N: 青木君への贈り物の候補数
# M: すぬけ君への贈り物の候補数
# D: 許容される贈り物の価値の差の最大値
# A: 青木君への贈り物の候補リスト
# B: すぬけ君への贈り物の候補リスト
# ans: 条件を満たす贈り物の組み合わせの最大の価値の和

# 1. io_func関数で入力を受け取る
# 2. solve関数で主な処理を行う
#    - リストAとBをソート
#    - Aの各要素に対して、Bから適切な要素を二分探索で探す
#    - 条件を満たす組み合わせの中で最大の価値の和を求める
# 3. 結果を出力する

オブジェクト指向版1

ac_object.py

import bisect
import logging
from abc import ABC, abstractmethod
from typing import List, Tuple

def setup_logger(debug_mode: bool) -> logging.Logger:
    logger = logging.getLogger(__name__)
    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')
    file_handler.setFormatter(formatter)
    logger.addHandler(file_handler)
    
    return logger

# 入力インターフェース
class InputInterface(ABC):
    @abstractmethod
    def get_input(self) -> Tuple[int, int, int, List[int], List[int]]:
        pass

# 標準入力クラス
class StandardInput(InputInterface):
    def get_input(self) -> Tuple[int, int, int, List[int], List[int]]:
        N, M, D = map(int, input().split())
        A = list(map(int, input().split()))
        B = list(map(int, input().split()))
        return N, M, D, A, B

# ソルバーインターフェース
class SolverInterface(ABC):
    @abstractmethod
    def solve(self, N: int, M: int, D: int, A: List[int], B: List[int]) -> int:
        pass

# 二分探索ソルバークラス
class BinarySearchSolver(SolverInterface):
    def __init__(self, debug_mode: bool = False):
        self.logger = setup_logger(debug_mode)

    def solve(self, N: int, M: int, D: int, A: List[int], B: List[int]) -> int:
        self.logger.debug("ソルバーの処理を開始します")
        A.sort()
        B.sort()
        self.logger.debug(f"ソートされたA: {A}")
        self.logger.debug(f"ソートされたB: {B}")

        ans = -1
        for a in A:
            tempb = a + D
            self.logger.debug(f"tempb = a(={a}) + D(={D})")
            ind = bisect.bisect_right(B, tempb)
            self.logger.debug(f"ind(={ind}) = bisect.bisect_right({B}, {tempb})")
            self.logger.debug(f"現在のa: {a}, tempb: {tempb}, ind: {ind}")
            if ind > 0 and abs(B[ind-1] - a) <= D:
                self.logger.debug(f"if {ind} > 0 and abs(B[{ind}-1] - {a}) <= D:")
                ans = max(ans, B[ind-1] + a)
                self.logger.debug(f"ans = max({ans}, B[{ind}-1] + {a})")
                self.logger.debug(f"新しい最大値: {ans}")

        self.logger.debug(f"最終的な結果: {ans}")
        return ans

# 出力インターフェース
class OutputInterface(ABC):
    @abstractmethod
    def output_result(self, result: int) -> None:
        pass

# 標準出力クラス
class StandardOutput(OutputInterface):
    def output_result(self, result: int) -> None:
        print(result)

# メインクラス
class GiftProblemSolver:
    def __init__(self, input_handler: InputInterface, solver: SolverInterface, output_handler: OutputInterface):
        self.input_handler = input_handler
        self.solver = solver
        self.output_handler = output_handler

    def run(self) -> None:
        N, M, D, A, B = self.input_handler.get_input()
        result = self.solver.solve(N, M, D, A, B)
        self.output_handler.output_result(result)

# メイン処理
if __name__ == "__main__":
    input_handler = StandardInput()
    solver = BinarySearchSolver(debug_mode=False)  # デバッグモードを有効にする
    output_handler = StandardOutput()
    
    problem_solver = GiftProblemSolver(input_handler, solver, output_handler)
    problem_solver.run()

オブジェクト図

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

テスト容易性

ac_object.py

import unittest

class TestBinarySearchSolver(unittest.TestCase):
    def setUp(self):
        self.solver = BinarySearchSolver(debug_mode=True)

    def test_solve_normal_case(self):
        N, M, D = 3, 4, 2
        A = [1, 3, 5]
        B = [2, 4, 6, 8]
        result = self.solver.solve(N, M, D, A, B)
        self.assertEqual(result, 11)

    def test_solve_no_valid_pair(self):
        N, M, D = 2, 2, 1
        A = [1, 10]
        B = [2, 11]
        result = self.solver.solve(N, M, D, A, B)
        self.assertEqual(result, 21)