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

問題

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

一覧ページ

雑記

AtCoder360のC/D/Eが難しすぎて、スランプに陥ったことに加え、この問題を「理解する」のに5時間くらい溶かした。
D問題って、こんなに難しかったけ。

2025-02-14 19:41:23,766 - __main__ - DEBUG - 左側移動後の仮状態: tmp=..BWBWBW
2025-02-14 19:41:23,766 - __main__ - DEBUG - 左側移動をキューに追加: tmp=..BWBWBW, count=1, 次のターゲット位置: i=0
2025-02-14 19:41:23,766 - __main__ - DEBUG - 左側移動: i=1, tar=6, 現在の状態: st=BWBWBW..
2025-02-14 19:41:23,766 - __main__ - DEBUG - 左側移動後の仮状態: tmp=B..WBWWB
2025-02-14 19:41:23,766 - __main__ - DEBUG - 左側移動をキューに追加: tmp=B..WBWWB, count=1, 次のターゲット位置: i=1
2025-02-14 19:41:23,766 - __main__ - DEBUG - 左側移動: i=2, tar=6, 現在の状態: st=BWBWBW..
2025-02-14 19:41:23,766 - __main__ - DEBUG - 左側移動後の仮状態: tmp=BW..BWBW
2025-02-14 19:41:23,766 - __main__ - DEBUG - 左側移動をキューに追加: tmp=BW..BWBW, count=1, 次のターゲット位置: i=2
2025-02-14 19:41:23,766 - __main__ - DEBUG - 左側移動: i=3, tar=6, 現在の状態: st=BWBWBW..
2025-02-14 19:41:23,766 - __main__ - DEBUG - 左側移動後の仮状態: tmp=BWB..WWB
2025-02-14 19:41:23,766 - __main__ - DEBUG - 左側移動をキューに追加: tmp=BWB..WWB, count=1, 次のターゲット位置: i=3
2025-02-14 19:41:23,766 - __main__ - DEBUG - 左側移動: i=4, tar=6, 現在の状態: st=BWBWBW..
2025-02-14 19:41:23,766 - __main__ - DEBUG - 左側移動後の仮状態: tmp=BWBW..BW
2025-02-14 19:41:23,766 - __main__ - DEBUG - 左側移動をキューに追加: tmp=BWBW..BW, count=1, 次のターゲット位置: i=4
2025-02-14 19:41:23,766 - __main__ - DEBUG - 現在の状態: st=..BWBWBW, count=1, tar=0
2025-02-14 19:41:23,766 - __main__ - DEBUG - 右側移動: i=2, tar=0, 現在の状態: st=..BWBWBW
2025-02-14 19:41:23,766 - __main__ - DEBUG - 右側移動後の仮状態: tmp=BW..BWBW
・・・

のように左右から切り取って移動パターンを放り込むのが超絶に難しかったよ。

解法手順1

(1) 事前チェック

• 初期状態と目標状態に含まれる "W" と "B" の数を比較する。
  • もし数が一致しない場合は、目標状態を達成することは不可能なので、-1 を出力して終了する。

(2) 幅優先探索 (BFS) を利用した最短操作回数の計算

• 幅優先探索を用いて、初期状態から目標状態までの最短操作回数を求める。
• 各状態をノードとして扱い、可能な操作による遷移をエッジとして探索する。

(3) 終了条件

• 現在の状態が目標状態と一致した場合、その時点で操作回数を出力して終了する。
• 探索が終了しても目標状態に到達できない場合は -1 を出力する。

ACコード1

ac.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 io_func():
    n = int(input())
    s = input()
    t = input()
    return n, s, t

# メイン処理
def solve(n, s, t, logger):
    logger.debug("solve関数開始: n=%d, s=%s, t=%s", n, s, t)
    
    s += ".."
    t += ".."

    b_count_s = s.count("B")
    b_count_t = t.count("B")

    logger.debug("Bの数: s=%d, t=%d", b_count_s, b_count_t)

    # Bの数が一致しない場合は解決不可能
    if b_count_s != b_count_t:
        print(-1)
        return

    q = deque()
    q.append([s, 0, n])
    visited = {}

    while q:
        st, count, tar = q.popleft()
        logger.debug("現在の状態: st=%s, count=%d, tar=%d", st, count, tar)

        if st == t:
            print(count)
            return

        # 左側の移動
        for i in range(tar - 1):
            logger.debug("左側移動: i=%d, tar=%d, 現在の状態: st=%s", i, tar, st)
            tmp = st[:i] + ".." + st[i + 2:tar] + st[i:i + 2] + st[tar + 2:]
            logger.debug("左側移動後の仮状態: tmp=%s", tmp)
            if tmp not in visited:
                visited[tmp] = True
                q.append([tmp, count + 1, i])
                logger.debug("左側移動をキューに追加: tmp=%s, count=%d, 次のターゲット位置: i=%d", tmp, count + 1, i)

        # 右側の移動
        for i in range(tar + 2, n + 1):
            logger.debug("右側移動: i=%d, tar=%d, 現在の状態: st=%s", i, tar, st)
            tmp = st[:tar] + st[i:i + 2] + st[tar + 2:i] + ".." + st[i + 2:]
            logger.debug("右側移動後の仮状態: tmp=%s", tmp)
            if tmp not in visited:
                visited[tmp] = True
                q.append([tmp, count + 1, i])
                logger.debug("右側移動をキューに追加: tmp=%s, count=%d, 次のターゲット位置: i=%d", tmp, count + 1, i)
                
    # 解が見つからない場合
    print(-1)

# メイン関数
def main():
    debug_mode = False  # デバッグモードを有効化
    logger = setup_logger(debug_mode)
    
    logger.info("プログラム開始")
    
    # 入力処理
    n, s, t = io_func()
    
    # 問題解決処理
    solve(n, s, t, logger)
    
    logger.info("プログラム終了")

if __name__ == "__main__":
    main()