---
tags: Programming Contest
---

# AtCoder Beginner Contest 177 題解

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

## 心得

賽後才寫的。跑去跟我弟打球，就沒打這個比賽了

## A, B

略

## C. Sum of product of pairs

常見的手法，改成這麼想：對於每個 A[j]，會貢獻多少值到答案中？是 `sum(A[:j]) * A[j]`，即到 j 之前的前綴和再乘上 A[j]，於是得到 code:

mod = 10 ** 9 + 7

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

ans = 0
pref = A[0]
for j in range(1, N):
    ans = (ans + A[j] * pref % mod) % mod
    pref = (pref + A[j]) % mod
print(ans)

## D. Friends

答案就是最大的那一群的大小，因為需要同樣數量的組，才能將這一群的人統統分開。實作上用 Disjoint Set 或 DFS 都可以（當然是 Disjoin Set 模版用起來！）

class DisjoinSet:
    def __init__(self, N):
        self.par = [-1] * N
        self.sz = [1] * N

    def root(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]

    def unite(self, a, b):
        a = self.root(a)
        b = self.root(b)
        if a == b:
            return
        if self.sz[a] > self.sz[b]:
            a, b = b, a
        self.par[a] = b
        self.sz[b] += self.sz[a]

    def same(self, a, b):
        return self.root(a) == self.root(b)

    def size(self, x):
        return self.sz[self.root(x)]

    def __str__(self):
        clusters = defaultdict(list)
        for x in range(N):
            clusters[self.root(x)].append(x)
        return str(list(clusters.values()))


N, M = map(int, input().split())
dsu = DisjoinSet(N)
for _ in range(M):
    x, y = map(int, input().split())
    x, y = x - 1, y - 1
    dsu.unite(x, y)

ans = max([dsu.size(x) for x in range(N)])
print(ans)

## E. Coprime

判定 not coprime 是簡單的，求出整個序列的 gcd，看值是不是大於 1。難點在於需要高速地求出任兩項是不是互質。即然 A[i] 最大才 10^6，那我們可以對每項都質因數分解，看有沒有某個質數重複出現，因為互質就代表沒有相同的質因數。

例如 [6, 4, 7]，因為 6=2x3，我們分解完 4 = 2^2 後發現質數 2 之前有被用過了，那這個序列就不可能是 pairwise coprime。

可以使用 set 來記錄用過了哪些質數。質因數分解時要注意不能對 1 做，把 1 的情況特判掉吧。

pypy 版本跑 384ms, python 版本跑 1225ms, c++ 版本跑 122ms。

import math

class SieveOfEratosthenes:
    def __init__(self, V):
        self.is_prime = [True] * (V + 1)
        self.primes = []
        for i in range(2, V + 1):
            if self.is_prime[i]:
                self.primes.append(i)
                for j in range(i * i, V + 1, i):
                    self.is_prime[j] = False
    
    def factorize(self, x):
        assert x > 1
        result = []
        for p in self.primes:
            exp = 0
            while x % p == 0:
                exp += 1
                x = x // p
            if exp > 0:
                result.append((p, exp))
            if p * p > x:
                break
        if x > 1:
            result.append((x, 1))
        return result


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

    if all(a == 1 for a in A):
        return 'pairwise coprime'

    gcd_all = 0
    for a in A:
        gcd_all = math.gcd(gcd_all, a)
    if gcd_all > 1:
        return 'not coprime'
    
    sieve = SieveOfEratosthenes(max(A))
    used_primes = set()
    for a in A:
        if a != 1:
            factors = sieve.factorize(a)
            for (p, e) in factors:
                if p in used_primes:
                    return 'setwise coprime'
                used_primes.add(p)
    
    return 'pairwise coprime'

print(solve())

## F. I hate Shortest Path Problem

等到[官方題解](https://atcoder.jp/contests/abc177/editorial/94)出來後，才搞清楚要怎麼解這題。官方題解寫得很不錯：我們維護 (end_col, start_col) 代表用最少步數到達 `(r, c)` 是從 row 0 哪個 col 出發的，這樣 row r 的答案就是 `min(end_col - start_col for all pairs)` + `r`。前者是我們向右了幾步，後者是向下了幾步。

實作上用 map 存當前 row 的 pairs，再用 multiset 存 end_col - start_col。當我們要遞推至下一行時，假設當前行禁止向下區間為 [a, b]，那我們刪除所有 end_col 在 [a, b + 1] 之間的 pairs，然後更新到達 col b + 1 的 start_col。因為當前行中，col 在 [a, b + 1] 之盼的這些格子都會走到下一行的 col b + 1。

對於每個 row，我們迭代了其中要刪除的那些 pairs 再外加一個 b + 1。pairs 的數量會越來越少，整體而言我們迭代過的 pair 數量仍然是 $O(W)$，於是時間複雜度是 $O((H + W)log(W))$

#include <iostream>
#include <map>
#include <set>
#include <vector>
using namespace std;

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

    multiset<int> steps; // num of steps going right, ie, end_col - start_col
    map<int, int> end2start; // end col to start col
    for (int c = 0; c < W; c++) {
        end2start[c] = c;
        steps.insert(0);
    }

    for (int r = 1; r <= H; r++) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;

        // Erase pairs (e, s) that a <= e <= b + 1
        auto lb = end2start.lower_bound(a);
        auto ub = end2start.upper_bound(b + 1);
        auto max_start = -1;
        for (auto it = lb; it != ub; ++it) {
            int end = it->first;
            int start = it->second;
            steps.erase(steps.find(end - start));
            max_start = max(max_start, start);
        }
        end2start.erase(lb, ub);

        // Update pair (b + 1, s)
        if (b != W - 1 and lb != ub) {
            end2start[b + 1] = max_start;
            steps.insert(b + 1 - end2start[b + 1]);
        }

        if (steps.size() > 0) {
            cout << *steps.begin() + r << endl;
        } else {
            cout << "-1" << endl;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

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