概要

各基本レシピの基本点と、ベースとなるレシピ番号とアレンジ点が与えられるので、全ての料理の得点の合計を求める問題です。

考察

この問題は非常にシンプルで、各料理について「ベースとなる基本レシピの基本点 + アレンジ点」を計算し、それらを全て足し合わせるだけで解けます。制約条件として \(N\) と \(M\) が最大 \(10^5\) と大きいですが、各料理の処理は基本レシピの配列からの参照と加算のみなので、十分高速に処理できます。

アルゴリズム

1. まず、基本レシピの基本点 \(A_1, A_2, \ldots, A_N\) を配列として読み込む
2. 続いて \(M\) 個の料理情報（ベースレシピ番号 \(B_j\) とアレンジ点 \(S_j\)）を読み込む
3. 各料理について、\(A[B_j-1] + S_j\) を計算し、合計値に加算する
4. 最終的な合計値を出力する

配列のインデックスは0から始まるため、ベースレシピ番号 \(B_j\) から1を引いてアクセスする必要があります。

計算量

• 時間計算量: \(O(N + M)\)
  • 基本レシピの読み込みに \(O(N)\)
  • 各料理の処理に \(O(M)\)
• 空間計算量: \(O(N)\)
  • 基本レシピの配列を保持するため

実装のポイント

• 入力データを一度に読み込んでから処理することで、効率的な入出力が可能になります

• ベースレシピ番号から1を引くことで、配列のインデックスに正しくアクセスできます

• 合計値は大きな数になる可能性があるため、整数型のオーバーフローに注意が必要ですが、Pythonでは自動で多倍長整数が扱われるため問題ありません

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    m = int(data[1])
    A = list(map(int, data[2:2+n]))
    total = 0
    index = 2 + n
    for _ in range(m):
        b = int(data[index])
        s = int(data[index+1])
        index += 2
        total += A[b-1] + s
    print(total)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。