---
tags: Programming Contest
---

# AtCoder Beginner Contest 170 題解

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

## 心得

賽後寫的。

## A, B, C

水題。

## D. Not Divisible

看了題解才想到，可以用 Sieve of Eratosthenes，因為 $A_i$ 最大才 $10^6$。

以下是一些要注意的或特判的 edge case：

1
1
5
2 2 2 3 3
5
2 2 2 4 4
5
1 1 1 1 2

使用 numpy 的 AC Code:

import numpy as np
 
N = int(input())
A = list(map(int, input().split()))
A = np.int32(A)
 
vals, cnts = np.unique(A, return_counts=True)
 
if len(vals) == 1:
    print(0 if cnts[0] > 1 else 1)
elif vals[0] == 1:
    print(0 if cnts[0] > 1 else 1)
else:
    sat = np.ones(vals.max() + 1, dtype=bool)
    for x in vals:
        sat[2 * x::x] = False
    ans = (sat[vals] & (cnts == 1)).sum().item()
    print(ans)

## E. Smart Infants

照著題目模擬就是，問題主要是要用對資料結構。對於每個 kindergarden 我們需要一個可以高速插入、高速刪除、高速查詢最大值的容器。

C++ 的 multiset 符合所需。使用 c++ 的 multiset 要注意的一點是 **`set.erase(val)` 會刪除容器中所有值為 `val` 的 entries，若只想刪除一個值為 `val` 的 entry，要用 `set.erase(set.find(val))`**。

以下為 c++ 的 AC Code:

#include <iostream>
#include <iterator>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
    
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int N, Q;
    int M = 2 * 100000;
    cin >> N >> Q;
    
    auto belong = vector<int>(N, -1);
    auto rating = vector<int>(N, -1);
    auto evennesses = multiset<int>();
    auto kdrgrtns = vector<multiset<int>>(M);
    
    for (int i = 0; i < N; i++) {
        int A, B; 
        cin >> A >> B;
        B--;
        rating[i] = A;
        belong[i] = B;
        kdrgrtns[B].insert(A);
    }
    for (auto kdrgrtn: kdrgrtns) {
        if (!kdrgrtn.empty()) {
            evennesses.insert(*kdrgrtn.rbegin());
        }
    }
    
    while (Q--) {
        int C, D;
        cin >> C >> D;
        C--; D--;
    
        auto &kdrgrtn_src = kdrgrtns[belong[C]];
        auto &kdrgrtn_dst = kdrgrtns[D];
    
        evennesses.erase(evennesses.find(*kdrgrtn_src.rbegin()));
        kdrgrtn_src.erase(kdrgrtn_src.find(rating[C]));
        if (kdrgrtn_src.size() > 0) {
            evennesses.insert(*kdrgrtn_src.rbegin());
        }

        if (kdrgrtn_dst.size() > 0) {
            evennesses.erase(evennesses.find(*kdrgrtn_dst.rbegin()));
        }
        kdrgrtn_dst.insert(rating[C]);
        evennesses.insert(*kdrgrtn_dst.rbegin());
    
        belong[C] = D;
    
        cout << *evennesses.begin() << endl;
    }
    
    return 0;
}

## F. Pond Skater

這題馬上讓人想到是最短路徑，於是就刻了一個 Dijkstra，然後就會 TLE。
對於每個 vertex 我們都展開 4 * K 條邊實在太多了，所幸我們可以剪枝。

當我們在 `(r, c)`，嘗試用 `dis[r][c] + 1` 鬆弛 `dis[r + k * dr][c + k * dc]` 不成功時，我們不需要展開更大的 `k`，因為那些更遠的點（即 `k` 更大）不可能透過目前的路徑得到更佳的解。

寫成程式碼就是在展開邊的地方加入剪枝：

// omit
for (int k = 1; k <= K; k++) {
    // omit
    if (dis[r + k * dr][c + k * dc] < dis[r][c] + 1) break;
    // omit
}

你就能 AC 了。官方題解我是沒有看懂，這題網路上的題解都是 BFS + 剪枝，我是覺得挺神奇的啦，最短路徑不是應該想到 Dijkstra 嗎？還有人說此剪枝方法不適用 Dijkstra，只能用在 BFS 上 (┛ಠ_ಠ)┛彡┻━┻

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

typedef tuple<int, int, int> t3i;
const int INF = 0x3f3f3f3f;

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

    int sr, sc, tr, tc;
    cin >> sr >> sc >> tr >> tc;
    sr--; sc--; tr--; tc--;

    vector<string> A(H);
    for (int r = 0; r < H; r++) {
        cin >> A[r];
    }

    auto deltas = vector<t3i>();
    deltas.push_back({+1, 0, 1});
    deltas.push_back({-1, 0, 1});
    deltas.push_back({0, +1, 1});
    deltas.push_back({0, -1, 1});

    auto dis = vector<vector<int>>(H, vector<int>(W, INF));
    auto que = priority_queue<t3i, vector<t3i>, greater<t3i>>();

    dis[sr][sc] = 0;
    que.push({0, sr, sc});

    while (!que.empty()) {
        auto [d, r, c] = que.top(); que.pop();
        if (d > dis[r][c]) continue;
        for (auto&& [dr, dc, w]: deltas) {
            for (int k = 1; k <= K; k++) {
                int nr = r + k * dr;
                int nc = c + k * dc;
                if (nr < 0 || nr >= H) break;
                if (nc < 0 || nc >= W) break;
                if (A[nr][nc] == '@') break;
                if (dis[nr][nc] < d + w) break;
                if (dis[nr][nc] > d + w) {
                    dis[nr][nc] = d + w;
                    que.push({dis[nr][nc], nr, nc});
                }
            }
        }
    }

    return ((dis[tr][tc] == INF) ? -1: dis[tr][tc]);
}

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

    cout << solve() << endl;

    return 0;
}

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