競プロ典型90問 004 - Cross Sum

問題

競プロ典型90問　004 - Cross Sum

考察

全探索を考える

あるA_n,mに対してのB_n,mを求める計算量を考えます。
計算量は同じ行と同じ列の数字を全て足すのでH+Wになります。
そして全てのA_n,mに対してこの計算を行うのでH　× W × (H+W)となって間に合いません。(制約内の最大値で考えると1.6*10^10になってしまう)

各行と列の合計を先に出して仕舞えば良いのでは

行と列の合計を先に求めることによって
A_n,mがある行と列の合計を足してA_n,mを引く計算をするだけでB_n,mが求められる。

ソース

H,W = map(int,input().split())

A = [[0]*W for i in range(H)]
hSum = [0] * H
vSum = [0] * W

for i in range(H):
    workA = list(map(int,input().split()))
    for j in range(W):
        vSum[j] += workA[j] 
    hSum[i] = sum(workA)
    A[i] = workA

for i in range(H):
    ans = [0] * W
    for j in range(W):
        ans [j] = hSum[i] + vSum[j] - A[i][j]
    print(" ".join(list(map(str,ans))))

Python3だとTLEになってしまうようなのでPyPy3で提出しました。
調べてみるとPython3でもできないことはないようですが上位の人でもギリギリみたいなのでPyPy3で提出するのが無難かなと思いました。

最後に

★2ということですぐに方針はたったのですが、一度コードを書いた時に縦の列と横の列を足しただけのコードを書いてしまい、A_n,mが2回足されてしまうのを見落としてしまいました。
考察時点で気づけそうなミスには気をつけていきたいですね。
テストで気づけばまだ良いのですが、たまたま入力例がうまくいくパターンだった場合WAしてしまいますし。

次回の記事に関してですが、★6,★7はみてみたところ手も足も出なさそうだったので一度飛ばそうと思っています。次回の記事は006 - Smallest Subsequencになるかと思います。
それでも今までで最高難易度の★5なので心してかかりたいと思います。

以上、最後まで読んでいただきありがとうございました。