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

# 問題
https://atcoder.jp/contests/abc374/tasks/abc374_e

## 入力例01
![25012601.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/530912/1d7d3649-9c58-acef-b7c4-3fd78dfca180.png)

### 解答
![25012602.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/530912/2958514c-8d1b-6494-4da3-18c97ea0976d.png)


# 既存投稿一覧ページへのリンク
[一覧ページ](https://qiita.com/o_chan_t/items/fc759695acfaef8df2cc)

## Before
[AtCoder Beginner Contest 373_D 問題](https://qiita.com/o_chan_t/items/c34c731ce3afd2708eb7)

## Next
[AtCoder Beginner Contest 375_C 問題](https://qiita.com/o_chan_t/items/1ab563cf7c348dec994c)



# 解法手順1

1. 入力を受け取る。N（工程数）とX（予算）、各工程の機械の情報（Ai, Pi, Bi, Qi）を読み込む。

2. 二分探索の範囲を設定する。初期値として、okを0、ngを10^9 + 1とする。

3. 二分探索を行う。
   - 中間値midを計算する。
   - is_ok関数を用いて、製造能力midが予算内で達成可能かどうかを判定する。
   - 可能な場合はokをmidに更新し、不可能な場合はngをmidに更新する。
   - ng - okが1より大きい間、この処理を繰り返す。

4. is_ok関数の実装:
   - 各工程に対して、min_cost関数を呼び出し、必要なコストを計算する。
   - 全工程のコストの合計が予算X以下であれば、Trueを返す。

5. min_cost関数の実装:
   - 2つの機械の組み合わせを考慮し、指定された製造能力wを達成するための最小コストを計算する。
   - 機械Sの台数を0から100まで変化させ、必要な機械Tの台数を計算する。
   - 同様に、機械Tの台数を0から100まで変化させ、必要な機械Sの台数を計算する。
   - すべての組み合わせの中で最小のコストを返す。

6. 二分探索が終了したら、okの値（達成可能な最大の製造能力）を出力する。


# ACコード1
```python:ac.py
import sys

def io_func():
    # 標準入力から値を読み込む
    input = sys.stdin.readline
    N, X = map(int, input().split())
    APBQ = [tuple(map(int, input().split())) for _ in range(N)]
    return N, X, APBQ

def min_cost(w, i, APBQ):
    # 指定された製造能力wを達成するための最小コストを計算する
    a, p, b, q = APBQ[i]
    ret = 10**18  # 最小コストの初期値を大きな値に設定
    
    # 機械Sの台数を0から100まで変化させる
    for j in range(101):
        rem_task = w - j * a
        k = max(0, -(-rem_task // b))  # 切り上げ除算
        cost = j * p + k * q
        ret = min(ret, cost)
    
    # 機械Tの台数を0から100まで変化させる
    for k in range(101):
        rem_task = w - k * b
        j = max(0, -(-rem_task // a))  # 切り上げ除算
        cost = j * p + k * q
        ret = min(ret, cost)
    
    return ret

def is_ok(w, N, X, APBQ):
    # 製造能力wが予算内で達成可能かどうかを判定する
    cost = 0
    for i in range(N):
        cost += min_cost(w, i, APBQ)
    return cost <= X

def solve(N, X, APBQ):
    # 二分探索の範囲を設定
    ok = 0
    ng = 10**9 + 1
    
    # 二分探索を行う
    while ng - ok > 1:
        mid = (ok + ng) // 2
        if is_ok(mid, N, X, APBQ):
            ok = mid
        else:
            ng = mid
    
    # 達成可能な最大の製造能力を出力
    print(ok)

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

###
# - N: 工程数
# - X: 予算
# - APBQ: 各工程の機械の情報 (Ai, Pi, Bi, Qi) のリスト
# - w: 製造能力
# - a, p: 機械Sの製造能力とコスト
# - b, q: 機械Tの製造能力とコスト
# - ok: 二分探索の下限値（達成可能な最大の製造能力）
# - ng: 二分探索の上限値

# 1. io_func関数:
#    - 標準入力から工程数N、予算X、各工程の機械情報APBQを読み込む
#    - 読み込んだ値を返す
# 2. min_cost関数:
#    - 指定された製造能力wを達成するための最小コストを計算
#    - 2つの機械の組み合わせを考慮し、最小コストを求める
# 3. is_ok関数:
#    - 製造能力wが予算内で達成可能かどうかを判定
#    - 各工程のコストを合計し、予算X以下であればTrueを返す
# 4. solve関数:
#    - 二分探索を用いて、予算内で達成可能な最大の製造能力を求める
#    - 二分探索の結果（ok）を出力する
# 5. メイン処理:
#    - io_func関数を呼び出して入力を受け取る
#    - solve関数を呼び出して問題を解く
```
## オブジェクト指向版1
```python:ac_object.py
import sys
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 read_input(self):
        pass

class StandardInputHandler(InputHandler):
    def read_input(self):
        # 標準入力から値を読み込む
        input_func = sys.stdin.readline
        N, X = map(int, input_func().split())
        APBQ = [tuple(map(int, input_func().split())) for _ in range(N)]
        return N, X, APBQ

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

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

class CostCalculator:
    def __init__(self, logger):
        self.logger = logger

    def min_cost(self, w, i, APBQ):
        # 指定された製造能力wを達成するための最小コストを計算する
        a, p, b, q = APBQ[i]
        ret = 10**18  # 最小コストの初期値を大きな値に設定
        
        self.logger.debug(f"製造能力 w={w}, 工程 i={i} の最小コスト計算開始")
        
        # 機械Sの台数を0から100まで変化させる
        for j in range(101):
            rem_task = w - j * a
            k = max(0, -(-rem_task // b))  # 切り上げ除算
            cost = j * p + k * q
            ret = min(ret, cost)
            self.logger.debug(f"機械S: {j}台, 機械T: {k}台, コスト: {cost}")
        
        # 機械Tの台数を0から100まで変化させる
        for k in range(101):
            rem_task = w - k * b
            j = max(0, -(-rem_task // a))  # 切り上げ除算
            cost = j * p + k * q
            ret = min(ret, cost)
            self.logger.debug(f"機械S: {j}台, 機械T: {k}台, コスト: {cost}")
        
        self.logger.debug(f"最小コスト: {ret}")
        return ret

class BudgetChecker:
    def __init__(self, cost_calculator):
        self.cost_calculator = cost_calculator

    def is_ok(self, w, N, X, APBQ):
        # 製造能力wが予算内で達成可能かどうかを判定する
        cost = 0
        for i in range(N):
            cost += self.cost_calculator.min_cost(w, i, APBQ)
        return cost <= X

class ManufacturingCapacityOptimizer:
    def __init__(self, budget_checker, logger):
        self.budget_checker = budget_checker
        self.logger = logger

    def solve(self, N, X, APBQ):
        # 二分探索の範囲を設定
        ok = 0
        ng = 10**9 + 1
        
        self.logger.debug("二分探索開始")
        
        # 二分探索を行う
        while ng - ok > 1:
            mid = (ok + ng) // 2
            self.logger.debug(f"現在の探索範囲: ok={ok}, ng={ng}, mid={mid}")
            if self.budget_checker.is_ok(mid, N, X, APBQ):
                ok = mid
                self.logger.debug(f"mid={mid} は予算内で達成可能")
            else:
                ng = mid
                self.logger.debug(f"mid={mid} は予算内で達成不可能")
        
        self.logger.debug(f"二分探索終了: 最大製造能力 = {ok}")
        return ok

def main(debug_mode=False):
    # ロガーの設定
    logger = setup_logger(debug_mode)
    
    # 入力処理
    input_handler = StandardInputHandler()
    N, X, APBQ = input_handler.read_input()
    
    # 最適化処理
    cost_calculator = CostCalculator(logger)
    budget_checker = BudgetChecker(cost_calculator)
    optimizer = ManufacturingCapacityOptimizer(budget_checker, logger)
    result = optimizer.solve(N, X, APBQ)
    
    # 出力処理
    output_handler = StandardOutputHandler()
    output_handler.output_result(result)

if __name__ == "__main__":
    main(debug_mode=True)  # デバッグモードを有効にする場合はTrueに設定

```

### 解法イメージ

![base_image.create_20250126225432.drawio.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/530912/8ca6a9fc-8a46-84fe-b883-2ebae2c48fd9.png)


### オブジェクト図
![2025年01月26日23時14分_atCoder374E.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/530912/36934311-7e71-962b-2f94-c6ecbe13f3da.png)