【AtCoder】競プロ典型90問 004 - Cross Sum（★2）

004 - Cross Sum（★2）

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

AtCoder

実行時間制限: 5 sec / メモリ制限: 1024 MiB / Difficulty: 399 / NoviSteps: 4Q / 配点: 2 点

問題概要

$H$ 行 $W$ 列のマス目があり、上から $i$ 行目、左から $j$ 列目にあるマス $(i, j)$ には、整数 $A_{i, j}$ が書かれている。

すべてのマス $(i, j)$ について、以下の値を求めよ。

• マス $(i, j)$ と同じ行または同じ列にあるマス(自分自身を含む)に書かれている整数をすべて合計した値

制約

• $2 \leq H, W \leq 2000$
• $1 \leq A_{i, j} \leq 99$
• 入力は全て整数

考察

全ての $HW$ マスそれぞれについて、同じ行または同じ列にあるマスを探索して合計を求めるという愚直な解法がまず思いつくだろう。

しかし、これでは計算量が $O(HW(H+W))$ となり、今回の制約では TLE してしまう。

これは、各マスごとに同じ行・列の和を何度も計算していることが原因である。

そこで、事前に各行・列の総和 $r_i, c_j$ をそれぞれ前計算しておき、各マス $(i, j)$ については

を答えとして出力することにする。

これなら計算量は $O(HW)$ となり、十分に高速である。

実装例

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
5. 
6.// ======================================== //
7. 
8.int main()
9.{
10.    int H, W;
11.    cin >> H >> W;
12.    vector<vector<int>> A(H, vector<int>(W));
13.    rep(i, 0, H) rep(j, 0, W) cin >> A[i][j];
14. 
15.    vector<int> rows(H), cols(W);
16.    rep(i, 0, H) rep(j, 0, W)
17.    {
18.        rows[i] += A[i][j];
19.        cols[j] += A[i][j];
20.    }
21. 
22.    rep(i, 0, H) rep(j, 0, W)
23.    {
24.        cout << rows[i] + cols[j] - A[i][j] << ' ';
25.    }
26.    cout << endl;
27.}

Submission #70696659 - 競プロ典型 90 問

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

AtCoder

実装時間: 10 分

コメント

これは包除原理の考え方を利用しているが、意外と馬鹿にできないテクニックである。