概要

各人が立て替えた金額と、自分が負担すべき金額の差を計算する問題。

考察

この問題では、各支払いごとに「誰がいくら立て替えたか」「誰がどれだけ負担すべきか」を記録し、最終的に各人ごとの差分 \(D_j\) を求めます。

素朴な方法として、毎回の支払いに対して、利用者全員に負担額を加算していく方法が考えられます。しかし、これでも十分高速です。重要なのは、入力を高速に読み込むことと、計算を効率的に行うことです。

各支払いにおいて、立て替え人は1人、利用者は複数いるので、立て替えた金額をその人に加算し、利用者それぞれに負担額（\(C_i / K_i\)）を加算します。制約より、\(\frac{C_i}{K_i}\) は常に整数です。

この処理を愚直に行うだけで十分間に合います。ただし、入力のパースが遅いとTLEする可能性があるため、高速な入力方法を使用します。

アルゴリズム

1. 各人について、「実際に立て替えた金額」と「本来負担すべき金額」を記録する配列を用意する。
2. 各支払いごとに以下を行う：
   • 立て替えた人 \(P_i\) の「実際に立て替えた金額」に \(C_i\) を加える。
   • 各利用者 \(B_{i,j}\) の「本来負担すべき金額」に \(\frac{C_i}{K_i}\) を加える。
3. 最後に、各人について「立て替えた金額 − 負担すべき金額」を計算して出力する。

計算量

• 時間計算量: \(O(M + \sum K_i)\)
• 空間計算量: \(O(N + \sum K_i)\)

※ \(\sum K_i \leq 10^5\) なので、十分高速。

実装のポイント

• 高速な入力が必要なため、sys.stdin.read を使って一度に読み込むと良い。
• actual_paid, should_pay の添字は1-indexedで扱うため、サイズは \(N+1\) にする。
• 各支払いの負担額は整数であることが保証されているため、そのまま割り算で計算可能。

## ソースコード

```python
import sys
input = sys.stdin.read

def main():
    data = input().split()
    idx = 0
    N = int(data[idx])
    idx += 1
    M = int(data[idx])
    idx += 1
    
    # D[j] = 実際に立て替えた金額 - 本来負担すべき金額
    actual_paid = [0] * (N + 1)
    should_pay = [0] * (N + 1)
    
    for _ in range(M):
        P = int(data[idx])
        idx += 1
        C = int(data[idx])
        idx += 1
        K = int(data[idx])
        idx += 1
        burden = C // K
        actual_paid[P] += C
        for __ in range(K):
            b = int(data[idx])
            idx += 1
            should_pay[b] += burden
            
    for j in range(1, N + 1):
        D = actual_paid[j] - should_pay[j]
        print(D)

if __name__ == "__main__":
    main()

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