概要

旅行中の各支払いについて、立て替えた人と利用した人の間で金銭のやり取りを整理し、各人が最終的に受け取るべき（または支払うべき）金額を求める問題です。

考察

各人について知りたいのは「実際に立て替えた合計金額」から「本来負担すべき合計金額」を引いた差額 \(D_j\) です。

具体例で考えてみましょう。3人グループで、人1が900円を立て替え、利用者が人1・人2・人3だったとします。

• 人1は900円を立て替えた → \(D_1\) に \(+900\)
• 一人あたりの負担額は \(900 \div 3 = 300\) 円
• 人1, 人2, 人3 それぞれの \(D\) から \(300\) を引く

結果：\(D_1 = 900 - 300 = 600\)、\(D_2 = -300\)、\(D_3 = -300\)

つまり人1は600円を受け取るべきで、人2と人3はそれぞれ300円を支払うべきです。

このように、各支払いごとに以下の2つの処理を行えばよいことが分かります：

1. 立て替えた人 \(P_i\) の \(D\) に \(C_i\) を加算する
2. 利用した各人 \(B_{i,k}\) の \(D\) から負担額 \(\frac{C_i}{K_i}\) を減算する

素朴に全支払い・全利用者を走査しても、制約で \(\sum_{i=1}^{M} K_i \leq 10^5\) と保証されているため、利用者の走査にかかる合計回数は高々 \(10^5\) 回です。特別な工夫なくそのまま実装すれば十分高速に動作します。

アルゴリズム

1. 長さ \(N+1\) の配列 \(D\) を \(0\) で初期化する（1-indexed で使うため）。
2. 各支払い \(i = 1, 2, \ldots, M\) について：
   • 立て替えた人 \(P_i\) に対して \(D[P_i]\) に \(C_i\) を加算する。
   • 一人あたりの負担額 \(\text{share} = C_i \div K_i\) を計算する。
   • 利用者リスト \(B_{i,1}, \ldots, B_{i,K_i}\) の各人 \(b\) について、\(D[b]\) から \(\text{share}\) を減算する。
3. \(j = 1, 2, \ldots, N\) の順に \(D[j]\) を出力する。

計算量

• 時間計算量: \(O(N + \sum_{i=1}^{M} K_i)\)
  • 各支払いの処理は立て替え者への加算（\(O(1)\)）と利用者への減算（\(O(K_i)\)）で、合計 \(O(\sum K_i)\)。出力に \(O(N)\)。
• 空間計算量: \(O(N + \sum_{i=1}^{M} K_i)\)
  • 配列 \(D\) に \(O(N)\)、入力の読み込みに \(O(\max K_i)\)（各行ごとに処理するため）。

実装のポイント

• 入力の高速化: Pythonでは sys.stdin.readline を使うことで入力を高速に読み込めます。\(M\) や \(K_i\) が大きい場合に効果があります。

• 1行にまとめて与えられる入力の扱い: 各支払い行には \(P_i, C_i, K_i\) に続いて \(K_i\) 個の利用者番号が並んでいます。まとめて list(map(int, input().split())) で読み込み、スライスで分割するのが簡潔です。

• 整数除算: \(\frac{C_i}{K_i}\) は整数であることが保証されているので、Pythonでは C // K で安全に計算できます。

• 立て替えた人が利用者に含まれる場合: 立て替えた人自身も利用者であるケースがあります。その場合、加算と減算の両方が適用されますが、特別な場合分けは不要で、そのまま正しく計算されます。

  ソースコード

import sys
input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    D = [0] * (N + 1)
    for _ in range(M):
        parts = list(map(int, input().split()))
        P = parts[0]
        C = parts[1]
        K = parts[2]
        B = parts[3:3 + K]
        D[P] += C
        share = C // K
        for b in B:
            D[b] -= share
    for j in range(1, N + 1):
        print(D[j])

main()

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