競プロ典型90問：004 - Cross Sum（★2）

問題

https://atcoder.jp/contests/typical90/tasks/typical90_d

挑戦結果

• 結果：解けた
• 時間：15分ぐらい

考えたこと

• 愚直に計算するとTLEなんだろうと思った
• 事前に縦と横で集計しておくと、$縦合計+横合計-A[i][j]$ で$B[i][j]$が求まると気がついた

解説を読んだふりかえり

• デバッグで思ったより時間がかかってしまった
• 愚直にやった場合の計算量も計算してみようと思った。

ソース

H, W = [int(x) for x in input().split()]
A = [[int(x) for x in input().split()] for _ in range(H)]
# 縦と横の合計
sumH = [0] * W
sumW = [0] * H
# 横についての合計
for i in range(H):
    for j in range(W):
        sumW[i] += A[i][j]
# 縦についての合計
for j in range(W):
    for i in range(H):
        sumH[j] += A[i][j]
# 縦方向の合計＋横方向の合計 - A[i][j]
for i in range(H):
    L = []
    for j in range(W):
        L.append(str(sumH[j] + sumW[i] - A[i][j]))
    print(" ".join(L))