概要

旅行中の複数回の支払い情報から、各人が最終的に受け取るべき金額、または支払うべき金額を計算する問題です。

考察

各支払いについて、以下の2つの情報を管理する必要があります： 1. 立て替えた人が実際に支払った金額（\(P_i\) が \(C_i\) 円を支払った） 2. 各利用者が本来負担すべき金額（\(\frac{C_i}{K_i}\) 円）

素朴なアプローチでは、各支払いごとにすべての利用者に対して処理を行うと、\(M\)回の支払いと各支払いの利用者数\(K_i\)の合計が最大\(10^5\)であるため、十分効率的に処理できます。

アルゴリズム

1. 各人\(j\)の精算額\(D_j\)を0で初期化する配列を用意する
2. 各支払い情報について：
   • 立て替えた人\(P_i\)の\(D\)値に\(C_i\)を加算する（立て替えた金額分）
   • その支払いの利用者全員の\(D\)値から\(\frac{C_i}{K_i}\)を減算する（負担すべき金額分）
3. すべての支払い処理後、各人の\(D_j\)を出力する

\(D_j\)が正の場合、その人は\(D_j\)円を受け取るべきであり、負の場合は\(|D_j|\)円を支払うべきことを意味します。

計算量

• 時間計算量: \(O(\sum_{i=1}^{M} K_i)\)
• 空間計算量: \(O(N)\)

実装のポイント

• 入力データを一度に読み込むことで効率化

• 各支払いの利用者リストを順次処理

• 整数除算を使用（問題文で\(\frac{C_i}{K_i}\)が整数であることが保証されている）

• 人番号が1-indexedなので、配列のサイズを\(n+1\)で確保

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    
    n = int(data[0])
    m = int(data[1])
    index = 2
    
    D = [0] * (n + 1)
    
    for _ in range(m):
        P = int(data[index]); index += 1
        C = int(data[index]); index += 1
        K = int(data[index]); index += 1
        per_person = C // K
        
        for i in range(K):
            person = int(data[index]); index += 1
            D[person] -= per_person
        
        D[P] += C
    
    for j in range(1, n + 1):
        print(D[j])

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。