問題
既存投稿一覧ページへのリンク
解法手順1
-
入力された文字列Sをリストに変換する。
-
各文字の出現位置をデフォルトディクショナリDに記録する。
-
文字列の長さが3未満の場合は、条件を満たす組み合わせが存在しないため0を出力して終了する。
-
中央の文字の位置iを1からlen(S)-1まで順に固定する。
-
各文字kについて以下の処理を行う：
a. kがS[i]と異なる場合：- 二分探索を用いてi未満の位置の数(pos)と、iより大きい位置の数(len(v)-pos)を求める。
- これらの積を答えに加算する。
b. kがS[i]と同じ場合： - 同様に二分探索を用いるが、中央の文字自身は除外するため、(len(v)-1-pos)を使用する。
-
最終的な答えを出力する。
ACコード1
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
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()
オブジェクト図
