Atcoder ABC 177

작성일 | In

결과


다 풀긴 했는데 F에서 너무 말린 것 같네요…

A. Don’t be late

$D/S \leq T$이면 Yes, 아니면 No를 출력하면 됩니다.
저는 실수 오차를 싫어하기 때문에 $D \leq T \times S$로 구현했습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int d, t, s; cin >> d >> t >> s;
    if(d <= t*s) cout << "Yes";
    else cout << "No";
}

B. Substring

$O(\vert S\vert\vert T\vert)$만에 모든 경우를 다 봐주면 됩니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    string s, t; cin >> s >> t;
    int mn = 1e9;
    int n = s.size(), m = t.size();
    for(int i=0; i<n; i++){
        int ed = i + m - 1;
        if(ed == n) break;
        int cnt = 0;
        for(int j=0; j<m; j++) cnt += s[i+j] != t[j];
        mn = min(mn, cnt);
    }
    cout << mn;
}

C. Sum of product of pairs

$S = \sum A_i$라고 합시다. 정답은 $(S^2 - \sum (A_i)^2) / 2$가 됩니다.

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
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;
const ll mod = 1e9+7;

ll n, a[202020], s;

ll pw(ll a, ll b){
    ll ret = 1; a %= mod;
    while(b){
        if(b & 1) ret = ret * a % mod;
        b >>= 1; a = a * a % mod;
    }
    return ret;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n;
    for(int i=1; i<=n; i++) cin >> a[i], s += a[i];
    s %= mod;
    ll res = s * s % mod;
    for(int i=1; i<=n; i++){
        res -= a[i] * a[i] % mod;
        res %= mod; res += mod; res %= mod;
    }
    cout << res * pw(2, mod-2) % mod;
}

D. Friends

친구 관계를 그래프로 나타내봅시다. 가장 큰 컴포넌트의 크기가 문제의 정답이 된다는 것을 쉽게 알 수 있습니다.
DFS / BFS / Union-Find 등으로 구현해주면 됩니다.

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
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;
const ll mod = 1e9+7;

int par[202020], sz[202020];
int find(int v){ return v == par[v] ? v : par[v] = find(par[v]); }
void merge(int u, int v){ u = find(u); v = find(v); if(u != v) par[u] = v, sz[v] += sz[u]; }

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int n, m; cin >> n >> m;
    iota(par, par+202020, 0);
    fill(sz, sz+202020, 1);

    for(int i=0; i<m; i++){
        int s, e; cin >> s >> e;
        merge(s, e);
    }
    int mx = 0;
    for(int i=1; i<=n; i++) mx = max(mx, sz[find(i)]);
    cout << mx;
}

E. Coprime

모든 수들의 소인수가 겹치지 않는다면 pairwise coprime입니다.
$\gcd(A_1, A_2, \ldots, A_N) = 1$이라면 setwise coprime입니다.
소인수 분해와 유클리드 호제법만 잘 사용해주면 됩니다.

여담으로, 저는 pairwise coprime을 판별할 때 BOJ 8291 Coprime Numbers코드를 재활용했습니다.
8291 Coprime Numbers는 주어진 수열에서 최대공약수가 1인 쌍의 개수를 세는 문제로, 이 문제의 상위호환이라고 볼 수 있습니다. 8291을 풀었다면, E번은 단순히 $cnt = N(N-1)/2$인지만 확인해주면 풀 수 있습니다.

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
41
42
43
44
45
46
47
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;

vector<int> prime;
int isp[1010];
void era(){
    for(int i=2; i<1010; i++){
        if(isp[i]) continue;
        prime.push_back(i);
        for(int j=i+i; j<1010; j+=i) isp[j] = 1;
    }
}

int n, g, flag = 1;
int chk[1010101];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    era(); cin >> n;
    for(int i=1; i<=n; i++){
        int t; cin >> t;
        if(i == 1) g = t;
        else g = __gcd(g, t);
        for(auto j : prime){
            if(t < j*j) break;
            if(t % j == 0){
                if(chk[j]) flag = 0;
                chk[j] = 1;
                while(t % j == 0) t /= j;
            }
        }
        if(t != 1){
            if(chk[t]) flag = 0;
            chk[t] = 1;
        }
    }

    if(flag){ cout << "pairwise coprime"; }
    else if(g == 1){ cout << "setwise coprime"; }
    else cout << "not coprime";
}

F. I hate Shortest Path Problem

세로 방향 이동 횟수는 행 번호와 동일하기 때문에 가로 방향 이동 횟수만 고려해주면 됩니다.
(i, i번째 열까지 가는데 필요한 가로 이동 횟수)를 set으로 관리합시다.

각 장애물$(A_i, B_i)$마다 구간 $[A_i, B_i]$에 있는 pair를 다 날려준 다음, $B_i+1$번째 열까지 가는데 필요한 가로 이동 횟수를 갱신해주면 됩니다. 이때 $B_i+1$번째 열까지 가는데 필요한 가로 이동 횟수의 최솟값은 아래에 나와있는 3번 연산을 이용하면 됩니다.

문제를 해결하기 위해 필요한 연산은 아래와 같습니다.

  1. 현재 set에 있는 pair 중 구간 $[A_i, B_i]$에 속하는 pair를 모두 선택해서 없애기
  2. 모든 $i$에 대해, ($i$번째 열로 가는데 필요한 가로 이동 횟수)의 최솟값 구하기
  3. $i \in [1, B_i]$인 $i$에 대해 ($i$번째 열로 가는데 필요한 가로 이동 횟수) + $(B_i+1)-i$의 최솟값 구하기

1번 연산은 set에서 lower_bound를 구하고, iterator를 하나씩 이동시키는 것으로 해결할 수 있습니다. 혹은 it = st.erase(it)와 같이 해도 됩니다.
2번 연산은 세그먼트 트리를 이용해 최소값을 구하면 됩니다. set의 원소가 바뀔 때마다 세그먼트 트리의 원소들도 같이 갱신해주면 됩니다.
3번 연산은 (i번째 열로 가는데 필요한 가로 이동 횟수) - i를 세그먼트 트리로 관리해주면 됩니다. 이때 3번 연산의 결괏값은 seg_query(1, $B_i+1$) + $B_i+1$이 됩니다.

이제 남은 것은, 열심히 구현해주면 됩니다.

KOI’16 초등부 4번 장애물 경기의 상위호환인 것 같습니다.

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;
typedef pair<ll, ll> p;

int n, m;
int a[202020], b[202020];
set<p> st;

ll tree[1 << 19], tree2[1 << 19];
const int sz = 1 << 18;
void update(int x, ll v){
    x |= sz; tree[x] = v;
    while(x >>= 1) tree[x] = min(tree[x << 1], tree[x << 1 | 1]);
}
void update2(int x, ll v){
    v -= x; x |= sz; tree2[x] = v;
    while(x >>= 1) tree2[x] = min(tree2[x << 1], tree2[x << 1 | 1]);
}
ll query(int l, int r){
    l |= sz; r |= sz; ll ret = 1e18;
    while(l <= r){
        if(l & 1) ret = min(ret, tree[l++]);
        if(~r & 1) ret = min(ret, tree[r--]);
        l >>= 1; r >>= 1;
    }
    return ret;
}
ll query2(int l, int r){
    l |= sz; r |= sz; ll ret = 1e18;
    while(l <= r){
        if(l & 1) ret = min(ret, tree2[l++]);
        if(~r & 1) ret = min(ret, tree2[r--]);
        l >>= 1; r >>= 1;
    }
    return ret;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    memset(tree, 0x3f, sizeof tree);
    memset(tree2, 0x3f, sizeof tree2);
    cin >> n >> m;
    for(int i=1; i<=m; i++){
        st.emplace(i, 0); update(i, 0); update2(i, 0);
    }

    for(int i=1; i<=n; i++){
        cin >> a[i] >> b[i];
        if(query(1, m) >= 1e9){ cout << "-1\n"; continue; } // 불가능

        ll mn = query2(1, b[i]+1) + b[i]+1; // 3번 연산

        auto it = st.lower_bound(p(a[i], -1)); // 1번 연산
        while(it != st.end()){
            if(it->x > b[i]+1) break;
            update(it->x, 1e18);
            update2(it->x, 1e18);
            it = st.erase(it);
        }

        if(b[i]+1 <= m){ // 3번 연산 결괏값 갱신
            st.emplace(b[i]+1, mn);
            update(b[i]+1, mn); update2(b[i]+1, mn);
        }

        ll res = query(1, m); // 2번 연산
        if(res >= 1e9) cout << "-1\n";
        else cout << res+i << "\n";
    }
}