BFSを用いた文字列の置換生成プログラム(AtCoder361D問題の準備)

Atcoder360のC/D/Eを解いて、少し調子に乗っていたことを反省。
まだまだ競技プログラミングの選手の中では下層にいることを認識したうえで、AtCoder361に挑戦

ひとまず、直接問題を解きに掛かる前に、前提知識を整理してから望むことにしました。

問題

既存投稿一覧ページへのリンク

一覧ページ

BFSを用いた文字列の置換生成プログラム

sample.py

from collections import deque
import logging

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)
    
    logger.debug("ロガーのセットアップが完了しました。デバッグモード: %s", debug_mode)
    return logger

def generate_permutations(s, logger):
    logger.info(f"入力文字列 '{s}' の置換生成を開始します")
    queue = deque([s])
    seen = set([s])
    result = []

    logger.debug("初期化: queue=%s, seen=%s, result=%s", queue, seen, result)

    while queue:
        current = queue.popleft()
        result.append(current)
        logger.debug(f"処理中の文字列: {current}")
        logger.debug("現在の状態: queue=%s, seen=%s, result=%s", queue, seen, result)

        logger.debug(f"文字列 '{current}' の処理を開始します")
        for i in range(len(current)):
            if current[i] != '.':
                logger.debug(f"'.'以外の文字 '{current[i]}' を処理中 (位置: {i})")
                for j in range(i+1, len(current)):
                    logger.debug(f"内部ループ開始: '{current[i]}' の後ろにある '.' を探索します")
                    if current[j] == '.':
                        logger.debug(f"'.' を発見 (位置: {j})")
                        logger.debug(f"文字列を入れ替える前: {current}")
                        new_string = list(current)
                        logger.debug(f"入れ替える文字: '{new_string[i]}' (位置: {i}) と '{new_string[j]}' (位置: {j})")
                        new_string[i], new_string[j] = new_string[j], new_string[i]
                        new_string = ''.join(new_string)
                        logger.debug(f"リストを文字列に戻した結果: {new_string}")
                        
                        if new_string not in seen:
                            queue.append(new_string)
                            seen.add(new_string)
                            logger.debug(f"新しい置換をキューに追加: {new_string}, 巡回済み{seen}")
                        else:
                            logger.debug(f"重複した置換をスキップ: {new_string}, 巡回済み{seen}")

    logger.info(f"置換生成が完了しました。総置換数: {len(result)}")
    logger.debug("最終結果: %s", result)
    return result

# テスト
debug_mode = True  # デバッグモードを有効にする場合はTrueに設定
logger = setup_logger(debug_mode)

input_string = "ABAB."
logger.info(f"入力文字列: {input_string}")

permutations = generate_permutations(input_string, logger)
logger.info("生成された置換:")
for perm in permutations:
    logger.info(perm)
    print(perm)  # コンソールにも出力

logger.info("プログラムの実行が完了しました。")
logger.debug("プログラムの実行状態: input_string=%s, permutations=%s", input_string, permutations)

BFSを用いた文字列の置換生成プログラム(連続した..との置換)

sample.py

import logging
from collections import deque

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)
    
    logger.debug("ロガーのセットアップが完了しました。デバッグモード: %s", debug_mode)
    return logger

def generate_permutations(s, logger):
    logger.info("文字列 '%s' の置換生成を開始します", s)
    queue = deque([s])
    seen = set([s])
    result = [s]

    logger.debug("初期状態: queue=%s, seen=%s, result=%s", queue, seen, result)

    while queue:
        current = queue.popleft()
        logger.debug("現在処理中の文字列: %s", current)

        for i in range(len(current) - 1):
            if current[i:i+2] == '..':
                logger.debug("'..'を見つけました。位置: %d", i)
                for j in range(len(current) - 1):
                    if j != i and current[j] != '.' and current[j+1] != '.':
                        logger.debug("置換前文字列: %s", current)
                        new_string = list(current)
                        new_string[i:i+2], new_string[j:j+2] = new_string[j:j+2], new_string[i:i+2]
                        new_string = ''.join(new_string)
                        logger.debug("置換後文字列: %s", new_string)
                        
                        if new_string not in seen:
                            queue.append(new_string)
                            seen.add(new_string)
                            result.append(new_string)
                            logger.info(f"新しい置換を追加: {new_string}, キューの情報: {queue}")
                        else:
                            logger.debug("重複した文字列: %s", new_string)

    logger.info("置換生成が完了しました。総数: %d", len(result))
    return result

# 使用例
debug_mode = True  # デバッグモードを有効にする場合はTrueに設定
logger = setup_logger(debug_mode)

s = "ABBBB.."
logger.info("入力文字列: %s", s)
permutations = generate_permutations(s, logger)
logger.info("生成された置換の数: %d", len(permutations))

for perm in permutations:
    logger.info("生成された置換: %s", perm)

print(f"生成された置換の数: {len(permutations)}")
for perm in permutations:
    print(perm)

この関数をそのまま適用してもTLEするのが目に見えているから、もう少し工夫が必要と。