概要

\(N\) 個の荷物のうち \(M\) 個がキャンセルされたとき、残った荷物の重さをある単位（ユニット）に変換した合計を求めます。

考察

この問題では、各荷物の重さ \(T_i\) を \(K\) で割った値（小数点以下切り捨て）であるユニット数 \(\lfloor T_i / K \rfloor\) を求め、キャンセルされなかった荷物のユニット数の合計を出力します。

素朴な方法としては、まずキャンセルされた荷物のリストを配列で持ち、各荷物に対して「その荷物がキャンセルされているか？」を毎回線形探索する方法があります。しかし、この方法では各荷物について最大 \(M\) 回の比較が必要になるため、全体で最大 \(O(N \times M)\) の計算量となり、最悪ケース（\(N, M = 2 \times 10^5\)）では時間内に処理しきれません（TLE）。

そこで、キャンセルされた荷物の管理番号を集合（set）に格納することで、「ある荷物がキャンセルされたか？」という判定を高速に行えるようにします。集合への要素追加や検索は平均的に \(O(1)\) で行えるため、全体の計算量を大きく削減できます。

さらに、Python では標準入力を高速に行うために sys.stdin.read を使用するのが一般的であり、今回のコードでも採用されています。

アルゴリズム

1. 入力を一度に読み込み、分割して変数に格納します。
2. 各荷物の重さ \(T_i\) をリストとして保持します。
3. キャンセルされた荷物の管理番号 \(D_j\) をセット（set）に格納します。
4. 各荷物について、管理番号（1-indexed）がキャンセルリストに含まれていない場合に限り、\(\lfloor T_i / K \rfloor\) を合計に加えます。
5. 最終的な合計を出力します。

計算量

• 時間計算量: \(O(N + M)\)
  （各荷物の処理が \(O(1)\) で、荷物の数 \(N\)、キャンセル数 \(M\)）
• 空間計算量: \(O(N + M)\)
  （荷物のリストとキャンセル番号のセットを保持）

実装のポイント

• キャンセルされた荷物の管理番号をリストではなく set で持つことで、高速な存在判定を実現。

• 管理番号は1-indexedなので、0-indexedのリストインデックスを使うときは i + 1 と比較する必要がある。

• 入力の高速化のために sys.stdin.read を使用している。

• \(M = 0\) の場合も正しく動作するように、空のsetに対して常に not in が True になる点に注意。

  ソースコード

import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    M = int(data[1])
    K = int(data[2])
    
    T = list(map(int, data[3:3+N]))
    
    D = set(map(int, data[3+N:3+N+M]))
    
    total_units = 0
    for i in range(N):
        if (i + 1) not in D:
            total_units += T[i] // K
    
    print(total_units)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。