問題
既存投稿一覧ページへのリンク
解法手順1
-
入力を受け取る。
- ケーキのサイズ (H, W)
- イチゴの数 N
- イチゴの座標 (pi, qi)
- 縦方向の切れ目の数 A と位置 ai
- 横方向の切れ目の数 B と位置 bi
-
イチゴの座標を、切れ目によって分割されるセルの座標に変換する。
- bisectを使用して、各イチゴがどのセルに属するかを効率的に判定する。
-
defaultdictを使用して、各セルにあるイチゴの数をカウントする。
- キーはセルの座標、値はイチゴの数とする。
-
セルごとのイチゴの数のリストを作成する。
-
全てのセルにイチゴがある場合と、ない場合で場合分けする。
- 全てのセルにイチゴがある場合：最小値と最大値を出力
- ないセルがある場合：最小値は0、最大値はイチゴの数の最大値を出力
-
結果を出力する。
ACコード1
ac.py
from collections import defaultdict as dd
from bisect import bisect
def io_func():
# ケーキのサイズを入力
h, w = map(int, input().split())
# イチゴの数を入力
n = int(input())
# イチゴの座標を入力
W = [tuple(map(int, input().split())) for _ in range(n)]
# 縦方向の切れ目の数と位置を入力
a = int(input())
A = list(map(int, input().split()))
# 横方向の切れ目の数と位置を入力
b = int(input())
B = list(map(int, input().split()))
return h, w, n, W, a, A, b, B
def solve(h, w, n, W, a, A, b, B):
# defaultdictを使用して各セルのイチゴの数をカウント
d = dd(int)
for x, y in W:
# bisectを使用してイチゴの座標をセルの座標に変換
d[(bisect(A, x), bisect(B, y))] += 1
# セルごとのイチゴの数のリストを作成
A = [x[1] for x in list(d.items())]
# 全てのセルにイチゴがある場合とない場合で場合分け
if len(A) < (a+1) * (b+1):
print(0, max(A))
else:
print(min(A), max(A))
# メイン処理
h, w, n, W, a, A, b, B = io_func()
solve(h, w, n, W, a, A, b, B)
###
# h, w: ケーキのサイズ
# n: イチゴの数
# W: イチゴの座標のリスト
# a: 縦方向の切れ目の数
# A: 縦方向の切れ目の位置のリスト
# b: 横方向の切れ目の数
# B: 横方向の切れ目の位置のリスト
# d: 各セルのイチゴの数を格納するdefaultdict
# 1. 入力処理を行うio_func関数を定義
# 2. 主な処理を行うsolve関数を定義
# 3. solve関数内で以下の処理を実行:
# - defaultdictを使用して各セルのイチゴの数をカウント
# - bisectを使用してイチゴの座標をセルの座標に変換
# - セルごとのイチゴの数のリストを作成
# - 全てのセルにイチゴがある場合とない場合で場合分けして結果を出力
# 4. メイン処理でio_func関数とsolve関数を呼び出し
オブジェクト指向版1
ac_object.py
import logging
from collections import defaultdict as dd
from bisect import bisect
from abc import ABC, abstractmethod
def setup_logger(debug_mode):
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 InputHandler(ABC):
@abstractmethod
def get_input(self):
pass
class StandardInputHandler(InputHandler):
def get_input(self):
# ケーキのサイズを入力
h, w = map(int, input().split())
# イチゴの数を入力
n = int(input())
# イチゴの座標を入力
W = [tuple(map(int, input().split())) for _ in range(n)]
# 縦方向の切れ目の数と位置を入力
a = int(input())
A = list(map(int, input().split()))
# 横方向の切れ目の数と位置を入力
b = int(input())
B = list(map(int, input().split()))
return h, w, n, W, a, A, b, B
class OutputHandler(ABC):
@abstractmethod
def output_result(self, min_strawberries, max_strawberries):
pass
class StandardOutputHandler(OutputHandler):
def output_result(self, min_strawberries, max_strawberries):
print(min_strawberries, max_strawberries)
class StrawberryCakeAnalyzer:
def __init__(self, debug_mode=False):
self.logger = setup_logger(debug_mode)
def analyze(self, h, w, n, W, a, A, b, B):
self.logger.debug("ケーキの分析を開始します")
# defaultdictを使用して各セルのイチゴの数をカウント
d = dd(int)
for x, y in W:
# bisectを使用してイチゴの座標をセルの座標に変換
cell = (bisect(A, x), bisect(B, y))
d[cell] += 1
self.logger.debug(f"イチゴの座標 ({x}, {y}) をセル {cell} に配置しました")
# セルごとのイチゴの数のリストを作成
strawberry_counts = [count for count in d.values()]
self.logger.debug(f"各セルのイチゴの数: {strawberry_counts}")
# 全てのセルにイチゴがある場合とない場合で場合分け
if len(strawberry_counts) < (a+1) * (b+1):
self.logger.debug("イチゴのないセルが存在します")
return 0, max(strawberry_counts)
else:
self.logger.debug("全てのセルにイチゴが存在します")
return min(strawberry_counts), max(strawberry_counts)
def main(debug_mode=False):
input_handler = StandardInputHandler()
output_handler = StandardOutputHandler()
analyzer = StrawberryCakeAnalyzer(debug_mode)
# 入力を取得
h, w, n, W, a, A, b, B = input_handler.get_input()
# 分析を実行
min_strawberries, max_strawberries = analyzer.analyze(h, w, n, W, a, A, b, B)
# 結果を出力
output_handler.output_result(min_strawberries, max_strawberries)
if __name__ == "__main__":
main(debug_mode=False) # デバッグモードを有効にする場合はTrueに設定
オブジェクト図
オブジェクト指向版1で書くメリット
拡張性と再利用性
ac_object.py
class FileInputHandler(InputHandler):
def __init__(self, filename):
self.filename = filename
def get_input(self):
with open(self.filename, 'r') as f:
h, w = map(int, f.readline().split())
n = int(f.readline())
W = [tuple(map(int, f.readline().split())) for _ in range(n)]
a = int(f.readline())
A = list(map(int, f.readline().split()))
b = int(f.readline())
B = list(map(int, f.readline().split()))
return h, w, n, W, a, A, b, B
class FileOutputHandler(OutputHandler):
def __init__(self, filename):
self.filename = filename
def output_result(self, min_strawberries, max_strawberries):
with open(self.filename, 'w') as f:
f.write(f"{min_strawberries} {max_strawberries}\n")
# main関数の修正
def main(debug_mode=False, input_file='input.txt', output_file='output.txt'):
# input_handler = StandardInputHandler()
output_handler = StandardOutputHandler()
input_handler = FileInputHandler(input_file)
# output_handler = FileOutputHandler(output_file)
analyzer = StrawberryCakeAnalyzer(debug_mode)
# 入力を取得
h, w, n, W, a, A, b, B = input_handler.get_input()
# 分析を実行
min_strawberries, max_strawberries = analyzer.analyze(h, w, n, W, a, A, b, B)
# 結果を出力
output_handler.output_result(min_strawberries, max_strawberries)
if __name__ == "__main__":
main(debug_mode=True) # デバッグモードを有効にする場合はTrueに設定
input.txt
7 6
5
6 1
3 1
4 2
1 5
6 2
2
2 5
2
3 4