LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@o_chan_t(おー ちゃん)

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

Posted at

問題

要約

  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番目の宝箱の番号

既存投稿一覧ページへのリンク

一覧ページ

解法手順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

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

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で書くメリット

拡張性と再利用性

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()

テスト容易性

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)
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?