Before
AtCoder Beginner Contest 375_E 問題
Next
AtCoder Beginner Contest 376_D 問題
その他・記事まとめ
1日1題(C,D,E問題)解いていけば3日でAtCoder1回分、1年あれば十分最新に追いつけると皮算用していたけれど、週にAtCoder1回分進めることも稀で差は広がるばかり。
C問題とD問題だけ解いて、最新に追いつくことを優先しよっかなぁ、と思ったけど難易度でD問題 > E問題のものが多々あったりするからE問題も解く対象にしておきたい。
実力は付いているのか疑いたくなるけれど、1月に投稿した記事を見直したり、去年投稿した問題を振り返ってみると当時より解けるようになっていることを実感できる分、まぁ前進はしているのかな？と思い込んで地道にやるしかないか。
本問は整列してからのに二分探索ですね。
入力例3
毎回、ソートしているから駄目かな？と思ったけど、二分探索は本当に高速ですね。
ac.py(※logger=falseにしても、logger.debugをコメントアウトしないとTLE※)
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 = int(input())
toy_sizes = list(map(int, input().split()))
box_sizes = list(map(int, input().split()))
return n, toy_sizes, box_sizes
def solve(n, toy_sizes, box_sizes, logger):
logger.debug(f"おもちゃの個数: {n}")
logger.debug(f"おもちゃの大きさ一覧: {toy_sizes}")
logger.debug(f"既存の箱の大きさ一覧: {box_sizes}")
toy_sizes.sort()
logger.debug(f"おもちゃの大きさを昇順にソート: {toy_sizes}")
ok = 10**9 + 1
ng = 0
logger.debug(f"二分探索開始: ok={ok}, ng={ng}")
while ok - ng > 1:
candidate_box_sizes = box_sizes[:]
mid = (ok + ng) // 2
candidate_box_sizes.append(mid)
candidate_box_sizes.sort()
logger.debug(f"現在のmid={mid}を追加して箱サイズをソート: {candidate_box_sizes}")
can_pack = True
for i in range(n):
if toy_sizes[i] > candidate_box_sizes[i]:
logger.debug(f"おもちゃ{i}（大きさ{toy_sizes[i]}）は箱{i}（大きさ{candidate_box_sizes[i]}）に入らない。mid={mid}は不適。")
can_pack = False
ng = mid
break
if can_pack:
logger.debug(f"mid={mid}で全てのおもちゃが箱に入る。okを更新。")
ok = mid
if ok == 10**9 + 1:
logger.debug(f"条件を満たす箱の大きさが存在しない。-1を出力。")
print(-1)
else:
logger.debug(f"条件を満たす最小の箱の大きさ: {ok}")
print(ok)
def main():
debug_mode = False # 必要に応じてTrueに
logger = setup_logger(debug_mode)
n, toy_sizes, box_sizes = io_func()
solve(n, toy_sizes, box_sizes, logger)
if __name__ == "__main__":
main()
Views: 0
