---
# System prepended metadata

title: AtCoder Beginner Contest 176 題解
tags: [Programming Contest]

---

---
tags: Programming Contest
---

# AtCoder Beginner Contest 176 題解

[題目連結](https://atcoder.jp/contests/abc176/tasks)

## 心得

很可惜沒在時間內解出第五題，想到正確方法，但來不及寫出來，還好最終有加到 rating。

## A, B, C

都是簽到題，手速拼起來。

## D. Wizard in Maze

一開始就想到可以轉換成最短路徑：每個點與 moveA 的點建成本為 0 的邊，與 moveB 建成本為 1 的邊，求起點與終點的最短路徑長度。

最一開始想到 scipy 中有 sparse matrix 與 dijkstra 可以直接拿來用，所以就用 python 寫了一個版本。但範測一直過不了，最後只好轉用 c++ 寫。

賽後研究才發現是 scipy 的 sparse matrix (csr_matrix) 在處理 duplicated entries 跟我想得不一樣，他是累加在一起。修掉這問題後，大部份測資會 AC，但有兩筆 TLE。看了別人的 submission，發現大部份人想到的方法是修改 BFS，若是 moveA，將相鄰點加進 queue 的開頭，若是 moveB，則是加進 queue 的尾端。這樣在走的時候，就會優先走 moveA 的點。很巧妙的方法，完全沒往這方向想，看了討論區，這方法還是個有名稱的方法，叫  [0-1 BFS](https://cp-algorithms.com/graph/01_bfs.html)，完全沒聽說過啊。

c++17 可以用`[...] = data` 將 `tuple` 或 `pair` 解構，寫起來真的舒服。
以下給出使用 dijkstra 的 AC Code：

```cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <tuple>
#include <functional>
using namespace std;

typedef pair<int, int> pii;
const int inf = 0x3f3f3f3f;

int solve() {
    int H, W; 
    int Cr, Cc;
    int Dr, Dc;
    cin >> H >> W;
    cin >> Cr >> Cc; Cr--; Cc--;
    cin >> Dr >> Dc; Dr--; Dc--;
    vector<string> S(H);
    for (int r = 0; r < H; r++) {
        cin >> S[r];
    }

    if (S[Cr][Cc] == '#' || S[Dr][Dc] == '#') {
        return -1;
    }

    auto deltas = vector<tuple<int, int, int>>();
    deltas.push_back(tuple(0, +1, 0));
    deltas.push_back(tuple(0, -1, 0));
    deltas.push_back(tuple(+1, 0, 0));
    deltas.push_back(tuple(-1, 0, 0));
    for (int dr = -2; dr <= 2; dr++) {
        for (int dc = -2; dc <= 2; dc++) {
            if (dr == 0 and dc == 0) continue;
            deltas.push_back(tuple(dr, dc, 1));
        }
    }

    auto dis = vector<int>(H * W, inf);
    auto que = priority_queue<pii, vector<pii>, greater<pii>>();

    dis[Cr * W + Cc] = 0;
    que.push(pii(0, Cr * W + Cc));

    while (!que.empty()) {
        auto [d, u] = que.top();
        que.pop();

        if (dis[u] < d) continue;

        for (auto&& [dr, dc, w] : deltas) {
            auto nr = u / W + dr;
            auto nc = u % W + dc;
            if (nr < 0 || nr >= H) continue;
            if (nc < 0 || nc >= W) continue;
            if (S[nr][nc] == '#') continue;
            if (dis[nr * W + nc] > dis[u] + w) {
                dis[nr * W + nc] = dis[u] + w;
                que.push(pii(dis[nr * W + nc], nr * W + nc));
            }
        }
    }

    if (dis[Dr * W + Dc] == inf) {
        return -1;
    }
    return dis[Dr * W + Dc];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cout << solve() << endl;

    return 0;
}
```

## E. Bomber

一開始看到題目，覺得是二分匹配，後來才發現只能放 1 個炸彈。

最一開始當然是覺得每個位置都放放看，將炸彈放在位置 (r, c) 時，透過預計算每個 row、每個 col 各有多少個目標，我們可以 $O(1)$ 的算出可以炸掉多少個目標，即 `cntR[r] + cntC[c] - (1 if S[r][c] is target else 0)`，答案為最大值。

但這題的難點是 H, W 都很大，光是枚舉所有的位置所需的 $O(H * W)$ 就會 TLE。於是我就想要如何加速，上述方法可以看成枚舉每個 row，在 row `r` 時，我們想找出此 row 的 `cntC[c] - (1 if S[r][c] is target else 0)`，這會是一個長度為 W 的陣列，我們求出其中的最大值，再加上 `cntR[r]`，就是這個 row 的最佳解。

例如這筆測資（x 代表有 target）：
```
xx.
...
x.x
```
各個 row 的 `cntC[c] - (1 if S[r][c] is target else 0)` 與得到的答案如下：



|       | col 1       | col 2       | col 3       | max | cntR[r] + max |
| ----- | ----------- | ----------- | ----------- | --- | ------------- |
| row 1 | (2 - 1) = 1 | (1 - 1) = 0 | (1 - 0) = 1 | 1   | 2 + 1 = 3     |
| row 2 | (2 - 0) = 0 | (1 - 0) = 1 | (1 - 0) = 1 | 2   | 0 + 2 = 2     |
| row 3 | (2 - 1) = 1 | (1 - 0) = 1 | (1 - 1) = 0 | 1   | 2 + 1 = 3     |


接下來問題就是如何高速的求出 `cntC[c] - (1 if S[r][c] is target else 0)` 了，在發現題目說 targets 的數量不超過 3 * 10^5 後，我就想到了可以用線段樹：

線段樹一開始存的是 `cntC`。又因為當我要進入 row `r` 時，因為我知道 row `r` 所有 target 的位置，我可以將線段樹中這些位置都**減去 1**，此時線段樹中存的就是 `cntC[c] - (1 if S[r][c] is target else 0)`。而我們想知道的最大值也可以用透過線段樹的 query 得出。當我們離開 row `r` 時，記得將那些 -1 的位置**加回來**，讓線段樹變成存 `cntC`。

處理 target 的部份 amortize 下去只有 $O(M)$，整體時間 $O(H + W + M + H log(W))$ = $O(H log(W))$，可以在時間內解出。看了別人的 submission，發現用線段樹的人不多呢，晚點再來研究他們是怎麼解的。

以下為 c++ 的 AC Code：

```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 0-based index
// tree size: 2 * NN - 1
// leaves indices: [NN - 1, 2 * NN - 1)
template<class T>
struct SegTree {
    int NN;
    T default_value;
    vector<T> data;

    T aggr(T a, T b) {
        return max(a, b);
    }

    SegTree(int N, T val) {
        default_value = val;
        NN = 1; while (NN < N) NN <<= 1;
        data = vector<T>(2 * NN - 1, val);
    }

    SegTree(const vector<T> v, T val) {
        default_value = val;
        int N = v.size();
        NN = 1; while (NN < N) NN <<= 1;
        data = vector<T>(2 * NN - 1, val);
        copy(v.begin(), v.end(), data.begin() + (NN - 1));
        build(0, 0, NN);
    }

    void build(int u, int l, int r) {
        if (r - l == 1) return;
        int m = (l + r) / 2;
        build(u * 2 + 1, l, m);
        build(u * 2 + 2, m, r);
        data[u] = aggr(data[2 * u + 1], data[2 * u + 2]);
    }

    T query(int a, int b, int u, int l, int r) {
        if (l >= b || r <= a)
            return default_value;
        if (l >= a && r <= b)
            return data[u];
        int m = (l + r) / 2;
        T res1 = query(a, b, u * 2 + 1, l, m);
        T res2 = query(a, b, u * 2 + 2, m, r);
        return aggr(res1, res2);
    }

    void update(int idx, T x, int u, int l, int r) {
        if (idx < l || idx >= r)
            return;
        if (idx == l && r - l == 1) {
            data[u] = x;
            return;
        }
        int m = (l + r) / 2;
        update(idx, x, u * 2 + 1, l, m);
        update(idx, x, u * 2 + 2, m, r);
        data[u] = aggr(data[2 * u + 1], data[2 * u + 2]);
    }

    void increment(int idx, T x, int u, int l, int r) {
        update(idx, data[NN - 1 + idx] + x, u, l, r);
    }
};

template <class T>
ostream & operator << (ostream &out, const SegTree<T> &seg) {
    out << "SegTree(NN=" << seg.NN << ", ";
    for (int u = seg.NN - 1, sz = seg.NN; sz >= 1; u /= 2, sz /= 2) {
        out << "[ ";
        for (int i = 0; i < sz; i++) {
            out << seg.data[u + i] << " ";
        }
        out << "]";
    }
    out << ")";
    return out;
}

int solve() {
    int H, W, M;
    cin >> H >> W >> M;

    auto cntR = vector<int>(H, 0);
    auto cntC = vector<int>(W, 0);
    auto t = vector<vector<int>>(H, vector<int>());
    for (int i = 0; i < M; i++) {
        int r, c; 
        cin >> r >> c;
        r--; c--;
        cntR[r]++;
        cntC[c]++;
        t[r].push_back(c);
    }

    auto seg = SegTree<int>(cntC, 0);
    // cout << seg << endl;
    int ans = -1;
    for (int r = 0; r < H; r++) {
        for (auto c : t[r]) {
            seg.increment(c, -1, 0, 0, seg.NN);
        }
        // cout << seg << endl;
        int val = cntR[r] + seg.query(0, W, 0, 0, seg.NN);
        ans = max(ans, val);
        for (auto c : t[r]) {
            seg.increment(c, +1, 0, 0, seg.NN);
        }
    }
    return ans;
}

int main () {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cout << solve() << endl;

    return 0;
}
```

:::success
[< 回到所有題解](https://hackmd.io/@amoshyc/HkWWepaPv/)
:::