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

# 問題
https://atcoder.jp/contests/abc141/tasks/abc141_d

## 要約

1. 高橋くんはN個の品物を1個ずつ順番に買う。
2. i番目に買う品物の値段はAi円。
3. 高橋くんはM枚の割引券を持っている。
4. 品物を買う際に割引券を好きな枚数使うことができる。
5. X円の品物を買う際にY枚の割引券を使った場合、その品物をX/(2^Y)円（小数点以下切り捨て）で買うことができる。
 全ての品物を買うために必要な最小金額を求める。

- N: 買う予定の品物の数
- Ai: i番目の品物の値段
- M: 高橋くんが持っている割引券の枚数

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


# アプローチ

1. 品物の価格を最大ヒープを用いて管理する。
2. 割引券を最も高価な品物から順に適用していく。
3. 全ての割引券を使用した後、残った価格の合計を計算する。

# 解法手順

1. 入力から品物の数N、割引券の枚数M、各品物の価格Aiを受け取る。
2. 品物の価格を負の値に変換し、最大ヒープとして扱えるようにする。
3. 変換した価格リストをヒープ化する。
4. M回のループを行い、以下の操作を繰り返す：
   a. ヒープから最大の価格（絶対値が最大）を取り出す。
   b. 取り出した価格を2で割り（小数点以下切り捨て）、新しい価格とする。
   c. 新しい価格を再びヒープに追加する。
5. ループ終了後、ヒープ内の全ての価格の絶対値の合計を計算する。
6. 計算された合計金額を出力する。


# ACコード
```python: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

1. 入力からN（品物の数）とM（割引券の枚数）を受け取る。

2. N個の品物の価格（Ai）をリストとして受け取る。

3. 品物の価格リストを降順にソートする。これにより、最も高価な商品から順に処理できる。

4. M回のループを実行し、以下の操作を行う：
   - リストの最後（最も高価な商品）の価格を取り出す。
   - その価格を2で割る（割引券を1枚使用した効果）。
   - 割引後の価格を再度リストに挿入する。

5. 処理後のリストの合計を計算し、それを最小の支払額として出力する。


# ACコード2
```python: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
```python: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()
```