問題
既存投稿一覧ページへのリンク
解法手順1
-
入力を受け取る：
- x, y, z（各キー操作にかかる時間）
- 目標の文字列 S
-
DPテーブルを初期化する：
- dp[i][j] : i文字目まで入力し、CapsLockの状態がjの時の最小時間
- j=0はCapsLock OFF、j=1はCapsLock ON
- 初期状態はdp[0][0] = 0, dp[0][1] = INF（非常に大きな値）
-
文字列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）
- 'A'の場合：
-
各状態で最小の時間を計算し、DPテーブルを更新する
-
最終的な答えは、dp[len(S)][0]とdp[len(S)][1]の小さい方
-
結果を出力する
ACコード1
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
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()
オブジェクト図
オブジェクト指向版1で書くメリット
拡張性と再利用性
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クラスのテストは以下のように書けます：
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()