AtCoder Beginner Contest 378

Rank: 455

A - Pairing (abc378 A)

tags: 計數(Counter)

題意

給定 44 個範圍在 11 到 44 的整數，分別代表 44 個球的顏色。每次操作可以選擇兩個顏色相同的球並將它們丟棄，給出可以執行操作的最大次數。

思路：計數(Counting)

統計每個顏色出現的次數 cnt[i]cnt[i]，對於每個顏色，將其出現的次數除以 22，取整數部分，最後將所有顏色的對數相加。

複雜度分析

  • 時間複雜度：O(n)\mathcal{O}(n)，其中 nn 為球的數量，本題中 n=4n = 4。
  • 空間複雜度：O(m)\mathcal{O}(m)，其中 mm 為球的顏色種類數量，本題中 m=4m = 4。
1
2
3
4
5
A = list(map(int, input().split()))
cnt = [0] * (5)
for x in A:
    cnt[x] += 1
print(sum(x // 2 for x in cnt))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
const int N = 4;
#define endl '\n'

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    vector<int> A(N), cnt(N + 1);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        cnt[A[i]]++;
    }
    int ans = 0;
    for (auto &x : cnt) {
        ans += x / 2;
    }
    cout << ans << endl;
    return 0;
}

B - Garbage Collection (abc378 B)

tags: 模運算(Modular Arithmetic)

題意

給定 NN 種垃圾的收取規則，其中第 ii 種垃圾會在第 did_i 天收取，其中 did_i 滿足 di mod qi=rid_i \bmod q_i = r_i。

回答 QQ 個查詢，每個查詢給定第 tjt_j 種垃圾在第 djd_j 天被放出，回答它將在第幾天被收取。

若垃圾在丟棄當天同時也是該種垃圾的收取日，則當天就會被收取。

思路：模運算(Modular Arithmetic)

對於每個查詢 (tj,dj)(t_j, d_j)，根據垃圾種類 tjt_j 對應的 qiq_i 和 rir_i，我們需要找到最早的大於或等於丟棄日期 djd_j 的日期 dansd_{ans}，使得 dans mod qi=rid_{ans} \bmod q_i = r_i。

  • 首先計算 r=dj mod qir = d_j \bmod q_i，如果 r=rir = r_i，則當天就會被收取，答案即為 djd_j。
  • 否則需要計算下一個滿足 d mod qi=rid \bmod q_i = r_i 的日期，這可以通過計算 (ri−dj) mod qi(r_i - d_j) \bmod q_i，然後將結果加到 djd_j 上得到。
    • 如果 ri>dj mod qir_i > d_j \bmod q_i，則直接得到需要增加的天數。
    • 如果 ri<dj mod qir_i < d_j \bmod q_i，則會借一個完整的週期( qiq_i )，確保結果為正數。
  • 但需要確保取模後的結果為正數，所以在 C++ 中需要對結果進行修正，即 ((ri−dj) mod qi+qi) mod qi((r_i - d_j) \bmod q_i + q_i) \bmod q_i。

複雜度分析

  • 時間複雜度：O(N+Q)\mathcal{O}(N + Q)，其中 NN 為垃圾種類數量，QQ 為查詢數量。
  • 空間複雜度：O(N)\mathcal{O}(N)，用於儲存垃圾種類規則。
1
2
3
4
5
6
7
8
9
10
11
N = int(input())
garbages = [tuple(map(int, input().split())) for _ in range(N)]
Q = int(input())
for _ in range(Q):
    t_j, d_j = map(int, input().split())
    q_i, r_i = garbages[t_j - 1]
    if d_j % q_i == r_i:
        ans = d_j
    else:
        ans = d_j + ((r_i - d_j) % q_i)
    print(ans)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int N, Q, q_i, r_i, t_j, d_j;
    cin >> N;
    vector<pair<int, int>> garbages(N);
    for (int i = 0; i < N; i++) {
        cin >> garbages[i].first >> garbages[i].second;
    }
    cin >> Q;
    for (int i = 0; i < Q; i++) {
        cin >> t_j >> d_j;
        q_i = garbages[t_j - 1].first;
        r_i = garbages[t_j - 1].second;
        if (d_j % q_i == r_i) {
            cout << d_j << endl;
        } else {
            cout << d_j + ((r_i - d_j) % q_i + q_i) % q_i << endl;
        }
    }
    return 0;
}

C - Repeating (abc378 C)

tags: 雜湊表(Hash Table)

題意

給定一個由 NN 個正數組成的陣列 AA = (A1,A2,…,AN)(A_1, A_2, \dots, A_N)，構造相同長度的序列 BB = (B1,B2,…,BN)(B_1, B_2, \dots, B_N)，滿足 BiB_i 為 AiA_i 上一次出現的位置，如果不存在這樣的位置，則令 Bi=−1B_i = -1。

思路：雜湊表(Hash Table)

使用一個雜湊表 pospos 紀錄每個數字最後出現的位置，遍歷陣列 AA，對於每個 AiA_i，如果 AiA_i 已經出現過，則 Bi=pos[Ai]B_i = pos[A_i]，否則 Bi=−1B_i = -1。最後更新 pos[Ai]pos[A_i] 為當前位置。

複雜度分析

  • 時間複雜度：O(N)\mathcal{O}(N)
  • 空間複雜度：O(N)\mathcal{O}(N)
1
2
3
4
5
6
7
8
9
10
11
12
from collections import defaultdict

N = int(input())
A = list(map(int, input().split()))

ans = [-1] * N
pos = defaultdict(lambda: -1)
for i, x in enumerate(A):
    ans[i] = pos[x]
    pos[x] = i + 1

print(*ans)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int N, x; cin >> N;
    unordered_map<int, int> pos;
    vector<int> ans(N, -1);
    for (int i = 0; i < N; i++) {
        cin >> x;
        ans[i] = (pos.find(x) == pos.end() ? -1 : pos[x]);
        pos[x] = i + 1;
    }
    for (int i = 0; i < N; i++) {
        cout << ans[i] << ' ';
    }
    cout << endl;
    return 0;
}

D - Count Simple Paths (abc378 D)

tags: 回溯(Backtracking) DFS

題意

給定一個大小為 H×WH \times W 的網格，其中 Si,jS_{i,j} 表示位於從上至下第 ii 行、從左至右第 jj 列的格子，若 Si,jS_{i,j} 為 . 表示空地，Si,jS_{i,j} 為 # 表示阻塞的格子。

另給定一個正整數 KK，計算從一個空地開始，進行 KK 步移動到相鄰的格子的方式數量（可以向上、向下、向左或向右移動），且不經過阻塞的格子，也不重複拜訪同一個格子。

約束條件

  • 1≤H,W≤101 \leq H, W \leq 10
  • 1≤K≤111 \leq K \leq 11
  • HH、WW 和 KK 為整數。
  • 每個 Si,jS_{i,j} 皆為 . 或 #。
  • 至少有一個格子為空地。

思路：回溯(Backtracking)

注意到 KK 最多只有 1111，因此可以考慮使用 回溯(Backtracking) 進行暴力搜索，對於每個空地格子 (i,j)(i, j)，以它為起點進行深度優先搜索，嘗試所有可能的路徑，並計算合法的路徑數量。

在回溯的過程中需要記錄已經拜訪過的格子，以避免重複拜訪，可以使用一個二維陣列 visitedvisited 來記錄每個格子是否被拜訪過、或是直接修改網格 SS 的值，並且在回溯時需要恢復狀態。

複雜度分析

  • 時間複雜度：O(H×W×4×3K−1)\mathcal{O}(H \times W \times 4 \times 3^{K-1})
    • 最多有 H×WH \times W 個可能的起點，每個起點最多有 44 個方向可以走，由於不能走回頭路，所以之後的每一步最多有 33 個方向可以走。
  • 空間複雜度：O(H×W)\mathcal{O}(H \times W)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import sys
sys.setrecursionlimit(10 ** 6)

H, W, K = map(int, input().split())
grid = [input().strip() for _ in range(H)]
DIR = [(-1,0), (1,0), (0,-1), (0,1)]

ans = 0
visited = [[False for _ in range(W)] for _ in range(H)]
def dfs(x, y, step):
    global ans
    if step == K:
        ans += 1
        return
    for dx, dy in DIR:
        nx, ny = x + dx, y + dy
        if 0 <= nx < H and 0 <= ny < W:
            if grid[nx][ny] == '.' and not visited[nx][ny]:
                visited[nx][ny] = True
                dfs(nx, ny, step + 1)
                visited[nx][ny] = False

for i in range(H):
    for j in range(W):
        if grid[i][j] == '.':
            visited[i][j] = True
            dfs(i, j, 0)
            visited[i][j] = False

print(ans)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    vector<pair<int, int>> DIR = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int H, W, K; cin >> H >> W >> K;
    vector<string> grid(H);
    for (int i = 0; i < H; i++) {
        cin >> grid[i];
    }
    int ans = 0;
    auto dfs = [&](auto &&dfs, int x, int y, int step) -> void {
        if (step == K) {
            ans += 1;
            return;
        }
        for (auto [dx, dy] : DIR) {
            int nx = x + dx, ny = y + dy;
            if (nx >= 0 && nx < H && ny >= 0 && ny < W && grid[nx][ny] == '.') {
                grid[nx][ny] = '#';
                dfs(dfs, nx, ny, step + 1);
                grid[nx][ny] = '.';
            }
        }
    };
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (grid[i][j] == '.') {
                grid[i][j] = '#';
                dfs(dfs, i, j, 0);
                grid[i][j] = '.';
            }
        }
    }
    cout << ans << endl;
    return 0;
}

E - Mod Sigma Problem (abc378 E)

tags: 前綴和(Prefix Sum) 樹狀陣列(BIT) 逆序對(Reverse Pair)

題意

給定一個長度為 NN 的非負整數陣列 A=(A1,A2,…,AN)A = (A_1, A_2, \dots, A_N)，以及一個正整數 MM，計算以下值：

∑1≤l≤r≤N((∑l≤i≤rAi)modM). \sum_{1 \leq l \leq r \leq N} \left( \left(\sum_{l \leq i \leq r} A_i\right) \mathbin{\mathrm{mod}} M \right).

其中，XmodMX \mathbin{\mathrm{mod}} M 表示非負整數 XX 除以 MM 後的餘數。

約束條件

  • 1≤N≤2×1051 \leq N \leq 2 \times 10^5
  • 1≤M≤2×1051 \leq M \leq 2 \times 10^5
  • 0≤Ai≤1090 \leq A_i \leq 10^9

思路：統計貢獻 + 樹狀陣列 + 逆序對

首先從沒有取模的狀況開始，即計算所有區間和的總和：

∑1≤l≤r≤N(∑l≤i≤rAi)\sum_{1 \leq l \leq r \leq N} \left(\sum_{l \leq i \leq r} A_i\right)

我們可以考慮以 rr 為右端點的區間的貢獻，即：

(∑1≤i≤rAi)+(∑2≤i≤rAi)+⋯+(∑r≤i≤rAi)=∑1≤l≤r(∑l≤i≤rAi)\left(\sum_{1 \leq i \leq r} A_i\right) + \left(\sum_{2 \leq i \leq r} A_i\right) + \cdots + \left(\sum_{r \leq i \leq r} A_i\right) = \sum_{1 \leq l \leq r} \left(\sum_{l \leq i \leq r} A_i\right)

令 s[r]s[r] 為前 rr 項的前綴和，則上述和可以表示為：

∑1≤l≤rs[r]−s[l−1]\sum_{1 \leq l \leq r} s[r] - s[l-1]

展開後為：

(s[r]−s[0])+(s[r]−s[1])+⋯+(s[r]−s[r−1])=s[r]×r−∑0≤l≤r−1s[l](s[r] - s[0]) + (s[r] - s[1]) + \cdots + (s[r] - s[r-1]) = s[r] \times r - \sum_{0 \leq l \leq r-1} s[l]

因此，我們可以在遍歷 rr 的過程中，先透過前綴和 ss 計算 s[r]×rs[r] \times r，接著計算以 rr 為右端點的區間的貢獻 s[r]×r−∑0≤l≤r−1s[l]s[r] \times r - \displaystyle\sum_{0 \leq l \leq r-1} s[l]，最後維護 ∑0≤l≤r−1s[l]\displaystyle\sum_{0 \leq l \leq r-1} s[l]，這只要加上 s[r]s[r] 即可。

至此，我們已經可以解決沒有取模的狀況。接著考慮取模後的情況：

(∑l≤i≤rAi) mod M=(s[r]−s[l−1]) mod M=(s[r] mod M)−(s[l−1] mod M) mod M\begin{align*} \left(\sum_{l \leq i \leq r} A_i\right) \bmod M &= \left( s[r] - s[l-1] \right) \bmod M \\ &= (s[r] \bmod M) - (s[l-1] \bmod M) \bmod M \end{align*}

我們可以在計算前綴和的過程中對 s[i]s[i] 取模，並且在計算答案時考慮取模後的值，但由於取模後 s[r] mod Ms[r] \bmod M 不一定會大於 s[l−1] mod Ms[l-1] \bmod M，因此需要考慮兩種情況：

  • 若 s[r] mod M≥s[l−1] mod Ms[r] \bmod M \geq s[l-1] \bmod M，則對答案的貢獻還是 s[r] mod M−s[l−1] mod Ms[r] \bmod M - s[l-1] \bmod M。
  • 若 s[r] mod M<s[l−1] mod Ms[r] \bmod M < s[l-1] \bmod M，則對答案的貢獻為 s[r] mod M−s[l−1] mod M+Ms[r] \bmod M - s[l-1] \bmod M + M，即需要補加 MM。

因此，我們在計算以 rr 為右端點的區間的貢獻時，需要計算有多少個 ll 滿足 s[r] mod M<s[l−1] mod Ms[r] \bmod M < s[l-1] \bmod M，即 逆序對(Reverse Pair) 的數量，這可以使用 樹狀陣列(Fenwick Tree / Binary Indexed Tree, BIT) 在 O(log⁡M)O(\log M) 的時間內完成。這裡直接使用 AtCoder Library 的樹狀陣列。

這裡 ll 的下標寫的不太統一，寫 s[l−1]s[l - 1] 的時候 ll 的範圍是 1≤l≤r1 \leq l \leq r，寫 s[l]s[l] 的時候 ll 的範圍是 0≤l≤r−10 \leq l \leq r-1。

複雜度分析

  • 時間複雜度：O(Nlog⁡M)\mathcal{O}(N \log M)
  • 空間複雜度：O(N+M)\mathcal{O}(N + M)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from atcoder.fenwicktree import FenwickTree

N, M = map(int, input().split())
A = list(map(int, input().split()))

s = [0] * (N + 1)
for i, x in enumerate(A):
    s[i+1] = (s[i] + x) % M

bit = FenwickTree(M)
bit.add(0, 1)

ans = 0
s_sl = 0 # sum(s[l])
for r in range(1, N+1):
    # 以 r 為右端點的區間有 r 個，其和為 s[r] * r - sum(s[l])
    ans += s[r] * r - s_sl
    # 計算有多少個 l 滿足 s[l] % MOD > s[r] % MOD，即逆序對數量
    # 對於這種情況，由於取模後不會是負數，所以需要補加 M 回來
    ans += M * (r - bit.sum(0, s[r] + 1)) 
    bit.add(s[r], 1)
    s_sl += s[r]
print(ans)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
#include <atcoder/fenwicktree>
using namespace std;
using namespace atcoder;
using LL = long long;
#define endl '\n'

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int N, M; cin >> N >> M;
    vector<int> A(N);
    vector<LL> s(N + 1);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        s[i + 1] = (s[i] + A[i]) % M;
    }

    fenwick_tree<LL> bit(M);
    bit.add(0, 1);
    LL ans = 0, s_sl= 0;
    for (int r = 1; r <= N; r++) {
        ans += s[r] * r - s_sl;
        ans += M * (r - bit.sum(0, s[r] + 1));
        bit.add(s[r], 1);
        s_sl += s[r];
    }
    cout << ans << endl;
    return 0;
}

F - Add One Edge 2 (abc378 F)

tags: 樹(Tree) DFS BFS

題意

給定一棵包含 NN 個頂點的樹，並給定 N−1N-1 條邊，第 ii 條邊連接頂點 uiu_i 和 viv_i。

在給定的樹中添加一條無向邊，總是會產生一個包含恰好一個環的圖。

在這樣的圖中，有多少滿足以下所有條件？

  • 該圖是 簡單圖 。
  • 環中的所有頂點的度數均為 33。

約束條件

  • 3≤N≤2×1053 \leq N \leq 2 \times 10^5
  • 1≤ui,vi≤N1 \leq u_i, v_i \leq N

思路：DFS / BFS

由於在加入一條邊後，環中的所有頂點的度數均為 33，因此這個環必定是由 22 個度數為 22 的頂點和若干個度數為 33 的頂點組成。

因此，我們只需要找到一個所有頂點的度數均為 33 的連通分量，並計算與這個連通分量相鄰的度數為 22 的頂點數量 cntcnt，在這些度數為 22 的頂點中任選兩個配對，便能產生一個符合條件的圖，故可以得該連通分量對答案的貢獻為 cnt×(cnt−1)2\frac{cnt \times (cnt - 1)}{2}。

得到上述結論後，我們只需要對樹進行 DFS 或 BFS，找到每個度數均為 33 的連通分量中，度數為 22 的頂點數量，並計算貢獻即可。

為了確保每個連通分量只會被計算一次，需要記錄每個頂點是否被訪問過。

複雜度分析

  • 時間複雜度：O(N)\mathcal{O}(N)
    • 每個點最多只會被訪問一次。
  • 空間複雜度：O(N)\mathcal{O}(N)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import sys
sys.setrecursionlimit(10**6)

N = int(input())
edges = [list(map(int, input().split())) for _ in range(N-1)]

g = [[] for _ in range(N + 1)]
deg = [0] * (N + 1)
for u, v in edges:
    g[u].append(v)
    g[v].append(u)
    deg[u] += 1
    deg[v] += 1

vis = [False] * (N + 1)
def dfs(u):
    if deg[u] != 3 or vis[u]:
        return 0
    vis[u] = True
    cnt = 0
    for v in g[u]:
        if deg[v] == 2:
            cnt += 1
        elif deg[v] == 3 and not vis[v]:
            cnt += dfs(v)
    return cnt

ans = 0
for x in range(1, N + 1):
    if deg[x] != 3 or vis[x]:
        continue
    cnt = dfs(x)
    ans += cnt * (cnt - 1) // 2
print(ans)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define endl '\n'

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int N; cin >> N;
    vector<pair<int, int>> edges(N - 1);
    for (int i = 0; i < N - 1; i++) {
        cin >> edges[i].first >> edges[i].second;
    }
    vector<vector<int>> g(N + 1);
    vector<int> deg(N + 1);
    for (auto [u, v] : edges) {
        g[u].push_back(v);
        g[v].push_back(u);
        deg[u] += 1;
        deg[v] += 1;
    }
    vector<bool> vis(N + 1);
    auto dfs = [&](auto dfs, int u) -> int {
        if (deg[u] != 3 || vis[u]) return 0;
        vis[u] = true;
        int cnt = 0;
        for (int v : g[u]) {
            if (deg[v] == 2) cnt += 1;
            else if (deg[v] == 3 && !vis[v]) cnt += dfs(dfs, v);
        }
        return cnt;
    };
    LL ans = 0;
    for (int i = 1; i <= N; i++) {
        if (deg[i] != 3 || vis[i]) continue;
        int cnt = dfs(dfs, i);
        ans += cnt * (cnt - 1LL) / 2;
    }
    cout << ans << endl;
    return 0;
}

寫在最後

PROMPT

1girl, solo, long hair, looking at viewer, bangs, hair ornament, dress, hair between eyes, bare shoulders, jewelry, sitting, closed mouth, green eyes, white hair, short sleeves, sidelocks, multicolored hair, outdoors, detached sleeves, green hair, sleeveless, pointy ears, white dress, side ponytail, bracelet, tree, symbol-shaped pupils, gradient hair, white footwear, bug, white socks, butterfly, leaf hair ornament, toeless footwear, cross-shaped pupils, in tree, swing, nahida (genshin impact),