概要

入荷予定の \(N\) 個の荷物のうち、キャンセルされなかった荷物について、それぞれの重さを \(K\) で割った値（小数点以下切り捨て）を求め、その合計を算出する問題です。

考察

この問題を解くために必要なステップは以下の3点です。

1. どの管理番号の荷物がキャンセルされたかを正確に把握する。
2. キャンセルされなかった荷物を特定し、それぞれの「ユニット数」を計算する。
3. 計算したユニット数の総和を求める。

ここで注意すべきは制約です。荷物の数 \(N\) は最大で \(2 \times 10^5\) と比較的大きいため、効率的な処理が求められます。

例えば、ある管理番号 \(i\) がキャンセルされたかどうかを判定する際、キャンセルリスト \(D\) を毎回最初から最後まで探すと、1回の判定に最大 \(O(M)\) の時間がかかります。これを \(N\) 回繰り返すと全体の計算量は \(O(N \times M)\) となり、最大で \(4 \times 10^{10}\) 回程度の計算が必要になるため、実行時間制限（TLE）に間に合いません。

この問題を解決するために、「管理番号 \(i\) がキャンセルされたか」を \(O(1)\) で判定できる工夫が必要です。具体的には、真偽値（boolean）の配列やハッシュセット（Pythonの set など）を利用します。

アルゴリズム

以下の手順で解を進めます。

1. 入力の受け取り: \(N, M, K\) および重さのリスト \(T\)、キャンセルされた番号のリスト \(D\) を読み込みます。
2. キャンセル情報の整理: 長さ \(N+1\) の配列 is_canceled を用意し、初期値をすべて False にします。リスト \(D\) に含まれる番号 \(d\) について、is_canceled[d] = True と更新します。
3. ユニット数の計算と合計:
   • \(i = 1\) から \(N\) まで順番に確認します。
   • もし is_canceled[i] が False であれば、その荷物は届いています。
   • 届いた荷物の重さ \(T_i\) を用いて、ユニット数 \(\lfloor T_i / K \rfloor\) を計算し、合計値に加算します。
   • Pythonでは // 演算子を使うことで、整数除算（小数点以下切り捨て）が簡単に行えます。
4. 結果の出力: 最終的な合計値を出力します。

計算量

• 時間計算量: \(O(N + M)\)
  • 入力の読み込みに \(O(N + M)\)、キャンセル情報の配列作成に \(O(M)\)、ユニット数の合計計算に \(O(N)\) かかります。\(N, M \le 2 \times 10^5\) なので、十分高速に動作します。
• 空間計算量: \(O(N)\)
  • 荷物の重さを保存するリストや、キャンセル判定用の配列に \(O(N)\) のメモリを使用します。

実装のポイント

• 高速な入出力: \(N\) や \(M\) が大きいため、Pythonでは sys.stdin.read().split() を使って一度にすべての入力を取得し、リストとして扱うことで実行時間を短縮しています。

• インデックスの管理: 荷物の管理番号は \(1\) から始まりますが、プログラミング言語の配列は通常 \(0\) から始まります。管理番号 \(i\) と配列のインデックスの対応関係（i なのか i-1 なのか）を間違えないように注意が必要です。

• 大きな数値の扱い: ユニット数の合計値は非常に大きな数になる可能性がありますが、Pythonは標準で多倍長整数をサポートしているため、オーバーフローを気にせず計算できます。

  ソースコード

import sys

def solve():
    # 全ての入力を一度に読み込み、空白（スペース、改行）で分割してリスト化します。
    # N, M, K が最大で 2*10^5 程度の規模であれば、この方法が効率的です。
    input_data = sys.stdin.read().split()
    
    # 入力が空の場合の例外処理
    if not input_data:
        return
    
    # 1行目の N (荷物の総数), M (キャンセル数), K (1ユニットの重さ) を取得
    N = int(input_data[0])
    M = int(input_data[1])
    K = int(input_data[2])
    
    # 荷物の重さ T_i は input_data のインデックス 3 から N 個分
    # キャンセルされた管理番号 D_j はインデックス 3 + N から M 個分
    
    # キャンセルされた管理番号を効率よく判定するため、boolean 配列を作成
    # 管理番号は 1 から N なので、サイズ N + 1 の配列を用意します。
    is_canceled = [False] * (N + 1)
    for i in range(3 + N, 3 + N + M):
        d = int(input_data[i])
        is_canceled[d] = True
    
    total_units = 0
    # 各荷物について、キャンセルされていなければユニット換算して加算
    for i in range(N):
        management_id = i + 1
        if not is_canceled[management_id]:
            # 重さ T_i は input_data[3 + i] に格納されている
            weight = int(input_data[3 + i])
            # 小数点以下切り捨て（整数除算）
            total_units += weight // K
            
    # 最終的な総和を出力
    print(total_units)

if __name__ == '__main__':
    solve()

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