2024 NYPC 예선 Round 1 / 2-A / 2-B 풀이

작성일 | In

서론

문제 지문과 공식 풀이는 NYPC 아카이브에서 확인할 수 있습니다. 채점은 BIKO에서 받을 수 있습니다.

제가 생각하는 난이도(solved.ac 기준)는 다음과 같습니다. Round 1 게임, Round 2-B 점 짝짓기는 사람마다 편차가 클 것 같습니다.

  • Round 1
    1. [B2] 초밥
    2. [S4] 무한 길이 물풍선
    3. [S3] 커닝시티 헤어샵
    4. [S3] 오르락 내리락
    5. [G3] 게임
    6. [P2] 어디로 피해야하지?
    7. [D5] 골드리치의 비밀 금고
    8. [D4] 브레이크가 고장난 카트 (output-only)
    9. [??] 1-2-3 퍼즐 (output-only)
  • Round 2-A
    1. [S?] 장비 교체
    2. [G?] 루시드의 레이저 공격을 피해라!
    3. [P5] 기차 여행
    4. [D4] 트리 읽기
  • Round 2-B
    1. [S?] 순열로 고치기
    2. [G1] 계단
    3. [P4] 점 짝짓기
    4. [P1] 합주 공연

PC 화면으로 보는 분들은 우측 사이드바를 이용해 원하는 문제로 빠르게 이동할 수 있습니다.

Round 1

1. 초밥

일반성을 잃지 않고 $A < B$라고 생각합시다. 만약 $3A < B$이면 매번 $A$를 1개, $B$를 3개씩 가져가더라도 모든 초밥을 옮길 수 없기 때문에 $-1$을 출력해야 합니다. 그렇지 않다면 항상 $3\min(A,B) \geq \max(A,B)$이 성립하도록 $\min(4,A+B)$개의 초밥을 옮길 수 있으므로 $\lceil \frac{A+B}{4} \rceil$번의 이동으로 모든 초밥을 옮길 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int TC; cin >> TC;
    for(int tc=1; tc<=TC; tc++){
        int a, b; cin >> a >> b;
        if(a > b) swap(a, b);
        if(b > 3 * a) cout << -1 << "\n";
        else cout << (a + b + 3) / 4 << "\n";
    }
}

2. 무한 길이 물풍선

이차원 평면에 여러 개의 점이 주어졌을 때, 두 점을 이어서 만들 수 있는 x축 또는 y축에 평행한 서로 다른 직선의 개수를 구하는 문제입니다. 만약 x좌표가 같은 점이 2개 있으면 y축에 평행한 직선을 만들 수 있고, y좌표가 같은 점이 2개 있으면 x축에 평행한 직선을 만들 수 있습니다.

따라서 x좌표가 같은 점 또는 y좌표가 같은 점이 2개 이상 있다면 정답이 1 증가합니다. x좌표와 y좌표를 각각 모아서 정렬한 다음 투 포인터를 사용하거나, std::map과 같은 연관 배열을 사용해서 $O(N \log N)$ 또는 (해시를 사용하면) $O(N)$ 시간에 문제를 해결할 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;

int N, R;
vector<int> X, Y;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N; X.resize(N); Y.resize(N);
    for(int i=0; i<N; i++) cin >> X[i] >> Y[i];
    sort(X.begin(), X.end());
    sort(Y.begin(), Y.end());
    for(int i=0, j=0; i<N; i=j){
        while(j < N && X[i] == X[j]) j++;
        R += j - i > 1;
    }
    for(int i=0, j=0; i<N; i=j){
        while(j < N && Y[i] == Y[j]) j++;
        R += j - i > 1;
    }
    cout << R;
}

3. 커닝시티 헤어샵

간단한 동적 계획법 문제입니다. $1, 2, \cdots, i$번 고객을 서비스하 데 걸리는 최소 시간을 $D(i)$로 정의하면, $D(i) = \min(D(i-1) + A_i, D(i-2) + \max(A_{i-1}, A_i))$와 같이 점화식을 세울 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll N, A[505050], D[505050];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N;
    for(int i=1; i<=N; i++) cin >> A[i];
    D[1] = A[1];
    for(int i=2; i<=N; i++) D[i] = min(D[i-1] + A[i], D[i-2] + max(A[i-1], A[i]));
    cout << D[N];
}

4. 오르락 내리락

구간의 시작점 $i$에 대해, $T[i\cdots j]$가 문제의 조건을 만족하는 가장 큰 구간의 끝점을 $f(i)$라고 정의하면, 문제의 정답은 구간 $[i, f(i)]$의 길이의 최댓값, 즉 $f(i) - i + 1$의 최댓값입니다.

모든 $1 \le i \le N-2$에 대해 $f(i) \le f(i+2)$가 항상 성립하기 때문에, 투 포인터를 이용해 $f(1), f(2), \cdots, f(N)$을 $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
#include <bits/stdc++.h>
using namespace std;

int N, A[202020], R;
int Inc[202020], Dec[202020];

bool Check(int i, int j){
    int len = j - i + 1;
    if(len <= 2) return true;
    if(len % 2 == 0) return Inc[i] == Inc[j-1] && Dec[i+1] == Dec[j];
    else return Inc[i] == Inc[j] && Dec[i+1] == Dec[j-1];
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N;
    for(int i=1; i<=N; i++) cin >> A[i];

    for(int i=3; i<=N; i++) Inc[i] = Inc[i-2] + (A[i-2] > A[i]);
    for(int i=3; i<=N; i++) Dec[i] = Dec[i-2] + (A[i-2] < A[i]);

    for(int i=1, j=1; i<=N; i+=2){
        while(j <= N && Check(i, j)) j++;
        R = max(R, j - i);
    }
    for(int i=2, j=2; i<=N; i+=2){
        while(j <= N && Check(i, j)) j++;
        R = max(R, j - i);
    }
    cout << R;
}

5. 게임

선공은 수를 최대한 작게 만들고, 후공은 수를 최대한 크게 만들어야 합니다. 선공의 입장에서 생각해 보면, 수를 최대한 작게 만들어야 하므로 앞에 있는 1을 제거해야 하고, 1이 없다면 앞에 있는 0을 제거하는 것은 의미가 없으므로 뒤에 있는 0을 제거해야 합니다. 반대로 후공은 수를 최대한 크게 만들어야 하므로 앞에 있는 0을 제거하는 것이 좋고, 0이 없다면 뒤에 있는 1을 제거하면 됩니다.

deque나 linked list 등을 이용하면 편리하게 구현할 수 있습니다.

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>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int N, K; string S;
    cin >> N >> K >> S;
    deque<int> P[2];
    for(int i=0; i<N; i++) P[S[i]-'0'].push_back(i);
    for(int i=0; i<K; i++){
        if(!P[1].empty()) P[1].pop_front();
        else P[0].pop_back();
        if(!P[0].empty()) P[0].pop_front();
        else P[1].pop_back();
    }
    int i = 0, j = 0;
    while(i < P[0].size() && j < P[1].size()){
        if(P[0][i] < P[1][j]) cout << 0, i++;
        else cout << 1, j++;
    }
    while(i < P[0].size()) cout << 0, i++;
    while(j < P[1].size()) cout << 1, j++;
}

6. 어디로 피해야하지?

먼저 물풍선을 x축에 평행한 선분과 y축에 평행한 선분으로 분할한 뒤, 평행하면서 겹치는 선분들을 합치고 시작합시다. $N^2$에서 이 선분들이 덮는 칸의 개수를 뺀 값이 정답입니다.

선분들이 덮는 칸의 개수는 각 선분의 길이를 모두 더한 뒤, 선분이 교차하는 횟수를 빼면 됩니다. 평행하면서 겹치는 선분을 모두 합쳤기 때문에, 각 지점은 최대 한 개의 수직 선분과 한 개의 수평 선분만 지나므로 단순히 교차점의 개수만 구해도 됩니다. 교차점은 세그먼트 트리 또는 펜윅 트리를 이용해 스위핑을 하면 $O(K \log K)$에 문제를 해결할 수 있습니다.

스위핑은 기본적으로 y축에 평행한 선분 $(y_1, y_2, x)$를 좌표 평면에 깔아놓은 다음, x축에 평행한 선분 $(x_1, x_2, y)$을 보면서 해당 y좌표에서 $[x_1, x_2]$ 구간에 있는 선분의 개수를 세는 방식으로 진행합니다. $[x_1, x_2]$ 구간에 있는 선분의 개수는 $[1, x_2]$ 구간에 있는 선분의 개수에서 $[1, x_1-1]$ 구간에 있는 선분의 개수를 빼면 됩니다.

따라서, 아래와 같이 이벤트를 만든 다음 x좌표가 증가하는 순서대로, x좌표가 같다면 이벤트 번호가 증가하는 순서대로 처리하면 됩니다.

  1. y축에 평행한 선분 $(y_1, y_2, x)$ 추가: 세그먼트 트리에서 구간 $[y_1, y_2]$에 1을 더함
  2. y좌표가 $y$이면서 $[1, x]$ 구간에 있는 선분의 개수를 구함: 세그먼트 트리에서 $y$ 지점의 값을 구함
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
77
78
79
80
81
82
83
84
85
86
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int SZ = 1 << 20;

template<typename T>
void Compress(vector<T> &v){
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
}
template<typename T>
int Index(const vector<T> &v, T x){
    return lower_bound(v.begin(), v.end(), x) - v.begin();
}

vector<pair<int,int>> Merge(vector<pair<int,int>> v){
    vector<pair<int,int>> res;
    sort(v.begin(), v.end());
    int st = 0, ed = -1;
    for(auto [s,e] : v){
        if(ed + 1 < s) res.emplace_back(st, ed), st = s, ed = e;
        ed = max(ed, e);
    }
    res.emplace_back(st, ed);
    return res;
}

int N, K; ll Color;
vector<tuple<int,int,int,int>> V;
vector<pair<int,int>> X[303030], Y[303030];
vector<int> Xc, Yc, C;

int T[SZ];
void Add(int x, int v){ for(x+=3; x<SZ; x+=x&-x) T[x] += v; }
void Add(int l, int r, int v){ Add(l, v); Add(r+1, -v); }
int Get(int x){ int r = 0; for(x+=3; x; x-=x&-x) r += T[x]; return r; }

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> K; V.reserve(K*2); Xc.reserve(K); Yc.reserve(K);
    for(int i=1; i<=K; i++){
        int x, y, r; cin >> x >> y >> r;
        V.emplace_back(0, x, max(1,y-r), min(N,y+r));
        V.emplace_back(1, y, max(1,x-r), min(N,x+r));
        Xc.push_back(x); Yc.push_back(y);
    }
    Compress(Xc); Compress(Yc);
    for(auto [flag,p,l,r] : V){
        if(flag == 0) X[Index(Xc, p)].emplace_back(l, r);
        if(flag == 1) Y[Index(Yc, p)].emplace_back(l, r);
    }
    for(int i=0; i<Xc.size(); i++) X[i] = Merge(X[i]);
    for(int i=0; i<Yc.size(); i++) Y[i] = Merge(Y[i]);

    for(int i=0; i<Xc.size(); i++) for(auto [l,r] : X[i]) Color += r - l + 1;
    for(int i=0; i<Yc.size(); i++) for(auto [l,r] : Y[i]) Color += r - l + 1;

    C.reserve(K*3);
    for(int i=0; i<Xc.size(); i++) for(auto [l,r] : X[i]) C.push_back(l-1), C.push_back(l), C.push_back(r);
    Compress(C);

    vector<tuple<int,int,int>> Upd;
    vector<tuple<int,int,int>> Qry;
    for(int i=0; i<Xc.size(); i++) for(auto [l,r] : X[i]) Upd.emplace_back(Xc[i], Index(C, l), Index(C, r));
    for(int i=0; i<Yc.size(); i++) for(auto [l,r] : Y[i])
        Qry.emplace_back(Index(C, Yc[i]), l-1, -1),
        Qry.emplace_back(Index(C, Yc[i]), r, +1);

    sort(Upd.begin(), Upd.end(), [](const auto &a, const auto &b){ return get<0>(a) < get<0>(b); });
    sort(Qry.begin(), Qry.end(), [](const auto &a, const auto &b){ return get<1>(a) < get<1>(b); });

    int i = 0, j = 0;
    while(i < Upd.size() && j < Qry.size()){
        if(get<0>(Upd[i]) <= get<1>(Qry[j])){
            auto [x,l,r] = Upd[i++]; Add(l, r, 1);
        }
        else{
            auto [y,_,f] = Qry[j++]; Color -= f * Get(y);
        }
    }
    while(j < Qry.size()){
        auto [y,_,f] = Qry[j++]; Color -= f * Get(y);
    }

    cout << 1LL * N * N - Color;
}

7. 골드리치의 비밀 금고

모스 알고리즘을 이용해 해결할 수 있습니다. 세그먼트 트리나 std::set 등을 이용해서 후보들 중에서 가장 작은 수를 선택하면 $O(Q \sqrt N \log N)$이라서 100점을 받을 수 없습니다. 하지만 후보의 변화는 $O(Q \sqrt N)$번 일어나는 반면에 최솟값을 구하는 연산은 $O(Q)$번밖에 일어나지 않는다는 점을 이용하면 $O(1)$ 갱신, $O(\sqrt N)$ 쿼리를 지원하는 자료구조를 사용해 $O(Q \sqrt N)$에 문제를 해결할 수 있습니다.

여담으로, $O(1)$ 갱신, $O(\sqrt N)$ 쿼리를 지원하는 자료구조 대신 std::bitset의 _Find_first()을 이용해도 $O(Q \sqrt N + QN / 64)$ 시간에 해결하여 100점을 받을 수 있습니다.

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
#include <bits/stdc++.h>
using namespace std;
constexpr int SZ = 512;

struct query{
    int s, e, i;
    query() = default;
    query(int s, int e, int i) : s(s), e(e), i(i) {}
    bool operator < (const query &q) const {
        if(s / SZ != q.s / SZ) return s < q.s;
        else return s / SZ % 2 ? e < q.e : e > q.e;
    }
};

struct container{
    vector<int> chk, buc;
    void set(int x){
        if(!chk[x]) chk[x] = 1, buc[x/SZ]++;
    }
    void reset(int x){
        if(chk[x]) chk[x] = 0, buc[x/SZ]--;
    }
    container() : chk(303030), buc(666) {}
    int get() const {
        for(int i=0; i<buc.size(); i++){
            if(!buc[i]) continue;
            int l = i * SZ, r = (i + 1) * SZ;
            for(int j=l; j<r; j++) if(chk[j]) return j;
        }
        return 0;
    }
};

int N, Q, A[303030], R[303030], C[303030];
vector<query> V;
container T;

void Ins(int x){
    C[A[x]]++;
    if(C[A[x]] == 1) T.set(A[x]);
    if(C[A[x]] != 1) T.reset(A[x]);
}
void Del(int x){
    C[A[x]]--;
    if(C[A[x]] == 1) T.set(A[x]);
    if(C[A[x]] != 1) T.reset(A[x]);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N;
    for(int i=1; i<=N; i++) cin >> A[i];
    cin >> Q; V.resize(Q); Q = 0;
    for(auto &[s,e,i] : V) cin >> s >> e, i = ++Q;
    sort(V.begin(), V.end());

    int s = V[0].s, e = V[0].e;
    for(int i=s; i<=e; i++) Ins(i);
    R[V[0].i] = T.get();

    for(int i=1; i<Q; i++){
        while(V[i].s < s) Ins(--s);
        while(e < V[i].e) Ins(++e);
        while(s < V[i].s) Del(s++);
        while(V[i].e < e) Del(e--);
        R[V[i].i] = T.get();
    }

    for(int i=1; i<=Q; i++) cout << R[i] << "\n";
}

8. 브레이크가 고장난 카트

카트가 정지한 상태를 정점으로 나타낸 방향 그래프를 생각해 보면, 한 SCC 안에 있는 모든 정점을 어떻게든 방문할 수 있다는 사실을 알 수 있습니다. 따라서 SCC를 압축한 DAG를 만든 다음 DP를 이용해 최대 개수를 구할 수 있습니다. 실제 이동 방법을 구하는 건 한 SCC 안에 있는 모든 정점을 어떻게든 방문하는 것을 $O(N^2)$ 정도에 잘 구현하면 됩니다.

2017 KAIST 가을 대회 D. Dev, Please Add This!(풀이), 2020 1차 선발고사 4번. 칠하기(풀이)를 풀면 도움이 될 수도 있습니다.

9. 1-2-3 퍼즐

미션 7까지는 손으로 해결할 수 있고, 8~10은 백트래킹을 이용해서 꽤 높은 점수를 받을 수 있습니다.

Round 2-A

1. 장비 교체

일단 모든 장비를 다운그레이드해서 돈을 최대한 많이 모은 다음, 앞에 있는 장비부터 최대한 많이 업그레이드하는 그리디 전략으로 정답을 구할 수 있습니다.

또는, $i, i+1, \cdots, N$번 장비를 다운그레이드해서 얻을 수 있는 돈을 $S[i]$라고 정의하면, 이 배열을 이용해 매번 $O(1)$ 시간에 장비를 업그레이드할지 다운그레이드할지 결정할 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll N, A[505050], B[505050], C;
char R[505050];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N;
    for(int i=1; i<=N; i++) cin >> A[i];
    for(int i=1; i<=N; i++) cin >> B[i];
    for(int i=1; i<=N; i++){
        if(B[i] != -1) C += B[i], R[i] = '-';
        else R[i] = '0';
    }
    for(int i=1; i<=N; i++){
        if(R[i] == '-' && B[i] <= C) C -= B[i], R[i] = '0';
        if(R[i] == '0' && A[i] != -1 && A[i] <= C) C -= A[i], R[i] = '+';
    }
    cout << R+1;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll N, A[505050], B[505050], S[505050], C;
char R[505050];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N;
    for(int i=1; i<=N; i++) cin >> A[i];
    for(int i=1; i<=N; i++) cin >> B[i];
    for(int i=1; i<=N; i++) S[i] = max(0LL, B[i]);
    for(int i=N; i>=1; i--) S[i] += S[i+1];
    for(int i=1; i<=N; i++) R[i] = '0';
    for(int i=1; i<=N; i++){
        if(A[i] != -1 && C + A[i] <= S[i+1]) C += A[i], R[i] = '+';
        else if(B[i] != -1 && C > S[i+1]) C -= B[i], R[i] = '-';
    }
    cout << R+1;
}

2. 루시드의 레이저 공격을 피해라!

만약 x축과 평행한 직선만 주어진다면 주어진 두 점의 y좌표 $y_1, y_2$ 사이에 직선이 있는지 판별하면 되고, 이분 탐색을 이용하면 매번 $O(\log M)$에 확인할 수 있습니다. 마찬가지로 y축에 평행한 직선이 주어지더라도 $O(\log M)$ 시간에 확인할 수 있다.

기울기가 45도 또는 135도인 직선이 주어지면 일차 함수의 y절편으로 이분 탐색을 해도 되지만, 개인적으로 저는 $(x, y)$를 $(x-y, x+y)$로 바꾸는 등의 방법으로 좌표계를 45도 회전시킨 뒤 x축 또는 y축에 평행한 직선처럼 처리하는 것을 선호합니다.

참고로, $(x, y)$를 $(x+y, x-y)$로 바꾸는 것은 아래와 같이 회전 변환을 적용한 뒤 상수 배 한 것을 의미합니다.

\[\begin{pmatrix}\cos 45\degree & -\sin 45\degree \\ \sin 45\degree & \cos 45\degree \end{pmatrix}\begin{pmatrix}x \\ y\end{pmatrix} = \frac{\sqrt 2}{2} \begin{pmatrix} x - y \\ x + y \end{pmatrix}\] 
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
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
using ll = long long;
using Point = pair<ll, ll>;
istream& operator >> (istream &in, Point &p){ return in >> p.x >> p.y; }

Point Rotate(Point p){ return {p.x + p.y, p.x - p.y}; }

vector<int> Solve(vector<Point> st, vector<Point> ed, vector<Point> qs, vector<Point> qe){
    int m = st.size(), q = qs.size();
    vector<int> res(q, 1), xv, yv;
    for(int i=0; i<m; i++){
        if(st[i].x == ed[i].x) xv.push_back(st[i].x);
        if(st[i].y == ed[i].y) yv.push_back(st[i].y);
    }
    sort(xv.begin(), xv.end());
    sort(yv.begin(), yv.end());

    auto on_laser = [&](Point p) -> bool {
        return binary_search(xv.begin(), xv.end(), p.x) || binary_search(yv.begin(), yv.end(), p.y);
    };
    auto inside = [](const vector<int> &v, int l, int r) -> bool {
        return upper_bound(v.begin(), v.end(), r-1) - lower_bound(v.begin(), v.end(), l+1) > 0;
    };

    for(int i=0; i<q; i++){
        if(on_laser(qs[i]) || on_laser(qe[i])) res[i] = 0;
        if(qs[i].x != qe[i].x){
            int x1 = qs[i].x, x2 = qe[i].x;
            if(x1 > x2) swap(x1, x2);
            if(inside(xv, x1, x2)) res[i] = 0;
        }
        if(qs[i].y != qe[i].y){
            int y1 = qs[i].y, y2 = qe[i].y;
            if(y1 > y2) swap(y1, y2);
            if(inside(yv, y1, y2)) res[i] = 0;
        }
    }
    return res;
}

int N, M, Q;
vector<Point> S, E, Q1, Q2;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M >> Q;
    S.resize(M); E.resize(M); Q1.resize(Q); Q2.resize(Q);
    for(int i=0; i<M; i++) cin >> S[i] >> E[i];
    for(int i=0; i<Q; i++) cin >> Q1[i] >> Q2[i];
    auto R1 = Solve(S, E, Q1, Q2);

    for(auto &p : S) p = Rotate(p);
    for(auto &p : E) p = Rotate(p);
    for(auto &p : Q1) p = Rotate(p);
    for(auto &p : Q2) p = Rotate(p);
    auto R2 = Solve(S, E, Q1, Q2);

    for(int i=0; i<Q; i++) cout << (R1[i] && R2[i]) << "\n";
}

3. 기차 여행

일반적으로 최단 경로 알고리즘은 한 시작점에서 다른 모든 정점으로 가는 최단 경로(SSSP)를 구하지만, 이 문제는 도착점이 고정된 상태에서 시작점이 쿼리로 주어집니다. 따라서 그래프의 방향을 뒤집어서 처리하는 것이 편할 것이라는 생각을 자연스럽게 할 수 있습니다.

시점 $t$에 $v$번 정점에 있는 상태를 순서쌍 $(v, t)$로 표현하면, 기차 $(s, t_s, d, t_d)$는 $(d, t_d)$에서 $(s, t_s)$로 상태를 전이하는 것이라고 생각할 수 있습니다. 따라서 각 순서쌍을 정점으로 하고, 기차를 통한 상태 전이를 간선으로 표현한 그래프를 만듭시다. 유의미한 정점만 만들면 정점이 $2M + Q$개, 간선이 $3M+Q$개인 그래프가 만들어집니다.

쿼리의 답을 구하는 것은 $(K, t)$를 $t$가 증가하는 순서대로 보면서, 방문하는 정점에 $t$를 기록하는 방식으로 각 정점에 도달하는 가장 빠른 시간을 구할 수 있습니다. 이는 DFS, BFS 등으로 방문하지 않은 정점만 방문하는 방식으로 처리할 수 있습니다.

좌표 압축이 들어가기 때문에 시간 복잡도는 $O((M+Q) \log (M+Q))$입니다.

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
#include <bits/stdc++.h>
using namespace std;

int N, M, K, Q, R[707070];
vector<tuple<int,int,int,int>> E;
vector<pair<int,int>> T;
vector<pair<int,int>> C;
vector<int> G[707070];

void DFS(int v, int c){
    R[v] = c;
    for(auto i : G[v]) if(R[i] == -1) DFS(i, c);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M >> K >> Q; E.resize(M); T.resize(Q);
    for(auto &[a,b,c,d] : E) cin >> a >> b >> c >> d, C.emplace_back(a, b), C.emplace_back(c, d);
    for(auto &[a,b] : T) cin >> a >> b, C.emplace_back(a, b);
    sort(C.begin(), C.end());
    C.erase(unique(C.begin(), C.end()), C.end());

    for(auto [a,b,c,d] : E){
        int s = lower_bound(C.begin(), C.end(), make_pair(c,d)) - C.begin();
        int e = lower_bound(C.begin(), C.end(), make_pair(a,b)) - C.begin();
        assert(C[s] == make_pair(c,d));
        assert(C[e] == make_pair(a,b));
        G[s].push_back(e);
    }
    for(int i=1; i<C.size(); i++) if(C[i-1].first == C[i].first) G[i].push_back(i-1);

    memset(R, -1, sizeof R);
    for(int i=0; i<C.size(); i++) if(C[i].first == K && R[i] == -1) DFS(i, C[i].second);

    for(int i=0; i<Q; i++) cout << R[lower_bound(C.begin(), C.end(), T[i]) - C.begin()] << "\n";
}

4. 트리 읽기

HLD를 이용해 경로를 $O(\log N)$개의 부분 문자열로 표현한 뒤, 해싱이나 접미사 배열 + LCP 배열 + RMQ를 이용해 부분 문자열의 사전 순 비교를 할 수 있습니다.

해싱을 이용해서 구현할 때 $O(\log N)$개의 부분 문자열을 모두 사전 순 비교를 하면 쿼리당 $O(\log^2 N)$이지만, 완전히 같은 두 부분 문자열을 $O(1)$ 시간에 판별하고 넘어가면 실제로 이분 탐색을 수행해야 하는 부분 문자열을 한 쌍밖에 없으므로 $O(\log N)$에 정답을 구할 수 있습니다.

참고로, 이 문제처럼 swap 연산에 비해 비교 연산이 많이 느린 경우, std::sort 대신 std::stable_sort를 사용하면 실행 시간을 많이 줄일 수 있습니다.

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll P1 = 917, M1 = 998244353;
constexpr ll P2 = 179, M2 = 993244853;

template<ll P, ll M>
struct hasher{
    vector<ll> h, p;
    void build(const string &s){
        int n = s.size();
        h.resize(n+1); for(int i=1; i<=n; i++) h[i] = (h[i-1] * P + s[i-1]) % M;
        p.resize(n+1); p[0] = 1; for(int i=1; i<=n; i++) p[i] = p[i-1] * P % M;
    }
    ll get(int l, int r) const {
        ll res = (h[r] - h[l-1] * p[r-l+1]) % M;
        return res >= 0 ? res : res + M;
    }
};

struct hashing{
    hasher<P1, M1> h1;
    hasher<P2, M2> h2;
    void build(const string &s){ h1.build(s); h2.build(s); }
    pair<ll,ll> get(int l, int r) const { l++; r++; return {h1.get(l, r), h2.get(l, r)}; }
};

int N, M, A[151515];
vector<int> Inp[151515], G[151515];
int Top[151515], Sz[151515], Dep[151515], Par[151515], In[151515], Rev[151515];
string S; hashing H;

int LCP(int s, int e, int l, int r){
    if(e-s == r-l && H.get(s, e) == H.get(l, r)) return e-s+1;
    int lo = 0, hi = min(e-s+1, r-l+1) - 1;
    while(lo < hi){
        int m = (lo + hi + 1) / 2;
        if(H.get(s, s+m-1) == H.get(l, l+m-1)) lo = m;
        else hi = m - 1;
    }
    return lo;
}

void DFS0(int v, int b=-1){
    for(auto i : Inp[v]) if(i != b) Dep[i] = Dep[v] + 1, Par[i] = v, G[v].push_back(i), DFS0(i, v);
}

void DFS1(int v){
    Sz[v] = 1;
    for(auto &i : G[v]){
        DFS1(i); Sz[v] += Sz[i];
        if(Sz[i] > Sz[G[v][0]]) swap(i, G[v][0]);
    }
}

void DFS2(int v){
    static int pv = 0; In[v] = ++pv; Rev[pv] = v;
    for(auto i : G[v]) Top[i] = i == G[v][0] ? Top[v] : i, DFS2(i);
}

pair<int,int> Block(int s, int e){
    if(In[s] <= In[e]) return { In[s] - 1, In[e] - In[s] + 1 };
    else return { N + N - In[s] + 1, In[s] - In[e] + 1 };
}

vector<pair<int,int>> GetPath(int u, int v){
    vector<pair<int,int>> l, r;
    while(Top[u] != Top[v]){
        if(Dep[Top[u]] > Dep[Top[v]]) l.push_back(Block(u, Top[u])), u = Par[Top[u]];
        else r.push_back(Block(Top[v], v)), v = Par[Top[v]];
    }
    l.push_back(Block(u, v));
    l.insert(l.end(), r.rbegin(), r.rend());
    return l;
}

bool Compare(const vector<pair<int,int>> &u, const vector<pair<int,int>> &v){
    int l = 0, r = 0;
    for(auto [st,len] : u) l += len;
    for(auto [st,len] : v) r += len;
    if(l != r) return l < r;
    for(int i=0, j=0, a=0, b=0; i<u.size() && j<v.size(); ){
        int st1 = u[i].first + a, len1 = u[i].second - a;
        int st2 = v[j].first + b, len2 = v[j].second - b;
        int len = min(len1, len2);
        int lcp = LCP(st1, st1+len-1, st2, st2+len-1);
        if(lcp < len) return S[st1+lcp] < S[st2+lcp];
        if(len1 == len) i++, a = 0; else a += len2;
        if(len2 == len) j++, b = 0; else b += len1;
    }
    return l < r;
}

vector<pair<int,int>> P[151515];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M;
    for(int i=1; i<=N; i++) cin >> A[i];
    for(int i=1,u,v; i<N; i++) cin >> u >> v, Inp[u].push_back(v), Inp[v].push_back(u);
    DFS0(1); DFS1(1); DFS2(Top[1]=1);

    for(int i=1; i<=N; i++) S += char(A[Rev[i]]+'0');
    S += "#";
    for(int i=N; i>=1; i--) S += char(A[Rev[i]]+'0');
    H.build(S);

    for(int i=1,u,v; i<=M; i++) cin >> u >> v, P[i] = GetPath(u, v);

    vector<int> O(M);
    iota(O.begin(), O.end(), 1);
    stable_sort(O.begin(), O.end(), [](int a, int b){ return Compare(P[a], P[b]); });
    for(auto i : O) cout << i << "\n";
}

접미사 배열을 이용해 구현하는 경우, 위 코드의 hasher, hashing 클래스와 LCP 함수를 제거한 뒤 아래 코드를 적절히 추가하면 됩니다. 구간 최솟값 쿼리(range minimum query)를 수행할 때 sprase table과 같은 $O(1)$ 쿼리를 지원하는 자료구조가 아닌 $O(\log N)$ 시간에 동작하는 세그먼트 트리 같은 것을 이용하면 쿼리당 $O(\log^2 N)$이 되어 100점을 받을 수 없습니다.

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
pair<vector<int>, vector<int>> SuffixArray(const string &s){
    int n = s.size(), m = max(n, 256);
    vector<int> sa(n), lcp(n), pos(n), tmp(n), cnt(m);
    auto counting_sort = [&](){
        fill(cnt.begin(), cnt.end(), 0);
        for(int i=0; i<n; i++) cnt[pos[i]]++;
        partial_sum(cnt.begin(), cnt.end(), cnt.begin());
        for(int i=n-1; i>=0; i--) sa[--cnt[pos[tmp[i]]]] = tmp[i];
    };
    for(int i=0; i<n; i++) sa[i] = i, pos[i] = s[i], tmp[i] = i;
    counting_sort();
    for(int k=1; ; k<<=1){
        int p = 0;
        for(int i=n-k; i<n; i++) tmp[p++] = i;
        for(int i=0; i<n; i++) if(sa[i] >= k) tmp[p++] = sa[i] - k;
        counting_sort();
        tmp[sa[0]] = 0;
        for(int i=1; i<n; i++){
            tmp[sa[i]] = tmp[sa[i-1]];
            if(sa[i-1]+k < n && sa[i]+k < n && pos[sa[i-1]] == pos[sa[i]] && pos[sa[i-1]+k] == pos[sa[i]+k]) continue;
            tmp[sa[i]] += 1;
        }
        swap(pos, tmp);
        if(pos[sa.back()] + 1 == n) break;
    }
    for(int i=0, j=0; i<n; i++, j=max(j-1,0)){
        if(pos[i] == 0) continue;
        while(sa[pos[i]-1]+j < n && sa[pos[i]]+j < n && s[sa[pos[i]-1]+j] == s[sa[pos[i]]+j]) j++;
        lcp[pos[i]] = j;
    }
    return {sa, lcp};
}

struct RMQ{
    vector<vector<int>> st;
    vector<int> lg;
    RMQ() = default;
    RMQ(const vector<int> &a){
        int n = a.size();
        st = vector<vector<int>>(__lg(n)+1, vector<int>(n));
        for(int i=0; i<n; i++) st[0][i] = a[i];
        for(int i=1; i<st.size(); i++) for(int j=0; j<n; j++) if(j + (1<<i) - 1 < n) st[i][j] = min(st[i-1][j], st[i-1][j+(1<<(i-1))]);
        lg.resize(n);
        for(int i=0; i<st.size(); i++) lg[1<<i] = i;
        for(int i=1; i<n; i++) if(!lg[i]) lg[i] = lg[i-1];
    }
    int query(int l, int r) const {
        if(l > r) return 0x3f3f3f3f;
        int k = lg[r-l+1];
        return min(st[k][l], st[k][r-(1<<k)+1]);
    }
};

vector<int> SA, Lcp, Pos;
RMQ Q;

int LCP(int s, int e, int l, int r){
    if(s == l) return min(e-s+1, r-l+1);
    int len = min(e-s+1, r-l+1);
    int u = Pos[s], v = Pos[l];
    if(u > v) swap(u, v);
    return min(Q.query(u+1, v), len);
}

int main(){
    // ...
    tie(SA,Lcp) = SuffixArray(S); Pos.resize(S.size());
    for(int i=0; i<S.size(); i++) Pos[SA[i]] = i;
    Q = RMQ(Lcp);
    // ...
}

Round 2-B

1. 순열로 고치기

1 이상 $N$ 이하의 수 중 여러 번 등장하는 수가 있다면 가장 뒤에 있는 수를 제외한 모든 수를 변경하는 것이 최적입니다. 따라서 1 이상 $N$ 이하의 수가 등장하는 마지막 인덱스를 구한 뒤, 그렇지 않은 모든 인덱스의 합을 구하면 됩니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll N, A[101010], B[101010], P[101010], R;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N;
    for(int i=1; i<=N; i++) cin >> A[i];
    for(int i=1; i<=N; i++) if(A[i] <= N) P[A[i]] = i;
    for(int i=1; i<=N; i++) B[P[i]] = i;
    for(int i=1; i<=N; i++) if(!B[i]) R += i;
    cout << R;
}

2. 계단

$i$번째 수를 마지막으로 하는 공차가 $d$인 등차 수열의 개수를 $D(i, d)$라고 정의합시다. $i$의 정의역의 크기는 $N$, $d$의 정의역의 크기는 $10^9$이지만, 실제로 의미있는 상태는 $O(N^2)$개밖에 없습니다.

상태 전이는 $D(j, A_i - A_j) \rightarrow D(i, A_i - A_j)$와 같이 설계할 수 있고, std::map과 같은 연관 배열을 사용하거나 실제로 의미있는 $d$만 좌표 압축해서 관리하는 방식으로 $O(N^2 \log 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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int MOD = 1e9+7;
inline void Add(int &a, const int b){ if((a += b) >= MOD) a -= MOD; }

void Compress(vector<int> &v){
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
}

int Index(const vector<int> &v, int x){
    int pos = lower_bound(v.begin(), v.end(), x) - v.begin();
    return pos < v.size() && v[pos] == x ? pos : -1;
}

int N, A[2020], D[2020][2020], R;
vector<int> C[2020];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N;
    for(int i=1; i<=N; i++) cin >> A[i];
    for(int i=1; i<=N; i++) for(int j=i-1; j>=1; j--) C[i].push_back(A[i]-A[j]);
    for(int i=1; i<=N; i++) Compress(C[i]);
    for(int i=1; i<=N; i++){
        for(int j=i+1; j<=N; j++){
            int pos = Index(C[j], A[j]-A[i]); Add(D[j][pos], 1);
            if(int prv=Index(C[i], A[j]-A[i]); prv != -1) Add(D[j][pos], D[i][prv]);
        }
    }
    for(int i=1; i<=N; i++) for(int j=0; j<C[i].size(); j++) Add(R, D[i][j]);
    cout << R;
}

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int MOD = 1e9+7;
inline void Add(int &a, const int b){ if((a += b) >= MOD) a -= MOD; }

int N, A[2020], R;
map<int, int> D[2020];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N;
    for(int i=1; i<=N; i++) cin >> A[i];
    for(int i=1; i<=N; i++){
        for(int j=i+1; j<=N; j++){
            auto it = D[j].find(A[j]-A[i]);
            if(it == D[j].end()) it = D[j].emplace(A[j]-A[i], 0).first;
            Add(it->second, 1);

            auto prv = D[i].find(A[j]-A[i]);
            if(prv != D[i].end()) Add(it->second, prv->second);
        }
    }
    for(int i=1; i<=N; i++) for(auto [a,b] : D[i]) Add(R, b);
    cout << R;
}

3. 점 짝짓기

일차원에서의 문제를 먼저 해결해 봅시다. $X_1, X_2, \cdots, X_N$이 오름차순으로 주어지면, $X_N - X_1$, $X_{N-1} - X_2$, $X_{N-2}, X_3$, $\cdots$ 와 같이 매칭하는 것이 최적이라는 것은 어렵지 않게 알 수 있습니다. 그리고 이는 $X_{N/2+1} - X_1$, $X_{N/2+2} - X_2$, $X_{N/2+3} - X_3$, $\cdots$ 와 같이 매칭하더라도 값이 바뀌지 않습니다.

이차원에서의 답은 x좌표와 y좌표를 나눠서 각각 해결한 것의 합 이하이며, 이 값을 달성하는 방법이 존재합니다.

주어진 x좌표들을 오름차순으로 정렬한 것을 $X_1, X_2, \cdots, X_N$, y좌표들을 오름차순으로 정렬한 것을 $Y_1, Y_2, \cdots, Y_N$이라고 합시다. $(X_{N/2}, Y_{N/2})$가 원점이 되도록 조정하면, (1사분면의 개수) = (3사분면의 개수), (2사분면의 개수) = (4사분면의 개수)가 됩니다. 따라서 1사분면의 점과 3사분면의 점을 매칭하고, 2사분면의 점과 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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll N, S, X[202020], Y[202020];
struct Point{ ll x, y, v, i; } A[202020];
vector<int> V[4];
vector<pair<int,int>> R;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N;
    for(int i=1; i<=N; i++) cin >> X[i] >> Y[i];
    for(int i=1; i<=N; i++) A[i] = { X[i], Y[i], 0, i };
    nth_element(A+1, A+N/2, A+N+1, [](auto a, auto b){ return a.x < b.x; });
    for(int i=1; i<=N/2; i++) A[i].v |= 1;
    nth_element(A+1, A+N/2, A+N+1, [](auto a, auto b){ return a.y < b.y; });
    for(int i=1; i<=N/2; i++) A[i].v |= 2;
    for(int i=1; i<=N; i++) V[A[i].v].push_back(A[i].i);
    for(int x : {0, 1}){
        int y = 3 ^ x;
        while(!V[x].empty() && !V[y].empty()){
            int i = V[x].back(), j = V[y].back();
            V[x].pop_back(); V[y].pop_back();
            R.emplace_back(i, j);
            S += abs(X[i] - X[j]) + abs(Y[i] - Y[j]);
        }
    }

    cout << S << "\n";
    for(auto [x,y] : R) cout << x << " " << y << "\n";
}

4. 합주 공연

h가 등장하지 않는 구간에서 문제의 정답은 (e의 개수)와 (g의 개수)의 최솟값입니다. 따라서 h를 기준으로 쪼개서 답을 구하면 되며, 갱신과 구간 쿼리가 주어지는 상황에서는 흔히 “금광 세그먼트 트리”라고 부르는 자료구조를 이용해 해결할 수 있습니다. 세그먼트 트리의 각 정점에서 다음과 같은 값을 관리하면 됩니다.

  • 첫 h가 나오기 전까지 e가 등장한 횟수
  • 첫 h가 나오기 전까지 g가 등장한 횟수
  • 마지막 h가 나온 이후로 e가 등장한 횟수
  • 마지막 h가 나온 이후로 g가 등장한 횟수
  • 첫 h와 마지막 h 사이에 있는 구간에서의 정답
  • 구간의 길이
  • 구간에 h가 있는지 여부

$O(N + Q \log 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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
using namespace std;
constexpr int SZ = 1 << 20;
const string S = "heg";

struct node{
    int lx, ly, rx, ry, md, sz, full;
    node() : node(0) {}
    node(int v) : node(v==1, v==2, v==1, v==2, 0, 1, v!=0) {}
    node(int lx, int ly, int rx, int ry, int md, int sz, int full)
        : lx(lx), ly(ly), rx(rx), ry(ry), md(md), sz(sz), full(full) {}
};

node operator + (const node &a, const node &b){
    return {
        a.lx + (a.full ? b.lx : 0),
        a.ly + (a.full ? b.ly : 0),
        (b.full ? a.rx : 0) + b.rx,
        (b.full ? a.ry : 0) + b.ry,
        a.md + b.md + (!a.full && !b.full ? min(a.rx + b.lx, a.ry + b.ly) : 0),
        a.sz + b.sz, a.full && b.full
    };
}

int N, Q, A[1010101]; node T[SZ<<1];
void Set(int x, int v){ for(T[x|=SZ]=v; x>>=1; ) T[x] = T[x<<1] + T[x<<1|1]; }
int Get(int l, int r){
    node lv, rv;
    for(l|=SZ, r|=SZ; l<=r; l>>=1, r>>=1){
        if(l & 1) lv = lv + T[l++];
        if(~r & 1) rv = T[r--] + rv;
    }
    lv = lv + rv;
    return lv.md + min(lv.lx, lv.ly) + (lv.full ? 0 : min(lv.rx, lv.ry));
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> Q;
    for(int i=1; i<=N; i++){ char c; cin >> c; A[i] = S.find(c); }
    for(int i=1; i<=N; i++) T[i|SZ] = A[i];
    for(int i=SZ-1; i; i--) T[i] = T[i<<1] + T[i<<1|1];
    for(int q=1; q<=Q; q++){
        int x, s, e; char v; cin >> x >> v >> s >> e;
        Set(x, S.find(v));
        cout << Get(s, e) << "\n";
    }
}