概要

各都市に必要な電力量と、送電線を通じて供給できる電力量が与えられるので、電力が足りていない都市の数を求めます。

考察

この問題では、各都市に対して、その都市に接続されている送電線の送電容量の合計（供給可能電力量 \(T_i\)）を求め、それが需要量 \(S_i\) を下回っているかどうかを判定する必要があります。

素朴な方法として、各送電線について両端の都市に容量を加算していく方法があります。しかし、単純に毎回配列に加算していったとしても、都市数 \(N\) と送電線数 \(M\) が最大 \(2 \times 10^5\) なので、全体で最大 \(2 \times 10^5\) 回の加算処理が必要になります。これは十分高速に処理できますが、加算のたびにリスト操作を行うと遅くなる可能性があります。特にPythonのようにリスト操作が重い言語では、標準入力の処理も含めて高速化が必要です。

この問題では、各送電線の情報を読み取りながら、各都市に供給される電力の総和を累積的に計算していけば良いです。つまり、各送電線の両端の都市に対応する配列の値に、その送電容量を加算していくだけです。その後、各都市ごとに供給可能電力量 \(T_i\) と需要量 \(S_i\) を比較すれば答えが得られます。

アルゴリズム

1. 各都市の需要量 \(S_i\) を読み込む。
2. 各送電線について、結ばれている都市 \(U_j\) と \(V_j\) の両方に送電容量 \(W_j\) を加算する（\(T_{U_j}\) と \(T_{V_j}\) に加算）。
3. 各都市 \(i\) に対して、\(T_i < S_i\) であればカウントを増やす。
4. カウントした数を出力する。

計算量

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

※ 各送電線について両端の都市を更新する操作が \(O(1)\) で行えるため、全体で \(O(M)\)。最後に全都市を走査するのに \(O(N)\) かかります。

実装のポイント

• 入力が非常に多いので sys.stdin.read を使って高速に読み込む。

• 都市番号は1-indexedで与えられるので、内部では0-indexedに変換して扱う（\(U_j - 1\), \(V_j - 1\)）。

• 供給可能電力量を保持する配列 \(T\) は最初ゼロで初期化しておく。

  ソースコード

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
    
    S = [int(data[idx + i]) for i in range(N)]
    idx += N
    
    T = [0] * N
    for _ in range(M):
        U = int(data[idx]) - 1
        idx += 1
        V = int(data[idx]) - 1
        idx += 1
        W = int(data[idx])
        idx += 1
        T[U] += W
        T[V] += W
    
    count = 0
    for i in range(N):
        if T[i] < S[i]:
            count += 1
    
    print(count)

if __name__ == "__main__":
    main()

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