【競技プログラミング】AtCoder Beginner Contest 321_D問題

# 問題
https://atcoder.jp/contests/abc321/tasks/abc321_d

## 要約
1. 変数情報：
   - N: 主菜の種類数
   - M: 副菜の種類数
   - Ai: i番目の主菜の価格
   - Bj: j番目の副菜の価格
   - P: 定食の価格上限

2. 定食の構成：
   - 1種類の主菜と1種類の副菜で構成される
   - 定食の価格は min(s, P) で計算される
     ここで、s は選んだ主菜と副菜の価格の合計

3. 求めるもの：
   すべての可能な主菜と副菜の組み合わせ（NM通り）に対する定食の価格の総和

4. 計算方法：
   - 各主菜（N種類）と各副菜（M種類）のすべての組み合わせを考える
   - 各組み合わせに対して、定食の価格 min(Ai + Bj, P) を計算する
   - すべての組み合わせの定食価格を合計する


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


# 解法手順

1. 入力を受け取る：
   - N, M, P を入力から読み取る
   - 主菜の価格リスト A を入力から読み取る
   - 副菜の価格リスト B を入力から読み取る

2. データの前処理：
   - A と B をそれぞれソートする
   - B の累積和リスト X を作成する

3. 各主菜に対して以下の処理を行う：
   - 現在の主菜の価格を a とする
   - 二分探索を使用して、B の中で p-a 以上となる最小のインデックス tmp を見つける
   - tmp が 0 でない場合：
     - X[tmp-1] + tmp * a + (len(B) - tmp) * p を計算し、結果に加算する
   - tmp が 0 の場合：
     - len(B) * p を結果に加算する

4. 最終的な結果を出力する


# ACコード
```python:ac.py

import itertools
import bisect
import operator

def solve():
    # 2. データの前処理
    A.sort()  # A をソートする
    B.sort()  # B をソートする
    X = list(itertools.accumulate(B))  # B の累積和リスト X を作成する

    # 3. 各主菜に対して処理を行う
    ans = 0  # 結果を格納する変数を初期化
    for a in A:
        tmp = bisect.bisect_left(B, p - a)  # 二分探索で p-a 以上となる最小のインデックスを見つける
        if tmp != 0:
            # tmp が 0 でない場合の計算
            ans_a = X[tmp-1] + tmp * a + (len(B) - tmp) * p
        else:
            # tmp が 0 の場合の計算
            ans_a = len(B) * p
        ans += ans_a  # 結果に加算する

    # 4. 最終的な結果を出力する
    print(ans)

if __name__ == "__main__":
    # 1. 入力を受け取る
    n, m, p = map(int, input().split())  # N, M, P を入力から読み取る
    A = list(map(int, input().split()))  # 主菜の価格リスト A を入力から読み取る
    B = list(map(int, input().split()))  # 副菜の価格リスト B を入力から読み取る
    solve()


```


# 机上トレース
# 入力例1
1. データの前処理：
   - A と B をそれぞれソートする
A=[3, 5]
B=[1, 6]
   - B の累積和リスト X を作成する
X=[1,7]

2. 各主菜に対して以下の処理を行う：
2.1 1回目のループ
   - 現在の主菜の価格を a とする
a = 3
   - 二分探索を使用して、B の中で p-a 以上となる最小のインデックス tmp を見つける
tmp = bisect.bisect_left([1, 6], 7 - 3) = 1
   - tmp が 0 でない場合：
     - X[tmp-1] + tmp * a + (len(B) - tmp) * p を計算し、結果に加算する
ans += X[0]+1*3+(2-1)*7 = 1+3+7 = 11
→ 1円の副菜 + 3円の主菜1個 + 1個の定食上限価格

2.2 2回目のループ
   - 現在の主菜の価格を a とする
a = 5
   - 二分探索を使用して、B の中で p-a 以上となる最小のインデックス tmp を見つける
tmp = bisect.bisect_left([1, 6], 7 - 5) = 1
   - tmp が 0 でない場合：
     - X[tmp-1] + tmp * a + (len(B) - tmp) * p を計算し、結果に加算する
ans = X[0]+1*5+(2-1)*7 = 1+5+7 = 13
ans += 13 -> 24
→ 1円の副菜 + 5円の主菜1個 + 1個の定食上限価格

3. 最終的な結果を出力する
ans = 24

# 例01
1. データの前処理：
   - A と B をそれぞれソートする
A=[4, 6, 7, 8, 9, 10, 14]
B=[1, 5, 6, 7, 8, 9, 10, 11, 14, 16, 17]
   - B の累積和リスト X を作成する
X=[1, 6, 12, 19, 27, 36, 46, 57, 71, 87, 104]

2. 各主菜に対して以下の処理を行う：
2.1 1回目のループ
   - 現在の主菜の価格を a とする
a = 4
   - 二分探索を使用して、B の中で p-a 以上となる最小のインデックス tmp を見つける
tmp = bisect.bisect_left([1, 5, 6, 7, 8, 9, 10, 11, 14, 16, 17], 14 - 4) = 6
   - tmp が 0 でない場合：
     - X[tmp-1] + tmp * a + (len(B) - tmp) * p を計算し、結果に加算する
ans += X[5]+4*6+(11-6)*14 = 36+24+70 = 130
→ {(1, 5, 6, 7, 8, 9)円の副菜 + 4円の主菜6個} + 5個の定食上限価格


# その他周辺知識

## 累積和
```python
X = list(itertools.accumulate(B))  # B の累積和リスト X を作成する
```
累積和は、数列の部分和を効率的に計算する。

X[i] = B[0] + B[1] + ... + B[i]


## 二分探索
```python
tmp = bisect.bisect_left(B, p - a)  # 二分探索で p-a 以上となる最小のインデックスを見つける
```
p-a以上となる最小のインデックスを探す。

## 条件分岐
```python
if tmp != 0:
    ans_a = X[tmp-1] + tmp * a + (len(B) - tmp) * p
else:
    ans_a = len(B) * p
```
`tmp`が0でない場合、`X[tmp-1]`（累積和）、`tmp * a`、`(len(B) - tmp) * p`を合計している。
`tmp`が0の場合は、すべての組み合わせで上限価格`p`を使用する。