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

問題

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

一覧ページ

解法手順1

1. 入力処理

コード内のio_func()関数を用いて、以下の入力を処理する

• 1行目: 盤面サイズ $N$ とコマ数 $M$ を取得。
• 2行目以降: 各コマの位置（行番号、列番号）を取得。

2. ナイトの移動ルールを定義

ナイトが移動できる8方向をタプルで定義する

moves = [(2, 1), (1, 2), (-1, 2), (-2, 1),
         (-2, -1), (-1, -2), (1, -2), (2, -1)]

---

3. 禁止リスト（forbidden）の構築

禁止リストには以下を含める

1. 既存のコマが置かれているマス。
2. 既存のコマがナイトで到達可能なすべてのマス。

手順

• 各コマ位置 $(a, b)$ を禁止リストに追加。
• 各コマ位置からナイトが移動可能な全てのマス $(na, nb)$ を計算し、範囲内なら禁止リストに追加。

範囲チェック:

ナイトの移動した結果が盤面外の場合は無視します:

if 1 <= na <= n and 1 <= nb <= n:
    forbidden.add((na, nb))

---

4. 配置可能な空きマス数を計算

盤面全体の総マス数 $N^2$（$N \times N$）から、禁止リストに登録されたマス数を引くことで、配置可能な空きマス数を求める

ans = n * n - len(forbidden)

---

ACコード1

ac.py

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

def io_func():
    # 最初の行で n, m を取得
    n, m = map(int, input().split())
    
    # 次の m 行でコマの位置情報をリストとして取得
    pieces = []
    for _ in range(m):
        a, b = map(int, input().split())
        pieces.append((a, b))
    
    return n, m, pieces


# メインのロジック
def solve():
    logger = setup_logger(debug_mode=True)  # デバッグモード有効化
    n, m, pieces = io_func()
    
    logger.debug(f"盤面サイズ: {n}x{n}, コマの数: {m}")
    
    forbidden = set()
    moves = [(2, 1), (1, 2), (-1, 2), (-2, 1), (-2, -1), (-1, -2), (1, -2), (2, -1)]

    for a, b in pieces:
        forbidden.add((a, b))
        logger.debug(f"コマの位置: ({a}, {b}) を追加")
        
        for da, db in moves:
            na, nb = a + da, b + db
            if 1 <= na <= n and 1 <= nb <= n:
                forbidden.add((na, nb))
                logger.debug(f"コマ ({a}, {b}) による移動先 ({na}, {nb}) を禁止リストに追加")

    ans = n * n - len(forbidden)
    logger.debug(f"禁止マス数: {len(forbidden)}, 配置可能マス数: {ans}")
    
    print(ans)

# エントリーポイント
def main():
    solve()

if __name__ == "__main__":
    main()