概要

キャンセルされなかった荷物について、各荷物の重さをユニット数（重さを \(K\) で割って切り捨てた値）に変換し、その総和を求める問題です。

考察

問題の整理

• \(N\) 個の荷物があり、そのうち \(M\) 個がキャンセルされる
• 届いた荷物（\(N - M\) 個）それぞれについてユニット数 \(\lfloor T_i / K \rfloor\) を計算し、合計を求める

キャンセル判定の効率化

荷物が届いたかどうかを判定するために、毎回キャンセルリスト \(D\) を線形探索すると、1回の判定に \(O(M)\) かかり、全体で \(O(N \times M)\) となってしまいます。

例: \(N = 200,000\)、\(M = 100,000\) の場合、最悪で \(2 \times 10^{10}\) 回の比較が必要になり、TLE（時間超過）の原因になります。

解決策：集合（set）を使う

キャンセルされた管理番号を集合（set）に格納すれば、ある番号がキャンセルされたかどうかを平均 \(O(1)\) で判定できます。これにより全体の計算量を大幅に削減できます。

アルゴリズム

1. \(N\), \(M\), \(K\) を読み込む
2. 各荷物の重さ \(T_1, T_2, \ldots, T_N\) を配列に格納する
3. キャンセルされた管理番号 \(D_1, D_2, \ldots, D_M\) を集合に格納する
4. 管理番号 \(1\) から \(N\) まで順に以下を行う：
   • 管理番号が集合 \(D\) に含まれていなければ（キャンセルされていなければ）、ユニット数 \(\lfloor T_i / K \rfloor\) を合計に加算
5. 合計を出力する

具体例： - \(N=5\), \(M=2\), \(K=100\) - \(T = [250, 80, 350, 120, 500]\) - \(D = \{2, 4\}\)（管理番号2と4がキャンセル）

届く荷物は管理番号 1, 3, 5： - 番号1: \(\lfloor 250 / 100 \rfloor = 2\) - 番号3: \(\lfloor 350 / 100 \rfloor = 3\) - 番号5: \(\lfloor 500 / 100 \rfloor = 5\)

合計: \(2 + 3 + 5 = 10\)

計算量

• 時間計算量: \(O(N + M)\)
  • 集合の構築に \(O(M)\)
  • 各荷物の判定と計算に \(O(N)\)（集合への所属判定は平均 \(O(1)\)）
• 空間計算量: \(O(N + M)\)
  • 重さの配列に \(O(N)\)
  • キャンセル集合に \(O(M)\)

実装のポイント

1. 集合（set）の活用: Pythonでは set() を使うことで、要素の存在判定を高速に行えます。in 演算子でリストを検索すると \(O(M)\) ですが、集合なら平均 \(O(1)\) です。

2. \(M = 0\) のケース: キャンセルがない場合、3行目が入力に存在しません。この例外的な入力形式に対応するため、try-except で入力を処理しています。

3. 管理番号の1-indexedに注意: 配列は0-indexedですが、管理番号は1から始まります。T[i] は管理番号 \(i+1\) の荷物の重さを表すため、ループ内で management_number = i + 1 として対応しています。

4. 整数除算: Pythonでは // 演算子で切り捨て除算ができます。これは \(\lfloor a / b \rfloor\) に相当します。

   ソースコード

def main():
    line1 = input().split()
    N, M, K = int(line1[0]), int(line1[1]), int(line1[2])
    
    T = list(map(int, input().split()))
    
    if M > 0:
        D = set(map(int, input().split()))
    else:
        # M=0の場合、3行目が空行または存在しない可能性がある
        try:
            line3 = input().split()
            D = set(map(int, line3)) if line3 else set()
        except:
            D = set()
    
    total = 0
    for i in range(N):
        management_number = i + 1
        if management_number not in D:
            total += T[i] // K
    
    print(total)

if __name__ == "__main__":
    main()

---

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