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

問題

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

一覧ページ

解法手順1

1. データ構造の初期化

• 各行と列の壁の位置を効率的に管理するため、SortedList を使用する。
  • rows[i]: $i$ 行目に残っている壁の列インデックスを保持。
  • cols[j]: $j$ 列目に残っている壁の行インデックスを保持。
• 初期状態では、各行にはすべての列 ($0$ から $W-1$) が、各列にはすべての行 ($0$ から $H-1$) が含まれている。

rows = [SortedList(range(W)) for _ in range(H)]
cols = [SortedList(range(H)) for _ in range(W)]

---

2. クエリ処理

各クエリで以下の処理を行う

(1) 爆弾を置いたマスに壁がある場合

• 壁を破壊し、その位置を rows と cols から削除する

if c in rows[r]:
    rows[r].discard(c)
    cols[c].discard(r)

(2) 爆弾を置いたマスに壁がない場合

• 上下左右方向で最初に現れる壁を探して破壊する。
• SortedList の二分探索機能 (bisect) を利用して効率的に次の壁の位置を取得する。

# 行方向 (右側と左側)
idx1 = rows[r].bisect(c)
if 0 <= idx1 < len(rows[r]):
    tmp = rows[r].pop(idx1)
    cols[tmp].discard(r)

idx2 = rows[r].bisect(c) - 1
if 0 <= idx2 < len(rows[r]):
    tmp = rows[r].pop(idx2)
    cols[tmp].discard(r)

# 列方向 (下側と上側)
idx3 = cols[c].bisect(r)
if 0 <= idx3 < len(cols[c]):
    tmp = cols[c].pop(idx3)
    rows[tmp].discard(c)

idx4 = cols[c].bisect(r) - 1
if 0 <= idx4 < len(cols[c]):
    tmp = cols[c].pop(idx4)
    rows[tmp].discard(c)

---

3. 残った壁の数を計算

すべてのクエリ処理が終わった後、各行 (rows) に残っている壁の数を合計する。

remaining_walls = sum(len(row) for row in rows)

ACコード1

ac.py

import logging
from sortedcontainers import SortedList

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

def io_func():
    """
    標準入力からデータを受け取る関数。
    """
    H, W, Q = map(int, input().split())
    queries = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(Q)]
    return H, W, queries

def solve(H, W, queries, logger):
    """
    メイン処理を行う関数。
    """
    # 初期化: 各行と列の壁の位置をSortedListで管理
    rows = [SortedList(range(W)) for _ in range(H)]
    cols = [SortedList(range(H)) for _ in range(W)]

    logger.debug(f"初期化完了: rows={rows}, cols={cols}")

    # クエリ処理
    for r, c in queries:
        logger.debug(f"クエリ処理開始: 爆弾位置=({r}, {c})")

        if c in rows[r]:
            rows[r].discard(c)
            cols[c].discard(r)
            logger.debug(f"壁破壊: ({r}, {c})")
        else:
            # 行方向の処理
            idx1 = rows[r].bisect(c)
            if 0 <= idx1 < len(rows[r]):
                tmp = rows[r].pop(idx1)
                cols[tmp].discard(r)
                logger.debug(f"右方向の壁破壊: ({r}, {tmp})")
            idx2 = rows[r].bisect(c) - 1
            if 0 <= idx2 < len(rows[r]):
                tmp = rows[r].pop(idx2)
                cols[tmp].discard(r)
                logger.debug(f"左方向の壁破壊: ({r}, {tmp})")

            # 列方向の処理
            idx3 = cols[c].bisect(r)
            if 0 <= idx3 < len(cols[c]):
                tmp = cols[c].pop(idx3)
                rows[tmp].discard(c)
                logger.debug(f"下方向の壁破壊: ({tmp}, {c})")
            idx4 = cols[c].bisect(r) - 1
            if 0 <= idx4 < len(cols[c]):
                tmp = cols[c].pop(idx4)
                rows[tmp].discard(c)
                logger.debug(f"上方向の壁破壊: ({tmp}, {c})")

    # 残った壁の数をカウント
    remaining_walls = sum(len(row) for row in rows)
    logger.debug(f"残った壁の数: {remaining_walls}")
    
    print(remaining_walls)

def main():
    """
    メイン関数。
    """
    debug_mode = False  # デバッグモードを有効にする場合はTrueに設定
    logger = setup_logger(debug_mode)

    H, W, queries = io_func()
    logger.debug(f"入力データ: H={H}, W={W}, queries={queries}")

    solve(H, W, queries, logger)

if __name__ == "__main__":
    main()