【競技プログラミング】AtCoder Beginner Contest 275_C問題

問題

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

一覧ページ

解法手順1

1. 9x9の二次元配列として入力を受け取る。
2. 二重ループを使用して、平面上の全ての点を走査する。
3. 各点から、x方向とy方向に異なる長さと向きを持つベクトルを考える。
4. 現在の点と、そこからx方向、y方向、x+y方向に移動した3点が全て平面内にあり、かつ全てポーン('#')である場合を探す。
5. 条件を満たす4点の組み合わせを見つけたら、それらをソートしてタプルとして集合に追加する。
6. 全ての探索が終わったら、集合の要素数（ユニークな正方形の数）を出力する。

ACコード1

ac.py

def io_func():
    # 9x9の二次元配列として入力を受け取る
    n = 9
    s = [list(input()) for _ in range(n)]
    return n, s

def is_valid_square(s, i, j, x, y):
    # 正方形の4つの頂点が全て平面内にあり、かつ全てポーン('#')であるかチェックする
    n = len(s)
    if (0 <= i < n and 0 <= j < n and s[i][j] == '#' and
        0 <= i+x < n and 0 <= j+y < n and s[i+x][j+y] == '#' and
        0 <= i+x+y < n and 0 <= j+y-x < n and s[i+x+y][j+y-x] == '#' and
        0 <= i+y < n and 0 <= j-x < n and s[i+y][j-x] == '#'):
        return True
    return False

def solve(n, s):
    ans = set()  # ユニークな正方形を格納するための集合

    # 平面上の全ての点を走査
    for x in range(n):
        for y in range(n):
            if x == 0 and y == 0:
                continue  # (0,0)のベクトルは無視

            # 各点から、x方向とy方向に異なる長さと向きを持つベクトルを考える
            for i in range(n):
                for j in range(n):
                    # 正方形の条件を満たすかチェック
                    if is_valid_square(s, i, j, x, y):
                        # 条件を満たす4点の組み合わせを見つけたら、それらをソートしてタプルとして集合に追加
                        square = sorted([(i, j), (i+x, j+y), (i+x+y, j+y-x), (i+y, j-x)])
                        ans.add(tuple(square))

    # 集合の要素数（ユニークな正方形の数）を返す
    return len(ans)

# メイン処理
n, s = io_func()
result = solve(n, s)
print(result)

###
# n: 平面の大きさ (9x9)
# s: 9x9の二次元配列で、ポーンの配置を表す
# ans: ユニークな正方形を格納するための集合
# x, y: ベクトルのx成分とy成分
# i, j: 平面上の点の座標

# 1. io_func関数:
#    - 9x9の二次元配列として入力を受け取る
#    - 平面の大きさnと入力配列sを返す
# 2. is_valid_square関数:
#    - 与えられた4点が正方形を形成し、全てポーンが置かれているかをチェックする
#    - 正方形の条件を満たす場合はTrue、そうでない場合はFalseを返す
# 3. solve関数:
#    - 平面上の全ての点を走査する
#    - 各点から、x方向とy方向に異なる長さと向きを持つベクトルを考える
#    - is_valid_square関数を使用して、正方形の条件を満たすかチェックする
#    - 条件を満たす4点の組み合わせを見つけたら、それらをソートしてタプルとして集合に追加する
#    - 全ての探索が終わったら、集合の要素数（ユニークな正方形の数）を返す
# 4. メイン処理:
#    - io_func関数を呼び出して入力を受け取る
#    - solve関数を呼び出して結果を得る
#    - 結果を出力する

オブジェクト指向版1

ac_object.py

import logging
from typing import List, Tuple, Set

def setup_logger(debug_mode: bool) -> logging.Logger:
    logger = logging.getLogger(__name__)
    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')
    file_handler.setFormatter(formatter)
    logger.addHandler(file_handler)
    
    return logger

class InputReader:
    @staticmethod
    def read_input() -> Tuple[int, List[List[str]]]:
        # 9x9の二次元配列として入力を受け取る
        n = 9
        s = [list(input()) for _ in range(n)]
        return n, s

class SquareValidator:
    @staticmethod
    def is_valid_square(s: List[List[str]], i: int, j: int, x: int, y: int) -> bool:
        # 正方形の4つの頂点が全て平面内にあり、かつ全てポーン('#')であるかチェックする
        n = len(s)
        return (0 <= i < n and 0 <= j < n and s[i][j] == '#' and
                0 <= i+x < n and 0 <= j+y < n and s[i+x][j+y] == '#' and
                0 <= i+x+y < n and 0 <= j+y-x < n and s[i+x+y][j+y-x] == '#' and
                0 <= i+y < n and 0 <= j-x < n and s[i+y][j-x] == '#')

class SquareSolver:
    def __init__(self, debug_mode: bool):
        self.logger = setup_logger(debug_mode)

    def solve(self, n: int, s: List[List[str]]) -> int:
        ans: Set[Tuple[Tuple[int, int], ...]] = set()  # ユニークな正方形を格納するための集合
        validator = SquareValidator()

        self.logger.debug("正方形の探索を開始します")

        # 平面上の全ての点を走査
        for x in range(n):
            for y in range(n):
                if x == 0 and y == 0:
                    continue  # (0,0)のベクトルは無視

                # 各点から、x方向とy方向に異なる長さと向きを持つベクトルを考える
                for i in range(n):
                    for j in range(n):
                        # 正方形の条件を満たすかチェック
                        if validator.is_valid_square(s, i, j, x, y):
                            # 条件を満たす4点の組み合わせを見つけたら、それらをソートしてタプルとして集合に追加
                            square = tuple(sorted([(i, j), (i+x, j+y), (i+x+y, j+y-x), (i+y, j-x)]))
                            ans.add(square)
                            self.logger.debug(f"新しい正方形を発見: {square}")

        self.logger.debug(f"探索完了。ユニークな正方形の数: {len(ans)}")
        # 集合の要素数（ユニークな正方形の数）を返す
        return len(ans)

class SquareCounter:
    def __init__(self, debug_mode: bool):
        self.solver = SquareSolver(debug_mode)
        self.reader = InputReader()

    def count_squares(self) -> int:
        # 入力を読み込む
        n, s = self.reader.read_input()
        # 正方形を数える
        return self.solver.solve(n, s)

def main():
    # デバッグモードを設定（True: デバッグログ出力, False: 通常実行）
    debug_mode = True
    
    counter = SquareCounter(debug_mode)
    result = counter.count_squares()
    print(result)

if __name__ == "__main__":
    main()

オブジェクト図

オブジェクト指向版1で書くメリット

拡張性と再利用性

ac_object.py

class FileInputReader:
    @staticmethod
    def read_input(filename: str) -> Tuple[int, List[List[str]]]:
        with open(filename, 'r') as file:
            n = 9
            s = [list(line.strip()) for line in file]
        return n, s

class SquareCounter:
    def __init__(self, debug_mode: bool, input_reader: InputReader):
        self.solver = SquareSolver(debug_mode)
        self.reader = input_reader

    def count_squares(self, filename: str) -> int:
        # ファイルから入力を読み込む
        n, s = self.reader.read_input(filename)
        # 正方形を数える
        return self.solver.solve(n, s)

def main():
    debug_mode = True
    file_reader = FileInputReader()
    counter = SquareCounter(debug_mode, file_reader)
    result = counter.count_squares("input.txt")
    print(result)

オブジェクト図