【競技プログラミング】AtCoder Beginner Contest 376_C問題の考え方

問題

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

一覧ページ

Before

AtCoder Beginner Contest 375_E 問題

Next

AtCoder Beginner Contest 376_D 問題

その他・記事まとめ

Unity関連 / Qiita

雑記(ポエム)

1日1題(C,D,E問題)解いていけば3日でAtCoder1回分、1年あれば十分最新に追いつけると皮算用していたけれど、週にAtCoder1回分進めることも稀で差は広がるばかり。
C問題とD問題だけ解いて、最新に追いつくことを優先しよっかなぁ、と思ったけど難易度でD問題 > E問題のものが多々あったりするからE問題も解く対象にしておきたい。
実力は付いているのか疑いたくなるけれど、1月に投稿した記事を見直したり、去年投稿した問題を振り返ってみると当時より解けるようになっていることを実感できる分、まぁ前進はしているのかな？と思い込んで地道にやるしかないか。

解法手順1

本問は整列してからのに二分探索ですね。

入力例3

ACコード1

毎回、ソートしているから駄目かな？と思ったけど、二分探索は本当に高速ですね。

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()