【競プロ典型90問】004の解説（python） - Qiita

概要 競プロ典型90問の解説記事です。 解説の画像を見ても分からない（理解力が足りない）ことが多々あったので、後で解き直した際に確認できるようまとめました。 ※順次、全ての問題の解説記事を挙げていく予定です。 ※★５以上の問題は難易度的に後回しにしているため、投稿時期が遅くなる可能性があります。（代わりに丁寧に解説してくれる方いたらぜひお願いします） 問題004-Cross Sum 問題概要 マス(i, j)と同じ行、同じ列にあるマスの合計値を全てのマスで求める。 制約 ・入力は全て整数。 解き方 まず初めに、全てのマスにおいて、順番に合計値を求めていく方法が考えられるかと思います。 この考えでは、マスの総数が$HW ≒ 10^6$で各マスにおける処理が$H+W ≒ 10^3$となるため、TLEになってしまいmます。 上記の方法では、各行、各列の合計を繰り返し求めてしまっています。 そこで