【競プロ典型90問】「004 - Cross Sum(★2)」解法

このシリーズではE869120さんによって作成された競プロ典型90問をPythonで解いています。

問題

004 - Cross Sum(★2)

ポイント

1つ1つのマスに対して都度行と列の合計を計算して足し合わせる方法ではTLEとなってしまうため、

 ①最初に行の合計をリストで作成

 ②そのリストに列の合計を合算(その際、重複しているマスの値を引く)

という手順で解を求めます。

入力例2の場合:

①最初に行の合計をリストで作成

②そのリストに列の合計を合算(その際、重複しているマスの値を引く)

コード

def main():
    import sys
    sys.setrecursionlimit(10 ** 6)
    input = sys.stdin.readline

    # インプットの処理
    H, W = map(int, input().split(" "))
    masu = [list(map(int, input().split(" "))) for _ in range(H)]


    ans = []
    # ①最初に行の合計をリストで作成
    for i in range(H):
        row_sum = sum(masu[i])
        ans.append([row_sum] * W)

    # ②そのリストに列の合計を合算(その際、重複しているマスの値を引く)
    for j in range(W):
        col_sum = 0
        for i in range(H):
            col_sum += masu[i][j]  # 縦の列の合計を求める

        for i in range(H):
            ans[i][j] += col_sum - masu[i][j]  # 縦の列の合計を足す※重複したマスの値を引く

    # 解答の出力
    for a in ans:
        print(*a)


if __name__ == '__main__':
    main()

おすすめの記事