問題
既存投稿一覧ページへのリンク
解法手順1
- "atcoder" の各文字とその位置をディクショナリに記録する。
- 入力された文字列 S をリストに変換する。
- "atcoder" の各文字について以下を行う：
- S 内でその文字の現在位置を見つける。
- 現在位置が正しい位置と異なる場合：
- 現在位置が正しい位置より後ろにある場合は、前に移動させる。
- 現在位置が正しい位置より前にある場合は、後ろに移動させる。
- 移動の際は隣接する文字と交換し、交換回数を数える。
- 全ての交換回数の合計を出力する。
ACコード1
ac.py
from collections import Counter
def io_func():
# 入力文字列を受け取る
return input()
def solve(S):
# 'atcoder'の各文字の正しい位置を記録
np = Counter()
s = 'atcoder'
for i, char in enumerate(s):
np[char] = i
# 入力文字列をリストに変換
S = list(S)
ans = 0 # 交換回数を記録する変数
# 'atcoder'の各文字について処理を行う
for char in np:
t = S.index(char) # 現在の文字位置
if t == np[char]:
continue # 正しい位置にある場合はスキップ
elif t > np[char]:
# 現在位置が正しい位置より後ろにある場合
while t != np[char]:
S[t], S[t-1] = S[t-1], S[t] # 隣接する文字と交換
t -= 1
ans += 1
else:
# 現在位置が正しい位置より前にある場合
while t != np[char]:
S[t], S[t+1] = S[t+1], S[t] # 隣接する文字と交換
t += 1
ans += 1
return ans
# メイン処理
S = io_func()
result = solve(S)
print(result)
###
# np: 'atcoder'の各文字の正しい位置を記録するCounter
# S: 入力文字列をリストに変換したもの
# ans: 文字の交換回数
# t: 処理中の文字の現在位置
# 1. 入力関数io_funcで文字列Sを受け取る
# 2. solve関数で以下の処理を行う:
# a. 'atcoder'の各文字の正しい位置をnpに記録
# b. 入力文字列Sをリストに変換
# c. 'atcoder'の各文字について:
# - 現在位置tを見つける
# - 正しい位置と異なる場合、隣接文字との交換を繰り返し正しい位置に移動
# - 交換回数をansに加算
# 3. 最終的な交換回数ansを返し、出力する
オブジェクト指向版1
ac_object.py
import logging
from collections import Counter
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 StandardInputHandler(InputHandler):
def get_input(self):
return input()
class OutputHandler(ABC):
@abstractmethod
def output_result(self, result):
pass
class StandardOutputHandler(OutputHandler):
def output_result(self, result):
print(result)
class AtcoderSolver:
def __init__(self, debug_mode=False):
self.logger = setup_logger(debug_mode)
self.np = Counter()
self._initialize_np()
def _initialize_np(self):
# 'atcoder'の各文字の正しい位置を記録
s = 'atcoder'
for i, char in enumerate(s):
self.np[char] = i
def solve(self, S):
self.logger.debug(f"入力文字列: {S}")
S = list(S)
ans = 0 # 交換回数を記録する変数
# 'atcoder'の各文字について処理を行う
for char in self.np:
t = S.index(char) # 現在の文字位置
self.logger.debug(f"処理中の文字: {char}, 現在位置: {t}, 正しい位置: {self.np[char]}")
if t == self.np[char]:
self.logger.debug(f"{char}は正しい位置にあるためスキップ")
continue # 正しい位置にある場合はスキップ
elif t > self.np[char]:
# 現在位置が正しい位置より後ろにある場合
while t != self.np[char]:
S[t], S[t-1] = S[t-1], S[t] # 隣接する文字と交換
t -= 1
ans += 1
self.logger.debug(f"{char}を左に移動: 現在位置 {t+1} -> {t}")
self.logger.debug(f"現在の文字列: {S}")
else:
# 現在位置が正しい位置より前にある場合
while t != self.np[char]:
S[t], S[t+1] = S[t+1], S[t] # 隣接する文字と交換
t += 1
ans += 1
self.logger.debug(f"{char}を右に移動: 現在位置 {t-1} -> {t}")
self.logger.debug(f"現在の文字列: {S}")
self.logger.debug(f"最終的な交換回数: {ans}")
return ans
class AtcoderProgram:
def __init__(self, input_handler: InputHandler, output_handler: OutputHandler, solver: AtcoderSolver):
self.input_handler = input_handler
self.output_handler = output_handler
self.solver = solver
def run(self):
S = self.input_handler.get_input()
result = self.solver.solve(S)
self.output_handler.output_result(result)
if __name__ == "__main__":
debug_mode = True # デバッグモードを有効にする場合はTrueに設定
input_handler = StandardInputHandler()
output_handler = StandardOutputHandler()
solver = AtcoderSolver(debug_mode)
program = AtcoderProgram(input_handler, output_handler, solver)
program.run()
オブジェクト図
