👌

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

2025/01/01に公開

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

 要約変数
N: 主菜の種類数
M: 副菜の種類数
Ai: i番目の主菜の価格
Bj: j番目の副菜の価格
P: 定食の価格上限
定食の構成
1種類の主菜と1種類の副菜で構成される
定食の価格は min(s, P) で計算される

ここで、s は選んだ主菜と副菜の価格の合計
すべての可能な主菜と副菜の組み合わせ（NM通り）に対する定食の価格の総和

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

 アプローチ主菜と副菜の価格をソートし、二分探索を用いて計算を最適化する

 解法手順入力を受け取り、主菜の価格リストAsと副菜の価格リストBsを作成する。
AsとBsをそれぞれ昇順にソートする。
Bsの累積和リストBs_accumを作成する。これは後の計算で使用する。
各主菜の価格aに対して以下の処理を行う：

a. a + Bs[-1] < P の場合（すべての組み合わせがP未満）：
この主菜とすべての副菜の組み合わせの合計をそのまま結果に加算する。
b. a + Bs[0] >= P の場合（すべての組み合わせがP以上）：
この主菜とすべての副菜の組み合わせに対してPを結果に加算する。
c. 上記以外の場合：
二分探索を用いて、a + Bj >= P となる最小のjを見つける。
j以降の組み合わせに対してはPを加算する。
j未満の組み合わせに対しては、実際の合計を加算する。
全ての計算が終わったら、最終的な結果を出力する。

 ACコードac.py
def io_func():
    # 入力を受け取る
    N, M, P = map(int, input().split())  # N: 主菜の数, M: 副菜の数, P: 上限価格
    As = list(map(int, input().split()))  # 主菜の価格リスト
    Bs = list(map(int, input().split()))  # 副菜の価格リスト
    return N, M, P, As, Bs

def solve(N, M, P, As, Bs):
    # 主菜と副菜の価格リストをソート
    As.sort()
    Bs.sort()

    # 副菜の累積和リストを作成
    Bs_accum = []
    total = 0
    for b in Bs:
        total += b
        Bs_accum.append(total)

    result = 0
    for a in As:
        left = 0
        right = len(Bs)

        if a + Bs[-1] < P:
            # すべての組み合わせがP未満の場合
            result += len(Bs) * a + Bs_accum[-1]
            continue

        if a + Bs[0] >= P:
            # すべての組み合わせがP以上の場合
            result += P * len(Bs)
            continue

        # 二分探索でa + Bj >= P となる最小のjを見つける
        while left + 1 < right:
            mid = (left + right) // 2
            if Bs[mid] + a >= P:
                right = mid
            else:
                left = mid

        # j以降の組み合わせに対してはPを加算
        result += (len(Bs) - right) * P
        # j未満の組み合わせに対しては実際の合計を加算
        result += (left + 1) * a + Bs_accum[left]

    return result

if __name__=="__main__":
    # メイン処理
    N, M, P, As, Bs = io_func()
    print(solve(N, M, P, As, Bs))

###
# N: 主菜の数
# M: 副菜の数
# P: 上限価格
# As: 主菜の価格リスト
# Bs: 副菜の価格リスト
# Bs_accum: 副菜の価格の累積和リスト
# result: 最終的な合計金額

# 1. io_func関数:
#    - 標準入力から値を読み取り、必要なデータを返す
# 2. solve関数:
#    - 主な計算ロジックを含む
#    - 主菜と副菜の価格リストをソート
#    - 副菜の累積和リストを作成
#    - 各主菜に対して、組み合わせの合計金額を計算
#    - 二分探索を用いて効率的に計算を行う
# 3. メイン処理:
#    - io_func関数を呼び出してデータを取得
#    - solve関数を呼び出して結果を計算
#    - 結果を出力

問題

要約

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

アプローチ

解法手順

ACコード

Discussion