概要

各支払いについて「立て替えた人はプラス」「利用した人は均等割り分をマイナス」として差額 \(D_j\) を加算していき、最終的な \(D_1,\dots,D_N\) を求める問題です。

考察

求めたい \(D_j\) は

• 実際に立て替えた合計（自分が支払った分の合計）
• 本来負担すべき合計（利用した支払いの均等割りの合計）

の差です。

ここで重要なのは、各支払いを独立に見て、\(D\) に直接足し引きしていけばよいという点です。

支払い \(i\) を考えると：

• 立て替えた人 \(P_i\) は、その場で \(C_i\) 円払っているので \(D_{P_i}\) に \(+C_i\)
• 利用者は \(K_i\) 人で均等負担なので、利用者一人あたりの負担額は \(\frac{C_i}{K_i}\)
  • よって各利用者 \(b\) について \(D_b\) に \(-\frac{C_i}{K_i}\)

これを全支払いについて合計すれば、そのまま定義通りの \(D_j\) になります。

素朴なアプローチが危ない点

例えば「各人が誰にいくら払うか」まで取引を組み立てようとすると、人数が多いと管理が複雑になりがちです。しかしこの問題は 最終差額 \(D_j\) だけ分かればよく、取引の具体的な経路は不要です。

また、利用者全員に均等割りを配る処理は必要ですが、制約で \(\sum K_i \le 10^5\) が保証されているため、利用者に対するループ総回数も最大 \(10^5\) 回に抑えられ、十分高速に処理できます。

（例） - 3人いて、ある支払いで 1番が \(C=600\) 円立て替え、利用者が {1,2,3}（\(K=3\)）なら - \(D_1 += 600\) - 各利用者に \(-200\) ずつ → \(D_1 -=200, D_2 -=200, D_3 -=200\) - 結果：\(D_1=+400, D_2=-200, D_3=-200\)（1番が400円受け取り、2・3番が200円支払い）

アルゴリズム

1. 配列 \(D[1..N]\) を \(0\) で初期化する。
2. 各支払い \((P_i, C_i, K_i, B_{i,1..K_i})\) について：
   1. \(D[P_i] \mathrel{+}= C_i\)
   2. \(\text{share} = \frac{C_i}{K_i}\)（整数になる保証あり）
   3. 利用者 \(b \in \{B_{i,1},\dots,B_{i,K_i}\}\) それぞれに対し \(D[b] \mathrel{-}= \text{share}\)
3. 最後に \(D[1], D[2], \dots, D[N]\) を出力する。

この方法は定義通りに「立て替え＝プラス」「負担＝マイナス」を積み上げているだけなので、正しく \(D_j\) が求まります。

計算量

• 時間計算量: \(O\!\left(N + M + \sum_{i=1}^{M} K_i\right)\)（実質 \(O(N + M + 10^5)\)）
• 空間計算量: \(O(N)\)

実装のポイント

• \(C_i\) は最大 \(10^9\)、支払い回数もあるので \(D_j\) は大きくなり得ます。Python の int なら問題ありません（他言語なら 64bit 整数推奨）。

• 入力サイズが大きいので、sys.stdin.buffer.read() でまとめて読み、整数列として処理すると高速です。

• 人の番号が \(1..N\) なので、配列は N+1 サイズにして 1-index で扱うと実装が簡単です。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    M = next(it)

    D = [0] * (N + 1)

    for _ in range(M):
        P = next(it)
        C = next(it)
        K = next(it)
        D[P] += C
        share = C // K
        for _ in range(K):
            b = next(it)
            D[b] -= share

    out = "\n".join(str(D[i]) for i in range(1, N + 1))
    sys.stdout.write(out)

if __name__ == "__main__":
    main()

---

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