2021 SCPC 1차예선/2차예선 풀이 및 후기

작성일 | In

서론

본선 떨어지면 창피할까 봐 1차 예선 후기도 안 올렸는데, 다행히 본선 진출할 것 같아서 1/2차 후기를 함께 올립니다.

점수는 다음과 같습니다.

번호 1차 예선 점수 2차 예선 점수
1 친구들 80/80 원 안의 점 100/100
2 이진수 150/150 직8각형 200/200
3 No Cycle 180/180 산탄총 300/300
4 예약 시스템 88/190 패턴 매칭 209/400
5 차이 200/200 Hanoi Tower 33/500
총합   698/800   842/1500

데스크탑에서 보시는 분들은 오른쪽 사이드바를 활용하시면 원하는 문제로 쉽게 이동하실 수 있습니다.

1차 예선

1차 예선답게 쉬운 문제들이 출제되었습니다. 1235 풀고 4번 제출했는데 88점 밖에 안 나오길래 디버깅하기 귀찮아서 던지고 자러갔습니다.

1. 친구들

$i$와 $i+D_i$를 연결하고 컴포넌트의 개수를 세면 됩니다.

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

int N, A[101010], P[101010];
int Find(int v){ return v == P[v] ? v : P[v] = Find(P[v]); }
bool Merge(int u, int v){
    u = Find(u); v = Find(v);
    if(u == v) return false;
    P[u] = v; return true;
}

void Solve(){
    cin >> N; iota(P+1, P+N+1, 1);
    int R = N;
    for(int i=1; i<=N; i++){
        cin >> A[i];
        if(i+A[i] <= N) R -= Merge(i, i+A[i]);
    }
    cout << R << "\n";
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int T; cin >> T;
    for(int tc=1; tc<=T; tc++){
        cout << "Case #" << tc << "\n";
        Solve();
    }
}

2. 이진수

??? : Lexicographical 2-SAT

문제를 보자마자 Lexicographical 2-SAT을 검색해봤지만 아무것도 얻지 못했습니다.

정답은 “무조건 0 / 무조건 1인 위치”를 먼저 처리한 뒤, 앞에서부터 최대한 0을 많이 배치하는 그리디 알고리즘을 이용해 구할 수 있습니다.

만약 $A_i = 0$이라면 $B_{i-T}$와 $B_{i+T}$는 0이 되어야 합니다. 또한, $i \leq K$이거나 $i \geq N-K$이면 $B_i$에 관여하는 $A$의 값이 1개 이하이므로 값을 결정할 수 있습니다. 이렇게 답을 고정하고 나면 답이 고정되지 않은 위치가 남아있을텐데, 해당 위치에는 1이 와도 상관 없다는 것을 알 수 있습니다.

이제, 앞에서부터 최대한 0을 많이 배치하는 그리디 알고리즘을 수행합니다. 구체적으로, 앞에서부터 “아직 확정이 안 된 위치”를 차례대로 순회하면서, 해당 위치에 0을 넣어도 올바른 비트열을 만들 수 있는지 확인하면 됩니다.

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

int N, K, A[50505], B[50505];

void Solve(){
    cin >> N >> K;
    for(int i=1; i<=N; i++){
        char c; cin >> c; A[i] = c - '0';
    }
    for(int i=1; i<=N; i++) B[i] = -1;
    for(int i=1; i<=K; i++){
        int j = N - i + 1;
        if(i+K <= N) B[i+K] = A[i];
        if(j-K >= 1) B[j-K] = A[j];
    }
    for(int i=1; i<=N; i++){
        if(!A[i]){
            if(i+K <= N) B[i+K] = 0;
            if(i-K >= 1) B[i-K] = 0;
        }
    }

    for(int i=1; i<=N; i++){
        if(!A[i]) continue;
        int l = i - K, r = i + K, now = 0;
        if(l >= 1) now |= B[l] == 1;
        if(r <= N) now |= B[r] == 1;
        if(!now){
            if(r <= N && B[r] != 0) B[r] = 1;
            else B[l] = 1;
        }
    }
    for(int i=1; i<=N; i++) cout << (B[i] == 1);
    cout << "\n";
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int T; cin >> T;
    for(int tc=1; tc<=T; tc++){
        cout << "Case #" << tc << "\n";
        Solve();
    }
}

3. No Cycle

??? : Reachability Problem

방향 간선으로만 위상 정렬을 한 뒤, $v$에서 $u$로 가는 경로가 없다면(간선 $(u,v)$를 추가해도 사이클이 안 생기면) $0$, $v$에서 $u$로 가는 경로가 있다면 $1$을 출력하면 됩니다. AMPPZ의 모 문제가 생각나서 Reachability Problem를 검색했지만 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
48
49
 
#include <bits/stdc++.h>
using namespace std;

int N, M, K, S[2020], E[2020], R[2020], C[555], pv;
vector<int> G[2020];
int que[555], head, rear;

void Clear(){
    for(int i=1; i<=N; i++) G[i].clear();
}

bool Check(int s, int e){
    head = rear = 0; pv++;
    que[rear++] = s; C[s] = pv;
    while(head < rear){
        int v = que[head++];
        if(v == e) return true;
        for(auto i : G[v]) if(C[i] != pv) que[rear++] = i, C[i] = pv;
    }
    return false;
}

void Solve(){
    cin >> N >> M >> K; Clear();
    for(int i=1; i<=M; i++){
        int s, e; cin >> s >> e;
        G[s].push_back(e);
    }
    for(int i=1; i<=K; i++) cin >> S[i] >> E[i];

    for(int i=1; i<=K; i++){
        if(Check(S[i], E[i])) R[i] = 0;
        else if(!Check(E[i], S[i])) R[i] = 0;
        else R[i] = 1;
        if(R[i] == 0) G[S[i]].push_back(E[i]);
        else G[E[i]].push_back(S[i]);
    }
    for(int i=1; i<=K; i++) cout << R[i];
    cout << "\n";
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int T; cin >> T;
    for(int tc=1; tc<=T; tc++){
        cout << "Case #" << tc << "\n";
        Solve();
    }
}

4. 예약 시스템 (X)

5번을 풀어서 4번은 대충 긁고 다시 자러갔습니다.

5. 차이

BOJ 3830 교수님은 기다리지 않는다와 똑같은 문제입니다. (풀이)

위 링크에 나와있는 것처럼 Union-Find로 풀면 되지만, 2년 전보다 실력이 감소했는지 도저히 이쁘게 구현할 방법이 떠오르지 않아 Heavy Light Decomposition을 들고 와서 밀었습니다.

사실 Link Cut Tree 짜다가 중간에 멈춘 거라서, 이정도면 양호하다고 생각합니다.

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
115
116
117
 
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
using PII = pair<int, int>;
constexpr int SZ = 1 << 17;

struct UnionFind{
    int P[SZ], F[SZ];
    void clear(){ iota(P, P+SZ, 0); memset(F, 0, sizeof F); }
    int find(int v){ return v == P[v] ? v : P[v] = find(P[v]); }
    bool merge(int u, int v){
        u = find(u); v = find(v);
        if(u == v) return false;
        F[v] |= F[u]; P[u] = v;
        return true;
    }
    bool check(int u, int v){ return find(u) == find(v); }
    void set(int v){ F[find(v)] = 1; }
    int get(int v){ return F[find(v)]; }
};
struct FenwickTree{
    int T[SZ];
    void add(int x, int v){ for(x+=5; x<SZ; x+=x&-x) T[x] += v; }
    int get(int x){ int ret = 0; for(x+=5; x; x-=x&-x) ret += T[x]; return ret; }
    int get(int l, int r){ return get(r) - get(l-1); }
    void clear(){ memset(T, 0, sizeof T); }
};

int N, Q;
vector<PII> Inp[101010];
vector<int> G[101010];
int top[101010], dep[101010], par[101010], sz[101010], in[101010], w[101010], pv;
UnionFind uf;
FenwickTree tree;

void dfs(int v, int b = -1){
    for(auto i : Inp[v]) if(i.x != b) G[v].push_back(i.x), w[i.x] = i.y, dfs(i.x, v);
}
void dfs1(int v){
    sz[v] = 1;
    for(auto &i : G[v]){
        dep[i] = dep[v] + 1; par[i] = v;
        dfs1(i); sz[v] += sz[i];
        if(sz[i] > sz[G[v][0]]) swap(i, G[v][0]);
    }
}
void dfs2(int v){
    in[v] = ++pv;
    for(auto i : G[v]) top[i] = (i == G[v][0]) ? top[v] : i, dfs2(i);
}
void hld(int root){
    pv = 0; dfs(root); dfs1(root); dfs2(top[root] = root);
    for(int i=1; i<=N; i++) tree.add(in[i], w[i]);
}
int query(int v){
    int ret = 0;
    for(; v; v=par[top[v]]) ret += tree.get(in[top[v]], in[v]);
    return ret;
}
int query(int u, int v){ return query(u) - query(v); }

int Type[202020], A[202020], B[202020], D[202020], Fail[202020];

void Clear(){
    uf.clear();
    tree.clear();
    for(int i=1; i<=N+1; i++) Inp[i].clear();
    for(int i=1; i<=N+1; i++) G[i].clear();
    for(int i=1; i<=Q; i++) Fail[i] = 0;
}

void Solve(){
    cin >> N >> Q; Clear();
    for(int i=1; i<=Q; i++){
        cin >> Type[i] >> A[i] >> B[i];
        if(Type[i] == 1){
            cin >> D[i];
            if(uf.merge(A[i], B[i])){
                Inp[A[i]].emplace_back(B[i], -D[i]);
                Inp[B[i]].emplace_back(A[i], D[i]);
            }
        }
        if(Type[i] == 2){
            if(!uf.check(A[i], B[i])) Fail[i] = 1;
        }
    }
    for(int i=1; i<=N; i++){
        if(uf.find(i) == i){
            Inp[N+1].emplace_back(i, 0);
            Inp[i].emplace_back(N+1, 0);
        }
    }
    hld(++N);

    uf.clear();
    for(int i=1; i<=Q; i++){
        if(Type[i] == 1){
            uf.merge(A[i], B[i]);
            if(query(A[i], B[i]) != D[i]) uf.set(A[i]);
        }
        else{
            if(Fail[i]) cout << "NC\n";
            else if(uf.get(A[i])) cout << "CF\n";
            else cout << query(A[i], B[i]) << "\n";
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int T; cin >> T;
    for(int tc=1; tc<=T; tc++){
        cout << "Case #" << tc << "\n";
        Solve();
    }
}

2차 예선

미친듯이 말렸습니다. 1번은 풀어본 문제라서 빨리 풀었고 2번도 운좋게 전체 20번째로 풀긴 했지만, 그 다음부터 엄청 말렸습니다.

3번 문제 Subtask 1/2를 긁기 위한 코드를 7번이나 제출했지만 모두 0점을 받아서 멘탈이 심하게 흔들렸습니다. 이러다 300점으로 마무리하겠다는 생각이 들어서 4번을 먼저 풀었습니다.
처음에는 4번에서 쓸데 없는 log를 붙여서 81점만 받았습니다. 이 당시에는 시간 복잡도를 정확하게 계산하지 않아서 단순히 제 풀이가 느린 풀이라고 생각하고 넘어갔습니다.

다시 3번으로 돌아와서, 코드를 전부 밀고 처음부터 다시 짰습니다. 2차원 펜윅 트리를 이용한 $O(N^2K \log^2 N)$ 풀이를 제출해서 47점을 받았습니다. 코드를 잠시 살펴보니 펜윅 트리 대신 누적합 배열을 써도 충분하다는 것을 깨닫고 $O(N^2K)$ 풀이를 제출해서 107점을 추가로 받았습니다.

3번에서 log^2를 떼고 나니 4번 풀이에 붙은 쓸데 없는 log가 생각나서 없애고 128점을 추가로 받았습니다. 이때가 대회 종료 4시간 전입니다.

제출 기회가 한 번 밖에 남지 않은 3번 문제와 건들지도 않은 5번 문제 중 어떤 것을 잡을지 고민했고, 먼저 완전탐색으로 빠르게 5번을 긁기로 결정했습니다. 대충 $O(3^N)$짜리 BFS를 구현해서 $N = 18$인 문제를 해결해 33점을 받았습니다.

3번 문제 풀이가 떠오르지 않아서 침대에 누워있었는데, 대회 종료 80분 전에 갑자기 풀이가 떠올라서 구현을 시작했습니다. 인덱스 실수가 수십 번 발생했고, 4번 정도 갈아엎어서 예제가 나오는 코드를 완성한 것이 대회 종료 5분 전이었습니다. 로컬에서 돌려보니 8초 걸려서(TL은 3초) 최적화를 시도했지만 7초까지 밖에 줄이지 못했습니다.
대회 종료 1분 전에 FastIO를 사용할까 고민했지만, 5년 전 모종의 사건 때문에 혹시 몰라서 사용하지 않기로 결정했습니다. 결국 로컬에서 7초 걸리는 코드를 대회 종료 30초 전에 제출했고, 다행히 AC를 받으면서 한숨을 돌렸습니다.

하루를 온전히 PS에 투자하는 경험은 약 1년 만에 해봤는데, 정말 즐거웠습니다.

문제 난이도는 1번 G? / 2번 P5 / 3번 P1-D5 / 4번 Subtask2 D5 / 4번 D3으로 예상합니다.

1. 원 안의 점

Atcoder ABC-D에 나와서 많은 이들을 고통스럽게 했던 ABC191-D Circle Lattice Points의 하위 호환입니다.

$Y$축 기준으로 반으로 자른 뒤, 각 $X$좌표마다 가능한 $Y$좌표의 최대/최소값을 투포인터 느낌으로 관리하면 $O(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
27
28
29
30
31
32
33
34
 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void Solve(){
    ll R, ans = 0;
    cin >> R;

    ll up = R, dw = -R;
    for(ll i=0; i<R; i++){
        while(i*i + up*up >= R*R) up--;
        while(i*i + dw*dw >= R*R && up >= dw) dw++;
        if(up < dw) break;
        ans += up - dw + 1;
    }

    up = R; dw = -R;
    for(ll i=1; i<R; i++){
        while(i*i + up*up >= R*R) up--;
        while(i*i + dw*dw >= R*R && up >= dw) dw++;
        if(up < dw) break;
        ans += up - dw + 1;
    }
    cout << ans << "\n";
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int T; cin >> T;
    for(int tc=1; tc<=T; tc++){
        cout << "Case #" << tc << "\n";
        Solve();
    }
}

2. 직8각형

점이 8개니까 $8!=40\,320$개의 순열을 모두 보면서, 각 점이 직8각형의 꼭짓점이 되는 모든 경우를 고려해도 됩니다. 또한, $L_1$거리를 사용하기 때문에 $X$, $Y$좌표를 독립적으로 생각할 수 있습니다.

$p_0$의 위치를 $(X_0, Y_0)$이라고 정의합시다. $p_1, \cdots, p_7$의 위치는 각각 $(X_0, Y_0+K)$, $(X_0+K, Y_0+2K)$, $(X_0+2K, Y_0+2K)$, $(X_0+3K, Y_0+K)$, $(X_0+3K, Y_0)$, $(X_0+2K, Y_0-K)$, $(X_0+K, Y_0-K)$입니다.
두 배열 $dx[] = \left{ 0,0,1,2,3,3,2,1 \right}$, $dy[] = \left{ 0,1,2,2,1,0,-1,-1 \right}$을 정의하면, $p_i = (X_0 + dx[i]\cdot K, Y_0 + dy[i]\cdot K)$로 표현할 수 있습니다.

점 $(x_i, y_i)$를 $p_i$와 매칭시키는 비용은 $\vert x_i - X_0 - dx[i]\cdot K \vert + \vert y_i - Y_0 - dy[i]\cdot K \vert$입니다. 즉, $\sum_i \vert x_i - X_0 - dx[i] \cdot K \vert$와 $\sum_i \vert y_i - Y_0 - dy[i]\cdot K$를 최소화하는 $X_0, Y_0$을 찾아야 합니다. 그러한 $X_0, Y_0$은 절댓값 기호 안에 있는 식을 0으로 만드는 값들의 중앙값($x_i-dx[i]\cdot K$, $y_i-dy[i]\cdot K$의 중앙값)이라는 것이 잘 알려져 있으므로 적절한 방법을 이용해 중앙값을 찾으면 됩니다. 저는 std::nth_element를 이용했습니다.

시간 제한 관련해서 이슈가 있었던 것으로 아는데, 저는 별 문제 없었습니다 :yum:

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
 
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using Point = pair<ll, ll>;
constexpr int dx[8] = { 0, 0, 1, 2, 3, 3, 2, 1 };
constexpr int dy[8] = { 0, 1, 2, 2, 1, 0, -1, -1 };

array<Point, 8> A;
ll K, X[8], Y[8];

ll Calc(){
    ll ret = 0;
    for(int i=0; i<8; i++){
        X[i] = A[i].x - K * dx[i];
        Y[i] = A[i].y - K * dy[i];
    }
    nth_element(X, X+4, X+8);
    nth_element(Y, Y+4, Y+8);
    for(int i=0; i<8; i++){
        ll xx = X[4] + K * dx[i];
        ll yy = Y[4] + K * dy[i];
        ret += abs(A[i].x - xx) + abs(A[i].y - yy);
    }
    return ret;
}

void Solve(){
    ll R = 0x3f3f3f3f3f3f3f3f;
    cin >> K;
    for(auto &i : A) cin >> i.x >> i.y;
    sort(all(A));
    do R = min(R, Calc()); while(next_permutation(all(A)));
    cout << R << "\n";
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int T; cin >> T;
    for(int tc=1; tc<=T; tc++){
        cout << "Case #" << tc << "\n";
        Solve();
    }
}

3. 산탄총

Subtask2 풀이($O(N^2K)$)풀이부터 알아봅시다.

다이아몬드 격자는 45도 회전하는 것이 좋습니다. $(i, j)$를 $(i-j, i+j)$로 바꾸면 됩니다. $A_{i,j}$가 영향을 주는 위치는 아래 그림처럼 나타낼 수 있습니다. 오른쪽의 회색 격자는 실제로 사용하지 않는 칸이므로 신경쓰지 않아도 됩니다.

45도 회전시킨 오른쪽 그림을 보면, 직사각형 영역에 1을 더하는 것을 $K$번 더한 결과와 동일하다는 것을 알 수 있습니다. 그러므로 $O(N^2)$개의 모든 칸에 대해 $O(K)$개의 직사각형 영역을 1 증가시키는 작업을 2D Prefix Sum을 이용해 수행하면 $O(N^2K)$에 문제를 풀어 154점을 얻을 수 있습니다.

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
 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int N4 = 888;

ll N, K, A[N4][N4], T[N4][N4];

void Skip(){
    for(int i=1; i<=N; i++) for(int j=1,t; j<=N; j++) cin >> t;
    cout << 0 << endl;
}

void Update(int r1, int c1, int r2, int c2, ll v){
    T[r2][c2] += v; T[r1-1][c2] -= v; T[r2][c1-1] -= v; T[r1-1][c1-1] += v;
}
void Coloring(int i, int j){
    int r1 = i - K + 1, r2 = i + K - 1;
    int c1 = j - K + 1, c2 = j + K - 1;
    for(int t=1; t<=K; t++, r1++, r2--, c1++, c2--){
        Update(r1, c1, r2, c2, A[i][j]);
    }
}

void Solve(){
    cin >> N >> K;
    if(N > 200){ Skip(); return; }
    for(int i=1; i<=N; i++) for(int j=1,t; j<=N; j++) cin >> t, A[i-j+N+N][i+j+N] = t;

    memset(T, 0, sizeof T);
    for(int i=1; i<=N; i++) for(int j=1; j<=N; j++) Coloring(i-j+N+N, i+j+N);
    for(int i=0; i<4*N; i++){
        for(int j=0; j<4*N; j++){
            if(i) T[i][j] += T[i-1][j];
            if(j) T[i][j] += T[i][j-1];
            if(i && j) T[i][j] -= T[i-1][j-1];
        }
    }

    ll mx = 0;
    for(int i=0; i<4*N; i++) for(int j=0; j<4*N; j++)
        if((i+j&1) == (N&1)) mx = max(mx, T[i][j]);
    cout << mx << endl;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int T; cin >> T;
    for(int tc=1; tc<=T; tc++){
        cout << "Case #" << tc << "\n";
        Solve();
    }
}

이 풀이를 열심히 최적화하면 $O(N^2)$ 풀이를 얻을 수 있습니다.

2D Prefix Sum을 구하기 위해 2차원 배열에 더하는 값은 아래 그림처럼 나타낼 수 있습니다.

어? 굉장히 익숙한 그림입니다. 대각선 구간에 하나씩 더하는 대신, 대각선에 대한 누적합도 같이 관리하면 됩니다!

수행할 작업들 간의 관계가 상당히 복잡합니다. 정리하자면,

  1. 대각선 방향의 누적합을 관리하기 위해 $O(N^2)$개의 포인트에 덧셈을 하고 누적합을 $O(N^2)$ 시간에 구합니다.
  2. (1)에서 구한 값을 이용해 Subtask2에서 관리하는 2D Prefix Sum을 $O(N^2)$시간에 구합니다.
  3. (2)에서 2D Prefix Sum을 이용해 실제 최댓값을 구합니다.

전체 문제를 $O(N^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
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
 
#pragma GCC optimize ("O3")
#pragma GCC target ("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int N4 = 2400;

ll N, K, A[N4][N4], T[N4][N4], X[N4][N4], Y[N4][N4];

void Clear(){
    for(int i=0; i<N*4; i++) memset(T[i], 0, sizeof(ll) * (N*4));
    for(int i=0; i<N*4; i++) memset(X[i], 0, sizeof(ll) * (N*4));
    for(int i=0; i<N*4; i++) memset(Y[i], 0, sizeof(ll) * (N*4));
}

bool Bound(int i, int j){
    return 0 <= i && i < 4*N && 0 <= j && j < 4*N;
}
void Coloring(int i, int j){
    int r1 = i - K + 1, r2 = i + K - 1;
    int c1 = j - K + 1, c2 = j + K - 1;
    X[r1-1][c1-1] += A[i][j];
    X[r2+1][c2+1] -= A[i][j];
    Y[r1-1][c2] -= A[i][j];
    Y[r2+1][c1-2] += A[i][j];
}
void Sum1(int i, int j){
    const int di = 1, dj = 1;
    T[i][j] += X[i][j];
    for(i+=di, j+=dj; Bound(i, j); i+=di, j+=dj){
        X[i][j] += X[i-di][j-dj];
        T[i][j] += X[i][j];
    }
}
void Sum2(int i, int j){
    const int di = 1, dj = -1;
    T[i][j] += Y[i][j];
    for(i+=di, j+=dj; Bound(i, j); i+=di, j+=dj){
        Y[i][j] += Y[i-di][j-dj];
        T[i][j] += Y[i][j];
    }
}

void Solve(){
    cin >> N >> K;
    for(int i=1; i<=N; i++) for(int j=1,t; j<=N; j++) cin >> t, A[i-j+N+N][i+j+N] = t;

    Clear();
    for(int i=1; i<=N; i++) for(int j=1; j<=N; j++) Coloring(i-j+N+N, i+j+N);
    for(int i=0; i<4*N; i++) Sum1(i, 0);
    for(int j=1; j<4*N; j++) Sum1(0, j);
    for(int j=0; j<4*N; j++) Sum2(0, j);
    for(int i=1; i<4*N; i++) Sum2(i, 4*N-1);

    for(int i=0; i<4*N; i++){
        for(int j=0; j<4*N; j++){
            if(i) T[i][j] += T[i-1][j];
            if(j) T[i][j] += T[i][j-1];
            if(i && j) T[i][j] -= T[i-1][j-1];
        }
    }

    ll mx = 0;
    for(int i=0; i<4*N; i++) for(int j=(N+i)&1; j<4*N; j+=2) mx = max(mx, T[i][j]);
    cout << mx << "\n";
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int T; cin >> T;
    for(int tc=1; tc<=T; tc++){
        cout << "Case #" << tc << "\n";
        Solve();
    }
}

4. 패턴 매칭 (Subtask 2 풀이)

??? : 어 이거 XXX 문제인데?

Subtask2와 똑같은 문제가 제가 참가했던 TST에 나왔다는 얘기가 있던데, 저는 본 기억이 없습니다. 아마 문자열 문제라는 것을 보자마자 넘기지 않았나 싶습니다. 1년 반이 지난 지금은 잘 풀었으니 성장했다고 봐도 되겠죠?
제 주변의 몇몇 분들은 TST를 통해 KMP의 아이디어를 생각한 것 같은데, 저는 CEOI 2015 Matching / 2020 서강대 파인애플 피자를 풀었던 기억을 통해서 KMP를 떠올렸습니다.

KMP와 똑같이, 패턴의 Failure Function을 구한 다음 원본 문자열과 패턴을 비교하는 방식으로 진행합니다. 문자열 $A, B$가 동치일 때 $A+a$와 $B+b$가 동치인지 확인하는 로직을 효율적으로 구현해야 합니다. Failure Function부터 구해봅시다.

1
2
 
Pattern : a b a b c d c d
Fail[i] : 0 1 2 3 2 2 3 4

일반적인 KMP에서 Failure Function을 구하는 함수는 다음과 같이 작성할 수 있습니다.

1
2
3
4
5
6
7
8
9
 
vector<int> GetFail(const string &P){
    int n = P.size();
    vector<int> Fail(n);
    for(int i=1, j=0; i<n; i++){
        while(j > 0 && P[i] == P[j]) j = Fail[j-1];
        if(P[i] == P[j]) Fail[i] = ++j;
    }
    return Fail;
}

여기에서 P[i] == P[j]는 P[i-j..i]와 P[0..j]가 동치인지, 즉 P[i-j..i] = P[0..j]인지 확인하는 부분입니다. 이 부분을 Match(i, j)라는 함수로 나타낸 뒤, Match함수를 잘 작성하는 것을 목표로 할 것입니다.

1
2
3
4
 
for(int i=1, j=0; i<n; i++){
    while(j > 0 && !Match(i, j)) j = Fail[j-1];
    if(Match(i, j)) Fail[i] = ++j;
}

만약 P[i-j..i-1]에 이미 P[i]가 등장했다면 P[i]는 매칭되어야 하는 짝이 정해져 있습니다. 마찬가지로, P[0..j-1]에 이미 P[j]가 등장했다면 P[j]는 매칭되어야 하는 짝이 정해져 있습니다. 등장한 적이 없다면 아직 매칭된 적 없는 임의의 문자와 매칭해도 됩니다.

이 정보를 빠르게 처리하는 방법으로, 각 문자 P[x]마다 자신과 똑같은 문자가 등장하는 가장 최근의 위치 prv[x]를 저장합니다. prv[x]를 알고 있다면, prv[i] ≥ i-j, prv[j] != NULL 등을 확인해서 매칭 여부를 상수 시간에 확인할 수 있습니다. 이때, prv 배열을 구하는 것은 $O(\vert P \vert)$ 시간에 할 수 있습니다.

이렇게 작성한 GetFail함수는 다음과 같습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
vector<int> GetFail(const string &P){
    int n = P.size();
    vector<int> Fail(n), prv(n, -1), lst(26, -1);
    for(int i=0; i<n; i++) prv[i] = lst[P[i]-'a'], lst[P[i]-'a'] = i;

    function<bool(int,int)> Match = [&](int i, int j){
        int it = prv[i], jt = prv[j];
        if(it != -1 && i-j <= it && P[j] != P[it-i+j]) return false;
        if(jt != -1 && 0 <= jt && P[i] != P[jt+i-j]) return false;
        return true;
    };

    for(int i=1, j=0; i<n; i++){
        while(j > 0 && !Match(i, j)) j = Fail[j-1];
        if(Match(i, j)) Fail[i] = ++j;
    }
    return Fail;
}

일반적인 KMP에서 실제 매칭을 수행하는 코드는 다음과 같이 작성할 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
 
int KMP(const string &S, const string &P){
    int ret = 0;
    auto Fail = GetFail(P);
    int n = S.size(), m = P.size();
    for(int i=0, j=0; i<n; i++){
        while(j && S[i] != P[j]) j = Fail[j-1];
        if(S[i] == P[j]){
            if(j+1 == m) ret++, j = Fail[j];
            else j++;
        }
    }
    return ret;
}

Failure Function을 구하는 코드와 매우 유사합니다. S[i] == P[j]를 비교하는 것은 S[j-i..i] = P[0..j]를 비교하는 것입니다. Failure Function을 구할 때 했던 것처럼, prv배열을 관리하면 매칭을 잘 수행할 수 있습니다.

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

vector<int> GetFail(const string &P){
    int n = P.size();
    vector<int> Fail(n), prv(n, -1), lst(26, -1);
    for(int i=0; i<n; i++) prv[i] = lst[P[i]-'a'], lst[P[i]-'a'] = i;

    function<bool(int,int)> Match = [&](int i, int j){
        int it = prv[i], jt = prv[j];
        if(it != -1 && i-j <= it && P[j] != P[it-i+j]) return false;
        if(jt != -1 && 0 <= jt && P[i] != P[jt+i-j]) return false;
        return true;
    };

    for(int i=1, j=0; i<n; i++){
        while(j > 0 && !Match(i, j)) j = Fail[j-1];
        if(Match(i, j)) Fail[i] = ++j;
    }
    return Fail;
}

int KMP(const string &S, const string &P){
    static vector<int> SG[26], PG[26];
    for(int i=0; i<26; i++) SG[i].clear(), PG[i].clear();

    int ret = 0;
    auto Fail = GetFail(P);
    int n = S.size(), m = P.size();

    vector<int> s_prv(n, -1), p_prv(m, -1), lst(26, -1);
    for(int i=0; i<n; i++) s_prv[i] = lst[S[i]-'a'], lst[S[i]-'a'] = i;
    fill(lst.begin(), lst.end(), -1);
    for(int i=0; i<m; i++) p_prv[i] = lst[P[i]-'a'], lst[P[i]-'a'] = i;

    function<bool(int,int)> Match = [&](int i, int j){
        int it = s_prv[i], jt = p_prv[j];
        if(it != -1 && i-j <= it && P[j] != P[it-i+j]) return false;
        if(jt != -1 && 0 <= jt && S[i] != S[jt+i-j]) return false;
        return true;
    };

    for(int i=0, j=0; i<n; i++){
        while(j && !Match(i, j)) j = Fail[j-1];
        if(Match(i, j)){
            if(j+1 == m) ret++, j = Fail[j];
            else j++;
        }
    }
    return ret;
}

void Solve(){
    int N, K;
    string S;
    cin >> N >> K >> S;
    ll ans = 0;
    for(int i=1; i<=K; i++){
        string P; cin >> P;
        ll now = KMP(S, P);
        ans += now * i;
    }
    cout << ans << endl;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int T; cin >> T;
    for(int tc=1; tc<=T; tc++){
        cout << "Case #" << tc << "\n";
        Solve();
    }
}

5. Hanoi Tower (33~44점 풀이)

BFS를 돌리면 $N = 18$일 때의 정답(33점)은 쉽게 구할 수 있습니다. BFS 돌려놓고 밥 먹고 오면 $N = 19$일 때의 답(44점)도 얻을 수 있습니다. 근데 codeground에 코드 길이 제한이 있어서 $N=19$는 제출하지 못했습니다.

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
 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using PII = pair<int, int>;
constexpr int N = 19;
constexpr int Size(){
    int ret = 1;
    for(int i=0; i<N; i++) ret *= 3;
    return ret;
}
constexpr int MX = Size(), S = 0, T = MX - 1;

int Pack(const array<int,N> &bit){
    int res = 0;
    for(auto i : bit) res = res * 3 + i;
    return res;
}
array<int,N> Unpack(int val){
    array<int,N> ret;
    for(int i=N-1; i>=0; i--) ret[i] = val % 3, val /= 3;
    return ret;
}

vector<PII> Next(int val){
    vector<int> vec[3];
    vector<PII> ret;
    auto bit = Unpack(val);
    for(int i=0; i<N; i++) vec[bit[i]].push_back(i);

    int cnt = -1;
    for(int from=0; from<3; from++){
        for(int to=0; to<3; to++){
            if(from == to) continue;
            cnt++;
            if(vec[from].empty()) continue;
            int x_idx = vec[from].size() / 2;
            int y_idx = (vec[to].size() + 1) / 2;
            int x = vec[from][x_idx];
            int y = y_idx < vec[to].size() ? vec[to][y_idx] : N+1;
            int small = 0 <= y_idx-1 && y_idx-1 < vec[to].size() ? vec[to][y_idx-1] : -1;
            if(small < x && x < y){
                bit[x] = to;
                ret.emplace_back(Pack(bit), cnt);
                bit[x] = from;
            }
        }
    }
    return ret;
}

int D[MX], P[MX], M[MX];

void BFS(){
    memset(D, -1, sizeof D);
    memset(P, -1, sizeof P);
    queue<int> q;
    q.push(S); D[S] = 0;
    while(q.size()){
        int v = q.front(); q.pop();
        if(v == T) break;
        for(const auto &[i,m] : Next(v)){
            if(D[i] == -1) D[i] = D[v] + 1, P[i] = v, M[i] = m, q.push(i);
        }
    }
}

string Get(){
    BFS();
    string ret;
    for(int i=T; i!=S; i=P[i]) ret += char('A' + M[i]);
    reverse(ret.begin(), ret.end());
    return ret;
}

void Solve(){
    auto res = Get();
    cout << "Case #1\n";
    cout << N << "\n" << res << "\n";
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    Solve();
}