概要

\(N\) 種類の基本レシピの基本点 \(A_i\) が与えられ、それをもとに \(M\) 品の料理を作ります。各料理の得点は「ベースにした基本レシピの点数 + アレンジ点」で決まるため、それら \(M\) 品の合計得点を求める問題です。

考察

この問題で求めたいのは、各料理 \(j\) (\(1 \le j \le M\)) の得点の総和です。 \(j\) 番目の料理の得点は、問題文の通り \(A_{B_j} + S_j\) と表せます。したがって、最終的な答えは以下の式の値を計算することになります。

\[\sum_{j=1}^{M} (A_{B_j} + S_j)\]

重要なポイント

1. 配列の添字（インデックス）: 問題文では基本レシピの番号が \(1, 2, \ldots, N\) と \(1\) から始まる形式（1-indexed）で与えられています。プログラミング言語（Pythonなど）の配列は通常 \(0\) から始まる（0-indexed）ため、レシピ番号 \(B_j\) を配列の添字として使う際は \(A[B_j - 1]\) のように \(1\) を引く必要があります。

2. 計算量と実行時間: \(N\) と \(M\) が最大 \(10^5\) と大きいため、二重ループなどを使うと間に合いません。しかし、各料理の計算は「配列からの値の取り出し」と「加算」のみなので、料理ごとに \(O(1)\) で計算できます。全体で \(O(N + M)\) となり、十分に高速に動作します。

3. 大きな数値の扱い: 基本点 \(A_i\) やアレンジ点 \(S_j\) は最大 \(10^9\) であり、料理の数 \(M\) も \(10^5\) です。合計値は最大で \(2 \times 10^{14}\) 程度になる可能性があります。Pythonでは自動的に大きな整数（多倍長整数）が扱われますが、他の言語（C++など）では 64bit 整数型（long long など）を使う必要があります。

アルゴリズム

1. 基本レシピの数 \(N\) と料理の数 \(M\) を入力から受け取る。
2. 基本レシピの点数 \(A_1, A_2, \ldots, A_N\) を配列（リスト）として格納する。
3. 合計得点を保持する変数 total_score を \(0\) で初期化する。
4. \(M\) 回のループを回し、各料理の情報 \((B_j, S_j)\) を受け取る。
5. total_score に \(A[B_j - 1] + S_j\) を加算する。
6. 最終的な total_score を出力する。

計算量

• 時間計算量: \(O(N + M)\)
  • レシピの入力に \(O(N)\)、料理の処理に \(O(M)\) かかります。
• 空間計算量: \(O(N)\)
  • 基本レシピの点数を保持するために長さ \(N\) の配列が必要です。

実装のポイント

• 高速な入出力: Pythonで入力行数が多い場合、input() を繰り返すと実行時間が長くなることがあります。sys.stdin.read().split() を使って全ての入力を一度に読み込み、リストとして処理することで、実行時間を大幅に短縮できます。

• 1-indexedへの対応: レシピ番号 \(B_j\) をそのまま配列のインデックスに使うと範囲外エラー（IndexError）になったり、間違ったレシピを参照したりするため、必ず -1 をして調整します。

  ソースコード

import sys

def solve():
    # 全ての入力を一度に読み込み、空白で分割してリストにする
    # これにより、大量の入力行を高速に処理できる
    input_data = sys.stdin.read().split()
    
    if not input_data:
        return
    
    # 基本レシピの数 N と料理の数 M を取得
    N = int(input_data[0])
    M = int(input_data[1])
    
    # 各基本レシピの基本点 A_i をリストとして取得
    # input_data[2] から input_data[2 + N - 1] までが A_1, ..., A_N
    # 0-indexed になるため、レシピ番号 b に対しては A[b-1] でアクセスする
    A = list(map(int, input_data[2:2+N]))
    
    total_score = 0
    
    # 料理の情報を順番に処理する
    # 各料理の情報 (B_j, S_j) は input_data[2 + N] 以降にペアで並んでいる
    current_ptr = 2 + N
    for _ in range(M):
        # ベースにするレシピの番号 B_j (1-indexed)
        b_j = int(input_data[current_ptr])
        # アレンジ点 S_j
        s_j = int(input_data[current_ptr + 1])
        
        # 料理の得点 = A[B_j - 1] + S_j を合計に加算
        total_score += A[b_j - 1] + s_j
        
        # 次の料理の情報へポインタを進める
        current_ptr += 2
        
    # 合計得点を出力
    print(total_score)

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-thinking によって生成されました。