問題
入力例01
解答
既存投稿一覧ページへのリンク
解法手順1
-
入力を受け取る。N（工程数）とX（予算）、各工程の機械の情報（Ai, Pi, Bi, Qi）を読み込む。
-
二分探索の範囲を設定する。初期値として、okを0、ngを10^9 + 1とする。
-
二分探索を行う。
- 中間値midを計算する。
- is_ok関数を用いて、製造能力midが予算内で達成可能かどうかを判定する。
- 可能な場合はokをmidに更新し、不可能な場合はngをmidに更新する。
- ng - okが1より大きい間、この処理を繰り返す。
-
is_ok関数の実装:
- 各工程に対して、min_cost関数を呼び出し、必要なコストを計算する。
- 全工程のコストの合計が予算X以下であれば、Trueを返す。
-
min_cost関数の実装:
- 2つの機械の組み合わせを考慮し、指定された製造能力wを達成するための最小コストを計算する。
- 機械Sの台数を0から100まで変化させ、必要な機械Tの台数を計算する。
- 同様に、機械Tの台数を0から100まで変化させ、必要な機械Sの台数を計算する。
- すべての組み合わせの中で最小のコストを返す。
-
二分探索が終了したら、okの値（達成可能な最大の製造能力）を出力する。
ACコード1
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
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に設定
解法イメージ
オブジェクト図
