概要

この問題は、旅行中に行われた複数の支払い（立て替え）について、最終的な各個人の収支バランス（受け取るべき金額、または支払うべき金額）を計算する問題です。

考察

各支払いにおいて、収支に影響を与える要素は以下の2点です。 1. 立て替えた人のプラス分: 支払い金額 \(C_i\) を全額出したため、その分だけ収支がプラスになります。 2. 利用者のマイナス分: 利用した \(K_i\) 人は、均等に割った額 \(\frac{C_i}{K_i}\) を負担するため、その分だけ収支がマイナスになります。

この問題のポイントは、「誰がどれだけ得をしたか・損をしたか」を一人ずつシミュレーションしても間に合うかという点です。 制約を見ると、人数 \(N\) や支払い回数 \(M\) は \(10^5\) です。また、全支払いの延べ利用者数 \(\sum K_i\) も \(10^5\) 以下となっています。 したがって、各支払いごとに「立て替えた人に加算」し、「利用者全員から減算」するという処理を愚直に行っても、全体の計算回数は \(M + \sum K_i\) 程度（約 \(2 \times 10^5\) 回）となり、制限時間内に十分に間に合います。

アルゴリズム

1. 長さ \(N+1\) の配列（またはリスト） \(D\) を用意し、すべて \(0\) で初期化します。\(D[j]\) は人 \(j\) の現在の収支バランスを表します。
2. 各支払い \(i = 1, 2, \ldots, M\) について以下の処理を行います。
   • 立て替えた人 \(P_i\) の収支を更新する： \(D[P_i] \leftarrow D[P_i] + C_i\)
   • 1人あたりの負担額を計算する： \(share = \frac{C_i}{K_i}\)
   • 各利用者 \(B_{i,j}\) (\(j=1 \ldots K_i\)) について、収支を更新する： \(D[B_{i,j}] \leftarrow D[B_{i,j}] - share\)
3. すべての支払いを処理した後、\(D[1]\) から \(D[N]\) までの値を順番に出力します。

計算量

• 時間計算量: \(O(N + M + \sum K_i)\)
  • 配列の初期化に \(O(N)\)、各支払いの処理に \(O(1 + K_i)\) かかるため、全体の計算量は入力のサイズに対して線形です。
• 空間計算量: \(O(N)\)
  • 各個人の収支を保持するための配列 \(D\) のサイズが \(N\) に比例します。

実装のポイント

• 高速な入出力: 入力データ数が最大で数十万個に及ぶため、Python標準の input() を繰り返すと実行時間が長くなる可能性があります。sys.stdin.read().split() を使って一括で入力を取得し、リストから順に取り出す方法が効率的です。

• 整数の扱い: 問題文で \(\frac{C_i}{K_i}\) が整数になることが保証されているため、切り捨て除算 // を使用して整数のまま計算することで、浮動小数点数による誤差を避けることができます。

• 出力の効率化: \(N\) 行の出力を1つずつ print() するよりも、文字列のリストに変換して '\n'.join() で一気に出力する方が高速です。

  ソースコード

import sys

def main():
    # 旅行の立て替え精算の問題を解くためのメイン関数
    # sys.stdin.read().split() を使用して、入力を一括で取得しトークンに分割します
    # これにより、大量の入力データに対しても高速に処理することが可能です
    input_data = sys.stdin.read().split()
    
    # 入力が空の場合は終了します
    if not input_data:
        return
    
    # グループの人数 N と支払い回数 M を取得
    N = int(input_data[0])
    M = int(input_data[1])
    
    # 各人の精算バランスを格納するリスト D
    # D[j] は人 j の「実際に立て替えた合計金額」から「本来負担すべき合計金額」を引いた値
    # 人の番号は 1 から N であるため、サイズ N+1 のリストを用意します
    D = [0] * (N + 1)
    
    # 現在処理しているトークンのインデックス
    ptr = 2
    
    # M 回の支払い情報を順に処理
    for _ in range(M):
        # 立て替えた人の番号 P_i, 金額 C_i, 利用者数 K_i を取得
        p_i = int(input_data[ptr])
        c_i = int(input_data[ptr+1])
        k_i = int(input_data[ptr+2])
        ptr += 3
        
        # 立て替えた人 P_i の実際に支払った金額を加算
        D[p_i] += c_i
        
        # 利用者一人あたりの負担額を計算 (C_i / K_i)
        # 問題の制約により、この値は必ず整数になります
        share = c_i // k_i
        
        # 各利用者の本来負担すべき金額を減算
        # 利用者のリスト B_{i,1}, ..., B_{i,K_i} を順に処理
        for _ in range(k_i):
            b_ij = int(input_data[ptr])
            D[b_ij] -= share
            ptr += 1
            
    # 人 1 から N までの精算バランス D_j を文字列のリストに変換
    results = map(str, D[1:])
    
    # すべての結果を改行区切りで一気に出力
    sys.stdout.write('\n'.join(results) + '\n')

if __name__ == '__main__':
    main()

この解説は gemini-3-flash-thinking によって生成されました。