概要

各料理の得点（基本点 + アレンジ点）を計算し、その合計を求める単純な集計問題です。

考察

この問題で重要な点は以下の通りです：

問題の理解

• \(N\) 種類の基本レシピがあり、それぞれに基本点 \(A_i\) が設定されている
• \(M\) 品の料理を作り、各料理は「ベースとなる基本レシピの基本点 \(A_{B_j}\)」+「アレンジ点 \(S_j\)」で得点が決まる
• すべての料理の得点の合計を求める

具体例で確認

例えば、基本点が \(A = [100, 200, 150]\) の3つのレシピがあり、以下の2品を作るとします： - 1品目：レシピ2をベースに、アレンジ点 \(+50\) → 得点 = \(200 + 50 = 250\) - 2品目：レシピ1をベースに、アレンジ点 \(-30\) → 得点 = \(100 + (-30) = 70\)

合計得点 = \(250 + 70 = 320\)

この問題のポイント

この問題は素朴なアプローチで十分解けます。各料理について順番に得点を計算して足し合わせるだけで、計算量的にも問題ありません。

ただし注意点として： - 配列のインデックスは0始まりなので、\(B_j\) 番目のレシピの基本点は A[B_j - 1] でアクセスする必要がある - 得点の合計が非常に大きくなる可能性があるが、Pythonでは整数のオーバーフローを気にする必要がない

アルゴリズム

1. \(N\) と \(M\) を読み込む
2. 基本点の配列 \(A\) を読み込む
3. 合計得点を表す変数 total を \(0\) で初期化
4. \(M\) 回のループで、各料理について：
   • ベースレシピ番号 \(B\) とアレンジ点 \(S\) を読み込む
   • total に \(A[B-1] + S\) を加算
5. total を出力

計算量

• 時間計算量: \(O(N + M)\)
  • 基本点の配列を読み込むのに \(O(N)\)
  • \(M\) 品の料理の得点を計算するのに \(O(M)\)
• 空間計算量: \(O(N)\)
  • 基本点の配列 \(A\) を保持するのに \(O(N)\)

実装のポイント

• 1-indexed と 0-indexed の変換: 問題文では基本レシピは1番目から数えていますが、Pythonの配列は0番目から始まります。そのため、レシピ番号 \(B\) に対応する基本点は A[B - 1] でアクセスします。

• 負のアレンジ点: アレンジ点 \(S_j\) は負の値を取りうるので、得点が基本点より低くなる場合もあります。

• オーバーフロー: \(A_i\) は最大 \(10^9\)、\(M\) は最大 \(10^5\) なので、合計は最大約 \(2 \times 10^{14}\) 程度になりますが、Pythonでは自動的に大きな整数を扱えるため問題ありません。

  ソースコード

def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    
    total = 0
    for _ in range(M):
        B, S = map(int, input().split())
        total += A[B - 1] + S
    
    print(total)

if __name__ == "__main__":
    main()

---

この解説は claude4.5opus によって生成されました。