問題
要約
- 高橋くんはN個の品物を1個ずつ順番に買う。
- i番目に買う品物の値段はAi円。
- 高橋くんはM枚の割引券を持っている。
- 品物を買う際に割引券を好きな枚数使うことができる。
- X円の品物を買う際にY枚の割引券を使った場合、その品物をX/(2^Y)円（小数点以下切り捨て）で買うことができる。
全ての品物を買うために必要な最小金額を求める。
- N: 買う予定の品物の数
- Ai: i番目の品物の値段
- M: 高橋くんが持っている割引券の枚数
既存投稿一覧ページへのリンク
アプローチ
- 品物の価格を最大ヒープを用いて管理する。
- 割引券を最も高価な品物から順に適用していく。
- 全ての割引券を使用した後、残った価格の合計を計算する。
解法手順
- 入力から品物の数N、割引券の枚数M、各品物の価格Aiを受け取る。
- 品物の価格を負の値に変換し、最大ヒープとして扱えるようにする。
- 変換した価格リストをヒープ化する。
- M回のループを行い、以下の操作を繰り返す：
a. ヒープから最大の価格（絶対値が最大）を取り出す。
b. 取り出した価格を2で割り（小数点以下切り捨て）、新しい価格とする。
c. 新しい価格を再びヒープに追加する。 - ループ終了後、ヒープ内の全ての価格の絶対値の合計を計算する。
- 計算された合計金額を出力する。
ACコード
ac.py
import heapq # heapqモジュールをインポート
def io_func():
# 入力を受け取る関数
n, m = map(int, input().split()) # 品物の数Nと割引券の枚数Mを受け取る
prices = list(map(int, input().split())) # 各品物の価格Aiを受け取る
return n, m, prices
def solve(n, m, prices):
# 主な処理を行う関数
# 価格を負の値に変換し、最大ヒープとして扱えるようにする
# heapq.heappop(negative_prices)で取得するの最小値のため
negative_prices = [-price for price in prices]
# 変換した価格リストをヒープ化する
heapq.heapify(negative_prices)
# M回のループを行い、割引を適用する
for _ in range(m):
# ヒープから最大の価格（絶対値が最大）を取り出す
max_price = heapq.heappop(negative_prices)
# 取り出した価格を2で割り（小数点以下切り捨て）、新しい価格とする
discounted_price = -(-max_price // 2)
# 新しい価格を再びヒープに追加する
heapq.heappush(negative_prices, discounted_price)
# ヒープ内の全ての価格の絶対値の合計を計算する
total_price = -sum(negative_prices)
return total_price
if __name__=="__main__":
# メイン処理
n, m, prices = io_func() # 入力を受け取る
result = solve(n, m, prices) # 解を計算する
print(result) # 結果を出力する
###
# n: 品物の数
# m: 割引券の枚数
# prices: 各品物の価格リスト
# negative_prices: 価格を負の値に変換したリスト（最大ヒープとして使用）
# max_price: ヒープから取り出した最大価格（負の値）
# discounted_price: 割引後の価格（負の値）
# total_price: 最終的な合計金額
# 1. io_func関数:
# - 標準入力から品物の数、割引券の枚数、各品物の価格を読み取る
# - 読み取った値を返す
# 2. solve関数:
# - 入力された価格リストを負の値に変換し、最大ヒープを作成
# - 割引券の枚数分だけ以下の操作を繰り返す:
# a. ヒープから最大価格を取り出す
# b. 取り出した価格を半額にする（小数点以下切り捨て）
# c. 割引後の価格をヒープに戻す
# - 最終的なヒープ内の価格の合計（絶対値）を計算して返す
# 3. メイン処理:
# - io_func関数を呼び出して入力を受け取る
# - solve関数を呼び出して解を計算する
# - 計算結果を出力する
解法手順2
-
入力からN（品物の数）とM（割引券の枚数）を受け取る。
-
N個の品物の価格（Ai）をリストとして受け取る。
-
品物の価格リストを降順にソートする。これにより、最も高価な商品から順に処理できる。
-
M回のループを実行し、以下の操作を行う：
- リストの最後（最も高価な商品）の価格を取り出す。
- その価格を2で割る（割引券を1枚使用した効果）。
- 割引後の価格を再度リストに挿入する。
-
処理後のリストの合計を計算し、それを最小の支払額として出力する。
ACコード2
ac.py
from sortedcontainers import SortedList # ソート済みリストを使用するためのインポート
def io_func():
# 入力を受け取る関数
n, m = map(int, input().split()) # N（品物の数）とM（割引券の枚数）を受け取る
prices = list(map(int, input().split())) # N個の品物の価格をリストとして受け取る
return n, m, prices
def solve(n, m, prices):
# メインの処理を行う関数
sorted_prices = SortedList(prices) # 価格リストをSortedListに変換
for _ in range(m): # M回のループを実行
highest_price = sorted_prices[-1] # 最も高価な商品の価格を取得
sorted_prices.pop() # 最も高価な商品をリストから削除
discounted_price = highest_price // 2 # 価格を2で割る（割引券を使用）
sorted_prices.add(discounted_price) # 割引後の価格をリストに追加
return sum(sorted_prices) # 処理後のリストの合計を返す
def main():
# メイン関数
n, m, prices = io_func() # 入力を受け取る
result = solve(n, m, prices) # 問題を解く
print(result) # 結果を出力
if __name__ == "__main__":
main()
###
# n: 品物の数
# m: 割引券の枚数
# prices: 品物の価格リスト
# sorted_prices: ソートされた価格リスト（SortedList）
# highest_price: 現在の最高価格
# discounted_price: 割引後の価格
# result: 最終的な支払額の合計
# 1. io_func関数:
# - 標準入力から品物の数、割引券の枚数、各品物の価格を読み取る
# - 読み取ったデータを返す
# 2. solve関数:
# - 入力された価格リストをSortedListに変換
# - 割引券の枚数分だけ以下の処理を繰り返す:
# a. 最も高価な商品の価格を取得
# b. その価格を2で割って割引後の価格を計算
# c. 割引後の価格をSortedListに追加
# - 最終的なSortedListの合計を計算して返す
# 3. main関数:
# - io_func関数を呼び出して入力データを取得
# - solve関数を呼び出して問題を解く
# - 結果を出力
オブジェクト指向版2
ac.py
from abc import ABC, abstractmethod
from sortedcontainers import SortedList
from typing import List
# 単一責任の原則 (SRP): 各クラスは単一の責任を持つ
class InputReader(ABC):
"""入力を読み取るための抽象基底クラス"""
@abstractmethod
def read_input(self) -> tuple:
"""入力を読み取り、タプルとして返す"""
pass
class ConsoleInputReader(InputReader):
"""コンソールから入力を読み取るクラス"""
def read_input(self) -> tuple:
# 品物の数と割引券の枚数を読み取る
n, m = map(int, input().split())
# 品物の価格リストを読み取る
prices = list(map(int, input().split()))
return n, m, prices
class PriceSorter:
"""価格をソートするクラス"""
def sort_prices(self, prices: List[int]) -> SortedList:
"""価格リストをソートしてSortedListとして返す"""
return SortedList(prices)
class DiscountApplier:
"""割引を適用するクラス"""
def apply_discount(self, price: int) -> int:
"""価格に50%の割引を適用"""
return price // 2
class ShoppingOptimizer:
"""買い物を最適化するクラス"""
def __init__(self, price_sorter: PriceSorter, discount_applier: DiscountApplier):
self.price_sorter = price_sorter
self.discount_applier = discount_applier
def optimize(self, n: int, m: int, prices: List[int]) -> int:
"""買い物を最適化し、最小の総支払額を計算"""
sorted_prices = self.price_sorter.sort_prices(prices)
for _ in range(m): # 割引券の枚数分ループ
highest_price = sorted_prices[-1] # 最高価格を取得
sorted_prices.pop() # 最高価格を削除
discounted_price = self.discount_applier.apply_discount(highest_price) # 割引を適用
sorted_prices.add(discounted_price) # 割引後の価格を追加
return sum(sorted_prices) # 総支払額を計算
class ShoppingApp:
"""アプリケーションのメインクラス"""
def __init__(self, input_reader: InputReader, optimizer: ShoppingOptimizer):
self.input_reader = input_reader
self.optimizer = optimizer
def run(self):
"""アプリケーションを実行"""
# 入力を読み取る
n, m, prices = self.input_reader.read_input()
# 最適化を実行
result = self.optimizer.optimize(n, m, prices)
# 結果を出力
print(result)
# 依存性注入の原則 (DIP): 高レベルのモジュールは低レベルのモジュールに依存しない
if __name__ == "__main__":
input_reader = ConsoleInputReader()
price_sorter = PriceSorter()
discount_applier = DiscountApplier()
optimizer = ShoppingOptimizer(price_sorter, discount_applier)
app = ShoppingApp(input_reader, optimizer)
app.run()