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

# 問題
https://atcoder.jp/contests/abc264/tasks/abc264_d

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


# 解法手順1

1. "atcoder" の各文字とその位置をディクショナリに記録する。
2. 入力された文字列 S をリストに変換する。
3. "atcoder" の各文字について以下を行う：
   - S 内でその文字の現在位置を見つける。
   - 現在位置が正しい位置と異なる場合：
     - 現在位置が正しい位置より後ろにある場合は、前に移動させる。
     - 現在位置が正しい位置より前にある場合は、後ろに移動させる。
   - 移動の際は隣接する文字と交換し、交換回数を数える。
4. 全ての交換回数の合計を出力する。


# ACコード1
```python: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
```python: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()
```

### オブジェクト図

![2025年01月23日20時15分_atcoder264D2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/530912/4d6e576f-bf76-a78d-8b26-73821c3e6afc.png)