---
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/)
:::
Sign in with Wallet
Connect another wallet