【競技プログラミング】AtCoder Beginner Contest 321_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) を計算する
   • すべての組み合わせの定食価格を合計する

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

一覧ページ

解法手順

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コード

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個の定食上限価格

1. 最終的な結果を出力する
   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個の定食上限価格

その他周辺知識

累積和

X = list(itertools.accumulate(B))  # B の累積和リスト X を作成する

累積和は、数列の部分和を効率的に計算する。

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

二分探索

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

p-a以上となる最小のインデックスを探す。

条件分岐

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を使用する。