概要

キャンセルされなかった荷物について、重さ \(T_i\) を \(K\) で割った整数部分 \(\lfloor T_i / K \rfloor\) を合計して出力します。

考察

各荷物 \(i\) のユニット数は \(\lfloor T_i / K \rfloor\) で、届かない（キャンセルされた）荷物の番号集合 \(\{D_1,\dots,D_M\}\) に含まれるものは合計から除外します。

ここで重要なのは「荷物 \(i\) がキャンセルされたか」を高速に判定することです。

• 素朴に、各荷物 \(i\) について \(D_1,\dots,D_M\) を順番に探す（線形探索）と、最悪で \(N \times M\) 回比較することになり、\(N,M \le 2\times 10^5\) なので最大で約 \(4\times 10^{10}\) 回となりTLEになります。
• そこで、キャンセル番号を 集合（set） に入れておき、各荷物番号 \(i\) がその集合に含まれるかを平均 \(O(1)\) で判定します。

具体例： - \(K=10\), \(T=[5, 23, 40]\), キャンセルが \(D=[2]\) のとき
- 1番: \(5//10=0\)（加算）
- 2番: キャンセル（除外）
- 3番: \(40//10=4\)（加算）
合計は \(0+4=4\) になります。

アルゴリズム

1. 入力で \(N,M,K\) と配列 \(T\) を受け取る。
2. キャンセル番号列 \(D\)（\(M>0\) のとき）を読み、集合 canceled = set(D) を作る。
3. \(i=1..N\) について以下を行う：
   • もし \(i \notin canceled\) なら、total += T[i] // K を加算する。
4. total を出力する。

計算量

• 時間計算量: \(O(N+M)\)（集合の構築が \(O(M)\)、各荷物の判定と加算が \(O(N)\)）
• 空間計算量: \(O(M)\)（キャンセル番号集合）

実装のポイント

• 荷物番号は問題文で \(1\) 始まりなので、enumerate(T, start=1) のようにして番号を合わせるとミスを防げます。

• \(M=0\) のときは3行目が存在しないため、sys.stdin.buffer.read().split() でまとめて読み、必要な個数だけ切り出す実装にすると安全です。

• 合計値は最大で \(N \times (10^9 // 1) \approx 2\times 10^{14}\) になり得ますが、Pythonの int は桁あふれしないのでそのまま扱えます。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    N, M, K = data[0], data[1], data[2]
    T = data[3:3 + N]
    D = data[3 + N:3 + N + M]
    canceled = set(D)

    total = 0
    for i, t in enumerate(T, start=1):
        if i not in canceled:
            total += t // K

    print(total)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。