概要
競プロ典型90問の解説記事です。
解説の画像を見ても分からない（理解力が足りない）ことが多々あったので、後で解き直した際に確認できるようまとめました。
※順次、全ての問題の解説記事を挙げていく予定です。
※★５以上の問題は難易度的に後回しにしているため、投稿時期が遅くなる可能性があります。（代わりに丁寧に解説してくれる方いたらぜひお願いします）
問題004-Cross Sum
問題概要
マス(i, j)と同じ行、同じ列にあるマスの合計値を全てのマスで求める。
制約
2 <= H, W <= 2000 \\
1 <= Ai <= 99 \\
・入力は全て整数。
解き方
まず初めに、全てのマスにおいて、順番に合計値を求めていく方法が考えられるかと思います。
この考えでは、マスの総数が$HW ≒ 10^6$で各マスにおける処理が$H+W ≒ 10^3$となるため、TLEになってしまいmます。
上記の方法では、各行、各列の合計を繰り返し求めてしまっています。
そこで、今回は、あらかじめ各行、各列の合計を求めておき、それらの組み合わせを全てのマスにおいて、求める手段をとります。（この方法では、A[i][j]が二重に足されるため、１つ分減算する点にご注意ください。）
実装の流れは以下になります。
- 各行H、列Wの和をそれぞれ求める。
- マス i, j と同じ行、同じ列にあるマスの合計値を求める。
1の処理でも２の処理でも$HW$、
すなわち $10^6$ のオーダーで求められるので、十分に間に合います。
引用元：競プロ典型90問 Github
実装
# 入力の受け取り
H, W = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
# 各行の和をLに格納する
L = []
for i in range(H):
L.append(sum(B[i]))
# 各列の和をRに格納する
R = []
for i in range(W):
cnt = 0
for j in range(H):
cnt += B[j][i]
R.append(cnt)
# 各マスにおいての行と列の合計値を求め、二重に加算されているA[i][j]を減算する。
B = []
for i in range(H):
l = []
for j in range(W):
sums = L[i] + R[j] - A[i][j]
l.append(sums)
B.append(l)
# 答えを出力する
for i in range(H):
print(*B[i])
最後に
今回の問題は、必要な値を事前に計算することが大きなポイントでした。
問題の解説を読んでも他の人のコードを見てもさっぱり分からないという方の
力に少しでもなれれば幸いです。
コードの改善点やその他、ご意見などあれば、気軽にコメントください。
また、この記事を読んで理解できた方はぜひLGTMを押していただけると嬉しいです。
（記事投稿のモチベになります。）
ここまでお読みいただきありがとうございました。