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

# 問題
https://atcoder.jp/contests/abc375/tasks/abc375_d

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


# 解法手順1


1. 入力された文字列Sをリストに変換する。

2. 各文字の出現位置をデフォルトディクショナリDに記録する。

3. 文字列の長さが3未満の場合は、条件を満たす組み合わせが存在しないため0を出力して終了する。

4. 中央の文字の位置iを1からlen(S)-1まで順に固定する。

5. 各文字kについて以下の処理を行う：
   a. kがS[i]と異なる場合：
      - 二分探索を用いてi未満の位置の数(pos)と、iより大きい位置の数(len(v)-pos)を求める。
      - これらの積を答えに加算する。
   b. kがS[i]と同じ場合：
      - 同様に二分探索を用いるが、中央の文字自身は除外するため、(len(v)-1-pos)を使用する。

6. 最終的な答えを出力する。


# ACコード1
```python:ac.py
from collections import defaultdict
import bisect

def io_func():
    # 入力文字列Sをリストに変換
    return list(input())

def solve(S):
    # 各文字の出現位置を記録するデフォルトディクショナリ
    D = defaultdict(list)
    
    # 各文字の出現位置を記録
    for i, s in enumerate(S):
        D[s].append(i)
    
    # 文字列の長さが3未満の場合、0を出力して終了
    if len(S) < 3:
        return 0
    
    ans = 0  # 条件を満たす組み合わせの数
    
    # 中央の文字の位置iを1からlen(S)-1まで順に固定
    for i in range(1, len(S) - 1):
        # 各文字kについて処理
        for k, v in D.items():
            if k != S[i]:
                # kがS[i]と異なる場合
                pos = bisect.bisect_left(v, i)
                ans += pos * (len(v) - pos)
            else:
                # kがS[i]と同じ場合
                pos = bisect.bisect_left(v, i)
                ans += pos * (len(v) - 1 - pos)
    
    return ans

# メイン処理
S = io_func()
result = solve(S)
print(result)

###
# S: 入力された文字列をリストに変換したもの
# D: 各文字の出現位置を記録するデフォルトディクショナリ
# ans: 条件を満たす組み合わせの数
# i: 中央の文字の位置
# k: 現在処理中の文字
# v: 文字kの出現位置のリスト
# pos: 二分探索で求めたiの挿入位置

# 1. io_func関数:
#    - 標準入力から文字列を受け取り、リストに変換して返す
# 2. solve関数:
#    - 文字列Sを受け取り、条件を満たす組み合わせの数を計算する
#    - 各文字の出現位置をデフォルトディクショナリDに記録
#    - 文字列の長さが3未満の場合、0を返す
#    - 中央の文字を固定し、両端の文字の組み合わせを数え上げる
#    - 二分探索を用いて効率的に計算を行う
# 3. メイン処理:
#    - io_func関数で入力を受け取る
#    - solve関数で結果を計算
#    - 結果を出力する
```
## オブジェクト指向版1
```python:ac_object.py
from collections import defaultdict
import bisect
import logging
from abc import ABC, abstractmethod

def setup_logger(debug_mode):
    logger = logging.getLogger(__name__)
    if not logger.handlers:  # ハンドラが存在しない場合のみ追加
        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="utf8")
        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 list(input())

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

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

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

    def analyze(self, S):
        self.logger.debug(f"文字列の解析を開始: {S}")
        
        # 各文字の出現位置を記録するデフォルトディクショナリ
        D = defaultdict(list)
        
        # 各文字の出現位置を記録
        for i, s in enumerate(S):
            D[s].append(i)
        
        self.logger.debug(f"文字の出現位置: {dict(D)}")
        
        # 文字列の長さが3未満の場合、0を出力して終了
        if len(S) < 3:
            self.logger.debug("文字列の長さが3未満のため、0を返します")
            return 0
        
        ans = 0  # 条件を満たす組み合わせの数
        
        # 中央の文字の位置iを1からlen(S)-1まで順に固定
        self.logger.debug(f"中央の文字の位置iを1から{len(S)}-1まで順に固定")
        for i in range(1, len(S) - 1):
            self.logger.debug(f"中央の文字位置: {i}(={S[i]})")
            # 各文字kについて処理
            for k, v in D.items():
                if k != S[i]:
                    # kがS[i]と異なる場合
                    pos = bisect.bisect_left(v, i)
                    ans += pos * (len(v) - pos)
                    self.logger.debug(f"文字 {k} (S[{i}](={S[i]})と異なる): pos={pos}(pos = bisect.bisect_left({v}, {i})), 加算値={pos * (len(v) - pos)}")
                else:
                    # kがS[i]と同じ場合
                    pos = bisect.bisect_left(v, i)
                    ans += pos * (len(v) - 1 - pos)
                    self.logger.debug(f"文字 {k} (S[{i}](={S[i]})と同じ): pos={pos}(bisect.bisect_left({v}, {i})), 加算値={pos * (len(v) - 1 - pos)}")
        
        self.logger.debug(f"最終結果: {ans}")
        return ans

class StringAnalysisApp:
    def __init__(self, input_handler: InputHandler, output_handler: OutputHandler, analyzer: StringAnalyzer):
        self.input_handler = input_handler
        self.output_handler = output_handler
        self.analyzer = analyzer

    def run(self):
        S = self.input_handler.get_input()
        result = self.analyzer.analyze(S)
        self.output_handler.output_result(result)

if __name__ == "__main__":
    debug_mode = True  # デバッグモードを有効にする場合はTrueに設定
    app = StringAnalysisApp(
        StandardInputHandler(),
        StandardOutputHandler(),
        StringAnalyzer(debug_mode)
    )
    app.run()
    

```

### オブジェクト図

![20250129224804_ABC375D.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/530912/959090ed-5caf-a67e-ecce-e03737faf9e2.png)