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

# 問題
https://atcoder.jp/contests/abc379/tasks/abc379_c

# 既存投稿一覧ページへのリンク
[一覧ページ](https://qiita.com/o_chan_t/items/fc759695acfaef8df2cc)

## Before
[AtCoder Beginner Contest 378_E 問題](https://qiita.com/o_chan_t/items/b1954cb730a5c07e9aed)

## Next
[AtCoder Beginner Contest 379_D 問題]()

## その他・記事まとめ
[Unity関連 / Qiita](https://qiita.com/o_chan_t/items/0b5ae1e7c45f106082b8)


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

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

```python
# 例: 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` を出力して終了する。

```python
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` を出力。

```python
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$

```python
    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
```python: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()

```