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

# 問題
https://atcoder.jp/contests/abc142/tasks/abc142_e

## 要約
1. N個の宝箱があり、それぞれに1からNまでの番号がついている。

2. M個の鍵が店で売られており、各鍵iについて以下の情報が与えられる
   - 価格: ai円
   - 開けられる宝箱の数: bi
   - 開けられる宝箱の番号: ci1, ci2, ..., cibi

3. 購入した鍵は何度でも使用可能である。

4. 全ての宝箱を開けるために必要な最小費用を求める。

5. 全ての宝箱を開けることが不可能な場合は、-1を出力する。

- N: 宝箱の総数
- M: 売られている鍵の数
- ai: i番目の鍵の価格
- bi: i番目の鍵で開けられる宝箱の数
- cij: i番目の鍵で開けられるj番目の宝箱の番号


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


# 解法手順1

## 解法アプローチ

1. ビット演算を用いて宝箱の開閉状態を表現する。
2. 動的計画法（DP）を使用して、各状態における最小費用を計算する。
3. 全ての宝箱を開けた状態の最小費用を求め、それが存在しない場合は-1を出力する。

## 具体的手順

1. 入力を受け取り、各鍵の情報を処理する。
2. 各鍵が開けられる宝箱の組み合わせをビット表現で表す。
3. DPテーブルを初期化する。dp[i][j]は、i番目までの鍵を使用して、宝箱の開閉状態がjの時の最小費用を表す。
4. 各鍵について、以下の2つの選択肢を考慮しながらDPテーブルを更新する：
   - 鍵を購入しない場合
   - 鍵を購入する場合
5. 全ての鍵を考慮した後、全ての宝箱が開いた状態（2^N - 1）の最小費用を確認する。
6. 最小費用が無限大でない場合はその値を、無限大の場合は-1を出力する。


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

def io_func():
    # 標準入力から宝箱の数Nと鍵の数Mを読み取る
    N, M = map(int, input().split())
    
    # 各鍵の情報を格納するリスト
    keys = []
    for _ in range(M):
        # 鍵の価格と開けられる宝箱の数を読み取る
        a, b = map(int, input().split())
        # 開けられる宝箱の番号を読み取る
        c = list(map(int, input().split()))
        # 宝箱の開閉状態をビット表現で表す
        box_state = sum(1 << (i - 1) for i in c)
        keys.append((a, box_state))
    
    return N, M, keys

def solve(N, M, keys):
    # DPテーブルを初期化する
    dp = [[float('inf')] * (1 << N) for _ in range(M + 1)]
    dp[0][0] = 0  # 初期状態（何も開いていない状態）のコストは0

    # 各鍵について処理を行う
    for i in range(M):
        price, can_open = keys[i]
        for j in range(1 << N):
            # 鍵を購入しない場合
            dp[i + 1][j] = min(dp[i][j], dp[i + 1][j])
            # 鍵を購入する場合
            dp[i + 1][j | can_open] = min(dp[i + 1][j | can_open], dp[i][j] + price)

    # 全ての宝箱が開いた状態の最小費用を取得
    min_cost = dp[-1][-1]
    
    # 結果を出力
    return min_cost if min_cost != float('inf') else -1

def main():
    N, M, keys = io_func()
    result = solve(N, M, keys)
    print(result)

if __name__ == "__main__":
    main()

###
# N: 宝箱の数
# M: 鍵の数
# keys: 各鍵の情報（価格と開けられる宝箱の状態）を格納したリスト
# dp: 動的計画法のテーブル。dp[i][j]はi番目までの鍵を使用して、宝箱の開閉状態がjの時の最小費用

# 1. io_func関数:
#    - 標準入力から宝箱の数N、鍵の数M、各鍵の情報を読み取る
#    - 各鍵が開けられる宝箱の組み合わせをビット表現で表す
#    - N, M, keysを返す
# 2. solve関数:
#    - DPテーブルを初期化する
#    - 各鍵について、鍵を購入する場合と購入しない場合の両方を考慮してDPテーブルを更新する
#    - 全ての宝箱が開いた状態の最小費用を計算し、結果を返す
# 3. main関数:
#    - io_func関数を呼び出して入力を処理する
#    - solve関数を呼び出して結果を計算する
#    - 結果を出力する

```
## オブジェクト指向版1
```python:ac_object.py
import sys
import logging
from abc import ABC, abstractmethod

# ロガーの設定
logger = logging.getLogger(__name__)
logger.setLevel(logging.DEBUG)
file_handler = logging.FileHandler('treasure_box_solver.log')
file_handler.setLevel(logging.DEBUG)
formatter = logging.Formatter('%(asctime)s - %(name)s - %(levelname)s - %(message)s')
file_handler.setFormatter(formatter)
logger.addHandler(file_handler)

class InputReader(ABC):
    @abstractmethod
    def read_input(self):
        pass

class ConsoleInputReader(InputReader):
    def read_input(self):
        # 標準入力から宝箱の数Nと鍵の数Mを読み取る
        N, M = map(int, input().split())
        
        # 各鍵の情報を格納するリスト
        keys = []
        for _ in range(M):
            # 鍵の価格と開けられる宝箱の数を読み取る
            a, b = map(int, input().split())
            # 開けられる宝箱の番号を読み取る
            c = list(map(int, input().split()))
            # 宝箱の開閉状態をビット表現で表す
            box_state = sum(1 << (i - 1) for i in c)
            keys.append((a, box_state))
        
        return N, M, keys

class TreasureBoxSolver:
    def __init__(self, debug=False):
        self.debug = debug

    def solve(self, N, M, keys):
        if self.debug:
            logger.debug("ソルバーの実行を開始します")

        # DPテーブルを初期化する
        dp = [[float('inf')] * (1 << N) for _ in range(M + 1)]
        dp[0][0] = 0  # 初期状態（何も開いていない状態）のコストは0
        if self.debug: logger.debug(f"DPの状態:{dp}")

        # 各鍵について処理を行う
        for i in range(M):
            price, can_open = keys[i]
            if self.debug: logger.debug(f"{i+1}番目の鍵を使います。(値段: {price}, 開けられる宝箱{str(bin(can_open)[2:]).zfill(N)})")
            for j in range(1 << N):
                # 鍵を購入しない場合
                dp[i + 1][j] = min(dp[i][j], dp[i + 1][j])
                if self.debug: logger.debug(f"鍵を購入しない場合: dp[{i + 1}][{str(bin(j)[2:]).zfill(N)}] = min(dp[{i}][{str(bin(j)[2:]).zfill(N)}], dp[{i + 1}][{str(bin(j)[2:]).zfill(N)}])")
                # 鍵を購入する場合
                dp[i + 1][j | can_open] = min(dp[i + 1][j | can_open], dp[i][j] + price)
                if self.debug: logger.debug(f"鍵を購入する場合: (dp[{i + 1}][{str(bin(j)[2:]).zfill(N)} | {str(bin(can_open)[2:]).zfill(N)}] = min(dp[{i + 1}][{str(bin(j)[2:]).zfill(N)} | {str(bin(can_open)[2:]).zfill(N)}], dp[{i}][{str(bin(j)[2:]).zfill(N)}] + price)")

            if self.debug:
                logger.debug(f"鍵{i+1}の処理が完了しました")

        # 全ての宝箱が開いた状態の最小費用を取得
        min_cost = dp[-1][-1]
        if self.debug: logger.debug(f"DPの最終状態:{dp}")
        
        # 結果を出力
        result = min_cost if min_cost != float('inf') else -1

        if self.debug:
            logger.debug(f"ソルバーの実行が完了しました。結果: {result}")

        return result

class TreasureBoxApp:
    def __init__(self, input_reader, solver):
        self.input_reader = input_reader
        self.solver = solver

    def run(self):
        N, M, keys = self.input_reader.read_input()
        result = self.solver.solve(N, M, keys)
        print(result)

def main():
    input_reader = ConsoleInputReader()
    solver = TreasureBoxSolver(debug=False)
    app = TreasureBoxApp(input_reader, solver)
    app.run()

if __name__ == "__main__":
    main()
```

### オブジェクト指向版1で書くメリット
#### 拡張性と再利用性
```python:ac_object.py
class FileInputReader(InputReader):
   def __init__(self, filename):
       self.filename = filename

   def read_input(self):
       with open(self.filename, 'r') as f:
           N, M = map(int, f.readline().split())
           keys = []
           for _ in range(M):
               a, b = map(int, f.readline().split())
               c = list(map(int, f.readline().split()))
               box_state = sum(1 << (i - 1) for i in c)
               keys.append((a, box_state))
       return N, M, keys

def main():
   input_reader = FileInputReader('input.txt')
   solver = TreasureBoxSolver(debug=True)
   app = TreasureBoxApp(input_reader, solver)
   app.run()
```

#### テスト容易性
```python:ac_object.py
import unittest

class TestTreasureBoxSolver(unittest.TestCase):
   def setUp(self):
       self.solver = TreasureBoxSolver(True)

   def test_solve_simple_case(self):
       N, M = 3, 2
       keys = [(10, 1), (15, 6)]
       result = self.solver.solve(N, M, keys)
       self.assertEqual(result, 25)

   def test_solve_impossible_case(self):
       N, M = 3, 2
       keys = [(10, 1), (15, 2)]
       result = self.solver.solve(N, M, keys)
       self.assertEqual(result, -1)

   def test_solve_complex_case(self):
       N, M = 5, 3
       keys = [(50, 31), (30, 3), (40, 28)]
       result = self.solver.solve(N, M, keys)
       self.assertEqual(result, 50)

```