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

問題

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

一覧ページ

Before

AtCoder Beginner Contest 378_E 問題

Next

AtCoder Beginner Contest 379_D 問題

その他・記事まとめ

Unity関連 / Qiita

解法手順1

ステップ1: 入力値を整理し、位置ごとの石の個数リストを作る

• 各マスの番号と石の個数をペアにしてリスト化し、位置順にソートする。(Xが小さい順ではないため)

# 例: stone_positions = [3, 1], stone_counts = [2, 1]
position_and_count = []
for pos, cnt in zip(stone_positions, stone_counts):
    position_and_count.append([pos, cnt])
position_and_count.sort()
# 結果: [[1, 1], [3, 2]]

---

ステップ2: 不可能判定のための累積条件をチェック

• 左から順に、i番目までの累積石数が「そのマス番号-1」未満なら不可能。
• 途中でこの条件を満たさない場合は -1 を出力して終了する。

is_possible = True
current_total = 0
for position, count in position_and_count:
    if current_total < position - 1:
        print(-1)
        is_possible = False
        break
    current_total += count

---

ステップ3: 全体の石の個数がNかどうかをチェック

• すべてのマスに1個ずつ石を置くには合計でN個の石が必要。
• そうでなければ -1 を出力。

if is_possible:
    if current_total != N:
        print(-1)

---

ステップ4: 最小操作回数を計算して出力

• 操作回数は「理想状態の石の位置の総和」から「現在の石の位置の総和」を引いたもの。
• 理想状態の総和は $1+2+\cdots+N = \frac{N(N+1)}{2}$
• 現在の総和は $\sum X_i \times A_i$

    else:
        operation_cost = 0
        for position, count in position_and_count:
            operation_cost += position * count
        min_operations = N * (N + 1) // 2 - operation_cost
        print(min_operations)

ACコード1

ac.py

import logging
from collections import defaultdict

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 = map(int, input().split())
    stone_positions = list(map(int, input().split()))
    stone_counts = list(map(int, input().split()))
    return N, M, stone_positions, stone_counts

def solve(N, M, stone_positions, stone_counts, logger):
    # 各マスの情報をまとめる
    logger.debug(f"入力値: N={N}, M={M}, stone_positions={stone_positions}, stone_counts={stone_counts}")
    position_and_count = []
    for pos, cnt in zip(stone_positions, stone_counts):
        position_and_count.append([pos, cnt])
        logger.debug(f"マス{pos}に石{cnt}個を記録")
    position_and_count.sort()
    logger.debug(f"位置と石の個数を位置順にソート: {position_and_count}")

    # 操作可能かどうかの判定と最小操作回数の計算
    is_possible = True
    current_total = 0
    operation_cost = 0
    for position, count in position_and_count:
        logger.debug(f"マス{position}に石{count}個。現在までの合計石数: {current_total}")
        if current_total < position - 1:
            logger.debug(f"マス{position}に到達するための石が不足（{current_total} < {position - 1}）")
            print(-1)
            is_possible = False
            break
        current_total += count
        operation_cost += position * count
        logger.debug(f"石を加算後の合計石数: {current_total}、操作コスト累積: {operation_cost}")

    if is_possible:
        if current_total != N:
            logger.debug(f"全マスに石を1個ずつ配置できない（合計石数{current_total} != {N}）")
            print(-1)
        else:
            min_operations = N * (N + 1) // 2 - operation_cost
            logger.debug(f"最小操作回数を計算: {min_operations}")
            print(min_operations)

def main():
    debug_mode = False  # 必要に応じてTrueに変更
    logger = setup_logger(debug_mode)
    N, M, stone_positions, stone_counts = io_func()
    solve(N, M, stone_positions, stone_counts, logger)

if __name__ == "__main__":
    main()