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

# 問題
https://atcoder.jp/contests/abc303/tasks/abc303_d

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


# 解法手順1
1. 入力を受け取る：
   - x, y, z（各キー操作にかかる時間）
   - 目標の文字列 S

2. DPテーブルを初期化する：
   - dp[i][j] : i文字目まで入力し、CapsLockの状態がjの時の最小時間
   - j=0はCapsLock OFF、j=1はCapsLock ON
   - 初期状態はdp[0][0] = 0, dp[0][1] = INF（非常に大きな値）

3. 文字列Sの各文字について以下の処理を行う：
   - 'A'の場合：
     - CapsLock OFFの場合：Shiftキー+aキー（y）またはCapsLock切り替え+aキー（z+x）
     - CapsLock ONの場合：aキー（x）またはCapsLock切り替え+Shiftキー+aキー（z+y）
   - 'a'の場合：
     - CapsLock OFFの場合：aキー（x）またはCapsLock切り替え+Shiftキー+aキー（z+y）
     - CapsLock ONの場合：Shiftキー+aキー（y）またはCapsLock切り替え+aキー（z+x）

4. 各状態で最小の時間を計算し、DPテーブルを更新する

5. 最終的な答えは、dp[len(S)][0]とdp[len(S)][1]の小さい方

6. 結果を出力する


# ACコード1
```python:ac.py
def io_func():
    # 入力を受け取る
    x, y, z = map(int, input().split())  # x, y, zを入力から取得
    s = input()  # 目標の文字列Sを入力から取得
    return x, y, z, s

def solve(x, y, z, s):
    INF = 1 << 60  # 非常に大きな値を設定
    
    # DPテーブルを初期化
    dp = [[INF, INF] for _ in range(len(s) + 1)]  # dp[i][j]: i文字目まで入力し、CapsLockの状態がjの時の最小時間
    dp[0][0], dp[0][1] = 0, INF  # 初期状態を設定
    
    # 文字列Sの各文字について処理を行う
    for i in range(len(s)):
        s_tmp = s[i]  # 現在の文字
        if s_tmp == 'A':
            # 大文字'A'の場合
            dp[i + 1][0] = min(dp[i + 1][0], dp[i][0] + y, dp[i][1] + z + y)  # CapsLock OFFの場合
            dp[i + 1][1] = min(dp[i + 1][1], dp[i][1] + x, dp[i][0] + z + x)  # CapsLock ONの場合
        else:
            # 小文字'a'の場合
            dp[i + 1][0] = min(dp[i + 1][0], dp[i][0] + x, dp[i][1] + z + x)  # CapsLock OFFの場合
            dp[i + 1][1] = min(dp[i + 1][1], dp[i][1] + y, dp[i][0] + z + y)  # CapsLock ONの場合
    
    # 最終的な答えを計算
    ans = min(dp[-1][0], dp[-1][1])  # dp[len(S)][0]とdp[len(S)][1]の小さい方
    return ans

# メイン処理
x, y, z, s = io_func()  # 入力を受け取る
result = solve(x, y, z, s)  # 問題を解く
print(result)  # 結果を出力

###
# 変数の意味:
# x: 通常のキー入力にかかる時間
# y: Shiftキーを使用した入力にかかる時間
# z: CapsLockの切り替えにかかる時間
# s: 入力目標の文字列
# INF: 非常に大きな値（初期化用）
# dp: 動的計画法のテーブル
# ans: 最終的な答え（最短時間）

# 1. io_func関数: 標準入力から必要なデータを読み込む
# 2. solve関数: 動的計画法を用いて最短時間を計算する
#    - DPテーブルを初期化
#    - 文字列の各文字に対して、CapsLockのON/OFFそれぞれの状態での最小時間を計算
#    - 最終的な最小時間を返す
# 3. メイン処理: 入力を受け取り、solve関数を呼び出し、結果を出力する

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

def setup_logger(debug_mode):
    logger = logging.getLogger(__name__)
    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='utf-8')
    file_handler.setFormatter(formatter)
    logger.addHandler(file_handler)
    
    return logger

class InputHandler(ABC):
    @abstractmethod
    def get_input(self):
        pass

class OutputHandler(ABC):
    @abstractmethod
    def output_result(self, result):
        pass

class StandardInputHandler(InputHandler):
    def get_input(self):
        x, y, z = map(int, input().split())
        s = input()
        return x, y, z, s

class StandardOutputHandler(OutputHandler):
    def output_result(self, result):
        print(result)

class Solver:
    def __init__(self, debug_mode=False):
        self.logger = setup_logger(debug_mode)

    def solve(self, x, y, z, s):
        self.logger.debug(f"開始: x={x}, y={y}, z={z}, s={s}")
        INF = 1 << 60
        
        dp = [[INF, INF] for _ in range(len(s) + 1)]
        dp[0][0], dp[0][1] = 0, INF
        
        for i in range(len(s)):
            s_tmp = s[i]
            self.logger.debug(f"処理中の文字: {s_tmp}")
            if s_tmp == 'A':
                self.logger.debug(f"dp[{i + 1}][0] = min(dp[{i + 1}][0](={dp[i + 1][0]}), dp[{i}][0](={dp[i][0]}) + y(={y}), dp[{i}][1](={dp[i][1]}) + z(={z}) + y(={y}))")
                dp[i + 1][0] = min(dp[i + 1][0], dp[i][0] + y, dp[i][1] + z + y)
                self.logger.debug(f"dp[{i + 1}][1] = min(dp[{i + 1}][1](={dp[i + 1][1]}), dp[{i}][1](={dp[i][1]}) + x(={x}), dp[i][1](={dp[i][0]}) + z(={z}) + x(={x}))")
                dp[i + 1][1] = min(dp[i + 1][1], dp[i][1] + x, dp[i][0] + z + x)
            else:
                self.logger.debug(f"dp[{i + 1}][0] = min(dp[{i + 1}][0](={dp[i + 1][0]}), dp[{i}][0](={dp[i][0]}) + x(={x}), dp[{i}][1](={dp[i][1]}) + z(={z}) + x(={x}))")
                dp[i + 1][0] = min(dp[i + 1][0], dp[i][0] + x, dp[i][1] + z + x)
                self.logger.debug(f"dp[{i + 1}][1] = min(dp[{i + 1}][1](={dp[i + 1][1]}), dp[{i}][1](={dp[i][1]}) + y(={y}), dp[{i}][0](={dp[i][0]}) + z(={z}) + y(={y}))")
                dp[i + 1][1] = min(dp[i + 1][1], dp[i][1] + y, dp[i][0] + z + y)
            self.logger.debug(f"DP状態: {dp[i+1]}")
        
        ans = min(dp[-1][0], dp[-1][1])
        self.logger.debug(f"最終結果: {ans}")
        return ans

class TypewriterSimulator:
    def __init__(self, input_handler: InputHandler, output_handler: OutputHandler, solver: Solver):
        self.input_handler = input_handler
        self.output_handler = output_handler
        self.solver = solver

    def run(self):
        x, y, z, s = self.input_handler.get_input()
        result = self.solver.solve(x, y, z, s)
        self.output_handler.output_result(result)

if __name__ == "__main__":
    input_handler = StandardInputHandler()
    output_handler = StandardOutputHandler()
    solver = Solver(debug_mode=True)  # デバッグモードをTrueに設定
    simulator = TypewriterSimulator(input_handler, output_handler, solver)
    simulator.run()
```

### オブジェクト図
![2025年01月21日19時57分_abc303d.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/530912/cfb9d50d-7639-55a0-6972-47971dd4c0e3.png)

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

    def get_input(self):
        with open(self.filename, 'r') as f:
            x, y, z = map(int, f.readline().split())
            s = f.readline().strip()
        return x, y, z, s

class FileOutputHandler(OutputHandler):
    def __init__(self, filename):
        self.filename = filename

    def output_result(self, result):
        with open(self.filename, 'w') as f:
            f.write(str(result))

# 使用例
input_handler = FileInputHandler('input.txt')
output_handler = FileOutputHandler('output.txt')
solver = Solver(debug_mode=True)
simulator = TypewriterSimulator(input_handler, output_handler, solver)
simulator.run()

```

#### テスト容易性
各クラスが単一の責任を持つため、ユニットテストが容易になります。例えば、Solverクラスのテストは以下のように書けます：

```python
import unittest

class TestSolver(unittest.TestCase):
    def setUp(self):
        self.solver = Solver(debug_mode=True)

    def test_solve_simple_case(self):
        result = self.solver.solve(7, 6, 4, 'AaAAAaa')
        self.assertEqual(result, 45)

if __name__ == '__main__':
    unittest.main()

```