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

작성일 | In

서론

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

점수는 다음과 같습니다.

번호 1차 예선 점수 2차 예선 점수
1 개미 100/100 수열연산 100/100
2 K 등분 140/140 반 협동게임 150/150
3 직교 다각형 140/140 ABC 200/200
4 지우개 0/190 직사각형 250/250
5 독립 135/230 황금 카드 73/300
총점   515/800   773/1000

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

1차 예선

1차 예선답게 쉬운 문제들이 출제되었습니다. 첫째 날에는 1, 2번과 5번의 부분 문제만 풀었는데, 혹시 떨어질까 불안해서 다음날 3번을 추가로 풀었습니다.
5번을 읽자마자 BOJ 7907 Bytean Road Race가 생각나서 싱글벙글하며 코드를 긁어서 제출했는데 만점이 안 나와서 슬펐습니다. 하지만 더 생각하기 귀찮아서 풀지 않았습니다. 4번은 풀이를 찾았지만 구현이 귀찮아 보여서 안 풀었습니다.

1. 개미

정렬한 다음, 원래 $i$번째에 있던 개미와 정렬된 배열에서 $i$번째에 있는 개미의 차이를 모두 더하면 됩니다.

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;
using ll = long long;

int N, P[303030];
pair<int,int> A[303030];

void Solve(){
    cin >> N;
    for(int i=1; i<=N; i++) cin >> P[i];
    for(int i=1; i<=N; i++) cin >> A[i].first, A[i].second = i;
    sort(A+1, A+N+1);

    ll R = 0;
    for(int i=1; i<=N; i++) R += abs(P[i] - P[A[i].second]);
    cout << R << "\n";
}

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

2. K 등분

원소의 합이 0인 경우와 0이 아닌 경우로 나눠서 해결할 수 있습니다.

원소의 합이 0인 경우는 Prefix Sum이 0이 되는 위치 중에서 K개를 선택하면 되므로 이항 계수를 이용해 쉽게 답을 구할 수 있습니다.

원소의 합을 $S(\neq 0)$라고 합시다. 각 조각의 합이 모두 같도록 $K$개로 나눠야 하므로, 각 조각의 합은 $S/K$가 되어야 합니다. 따라서 $S\not\equiv 0 \pmod K$이면 답은 0이고, $S \equiv 0\pmod K$이면 DP를 이용해 답을 계산할 수 있습니다.

각 조각의 합을 $s=S/K$라고 정의합시다. 첫 번째 조각까지의 누적합은 $s$, 두 번째 조각까지의 누적합은 $2s$, $k$번째 조각까지의 누적합은 $ks$가 되어야 합니다.
$D(k,i) := $ $k$번째 조각이 $i$번째 인덱스에서 끝나는 경우의 수라고 정의합시다. 모든 $k$에 대해, 실제로 계산해야 하는 인덱스의 총 개수는 최대 $N$개입니다. $D(k,\ast)$의 누적합을 구해 놓으면, 투 포인터 기법을 이용해 정답을 $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
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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll MOD = 1e9+7;
inline void Add(int &a, int b){ a += b; if(a >= MOD) a -= MOD; }

ll Pow(ll a, ll b){
    ll res = 1;
    for(; b; b >>= 1, a = a * a % MOD) if(b & 1) res = res * a % MOD;
    return res;
}

ll N, K, A[505050], S[505050], Fac[505050], Inv[505050];
vector<int> V[505050], D[505050];
ll Comb(int n, int r){ return r <= n ? Fac[n] * Inv[r] % MOD * Inv[n-r] % MOD : 0; }

void Solve(){
    cin >> N >> K;
    for(int i=0; i<=K; i++) V[i].clear(), D[i].clear();
    for(int i=1; i<=N; i++) cin >> A[i], S[i] = S[i-1] + A[i];
    if(S[N] == 0){
        int cnt = 0;
        for(int i=1; i<N; i++) cnt += S[i] == 0;
        cout << Comb(cnt, K-1) << "\n";
        return;
    }
    if(S[N] % K != 0){ cout << 0 << "\n"; return; }

    ll step = S[N] / K;
    for(int i=1; i<=N; i++){
        if(S[i] % step != 0) continue;
        ll q = S[i] / step;
        if(1 <= q && q <= K) V[q].push_back(i);
    }

    V[0].push_back(0); D[0].push_back(1);
    for(int i=1; i<=K; i++){
        if(V[i].empty()){ cout << 0 << "\n"; return; }
        for(int j=0, k=0; j<V[i].size(); j++){
            while(k < V[i-1].size() && V[i-1][k] < V[i][j]) k++;
            D[i].push_back(k ? D[i-1][k-1] : 0);
        }
        for(int j=1; j<D[i].size(); j++) Add(D[i][j], D[i][j-1]);
    }

    int res = D[K].back();
    if(D[K].size() > 1) res -= D[K][D[K].size()-2];
    if(res < 0) res += MOD;

    cout << res << "\n";
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    const int SZ = 500'000;
    Fac[0] = 1; for(int i=1; i<=SZ; i++) Fac[i] = Fac[i-1] * i % MOD;
    Inv[SZ] = Pow(Fac[SZ], MOD-2); for(int i=SZ-1; i>=0; i--) Inv[i] = Inv[i+1] * (i+1) % MOD;
    int TC; cin >> TC;
    for(int tc=1; tc<=TC; tc++) cout << "Case #" << tc << "\n", Solve();
}

3. 직교 다각형

문제를 처음 보면 어려워 보이지만, 예제를 직접 그림으로 그려보면 풀이를 쉽게 찾을 수 있습니다.

에러 점이 있는 행과 열은 홀수 개의 점을 갖고 있고, 그렇지 않은 행과 열은 짝수 개의 점을 갖고 있습니다. 그러므로 에러 점을 쉽게 검출할 수 있고, 남은 점들은 차례대로 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
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
using Point = pair<int, int>;

void Solve(){
    int N; cin >> N;
    vector<pair<int,int>> X(N), Y(N);
    for(int i=0; i<N; i++){
        int x, y; cin >> x >> y;
        X[i] = Y[i] = {x, y};
    }
    sort(X.begin(), X.end(), [](const Point &p1, const Point &p2) -> bool { return make_pair(p1.x, p1.y) < make_pair(p2.x, p2.y); });
    sort(Y.begin(), Y.end(), [](const Point &p1, const Point &p2) -> bool { return make_pair(p1.y, p1.x) < make_pair(p2.y, p2.x); });

    int xx = -1, yy = -1;
    for(int i=0, j=0; i<N; i=j){
        while(j < X.size() && X[i].x == X[j].x) j++;
        if((j - i) % 2 == 1) xx = X[i].x;
    }
    for(int i=0, j=0; i<N; i=j){
        while(j < Y.size() && Y[i].y == Y[j].y) j++;
        if((j - i) % 2 == 1) yy = Y[i].y;
    }

    if(xx != -1 && yy != -1){
        X.erase(find(X.begin(), X.end(), make_pair(xx, yy)));
        Y.erase(find(Y.begin(), Y.end(), make_pair(xx, yy)));
    }

    long long res = 0;
    for(int i=1; i<X.size(); i+=2) res += abs(X[i-1].y - X[i].y);
    for(int i=1; i<Y.size(); i+=2) res += abs(Y[i-1].x - Y[i].x);
    cout << res << "\n";
}

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

4. 지우개

연속한 a 그룹과 b 그룹을 묶은 다음, 양쪽 끝을 제외한 나머지 부분을 KMP로 매칭하면 되는 걸로 기억합니다.

나중에 codeground에 문제가 올라오면 풀고 수정하겠습니다.

5. 독립

Subtask 2(135점)는 BOJ 7907 Bytean Road Race(풀이)를 풀고 inversion counting을 하면 $O(N^2 \log N^2)$에 해결할 수 있습니다.

Subtask 3(230점)은 $O(N^2)$에 해결해야 합니다. 이 문제도 나중에 codeground에 문제가 올라오면 풀고 추가하도록 하겠습니다.

2차 예선

1, 2번은 쉬운 문제라서 빨리 풀었습니다. 각각 9시 10분, 9시 20분에 전체 참가자 중 13번째, 5번째로 풀었습니다.
3번은 풀이는 뻔한데 생각 정리가 잘 안 되길래 밥을 먹으면서 고민했습니다. 배열 크기를 너무 적게 잡아서 3번 틀리고 11시 29분에 16번째로 풀었습니다.
4번은 계절학교에서 비슷한 느낌의 문제를 풀었던 기억이 있어서 어렵지 않게 풀었습니다. 14시 01분에 11번째로 풀었습니다. 사소한 실수가 몇 가지 있어서 디버깅하는데 시간이 오래 걸렸습니다.
5번은 못 푸는 문제같아서 Subtask 1만 풀고 놀았습니다.

작년보다 쉽게 느껴졌는데 만점자 수 보면 아닌 것 같기도 하고… 개인적으로 올해 3번과 4번이 작년 3번(산탄총)보다 만점자 수가 적은 게 잘 이해가 안 갑니다.

1. 수열 연산

update(1, N)을 $\max(0, K-\min A)$번 호출하면 최소 횟수는 쉽게 달성할 수 있습니다. 최소 비용을 만드는 방법을 생각해 봅시다.

$\max(0,k-\min A)$번을 유지하면서 비용을 줄이기 위해서는 update(1, N)에 대응되는 작업을 한 번의 쿼리로 수행해야 합니다. 즉, $K$ 미만인 수를 전부 Update로 처리해야 합니다. 따라서 투 포인터 느낌으로 양끝에서 $K$ 이상인 원소들을 떼어내면서 update를 호출하면 문제를 해결할 수 있습니다.

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

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

void Solve(){
    cin >> N >> K; R = 0;
    for(int i=1; i<=N; i++) cin >> A[i];
    for(int i=1; i<=N; i++) B[i] = max(0LL, K - A[i]);
    if(*max_element(B+1, B+N+1) == 0){
        cout << 0 << " " << 0 << "\n";
        return;
    }

    ll l = 1, r = N, add = 0;
    while(l <= r && B[l] - add <= 0) l += 1;
    while(l <= r && B[r] - add <= 0) r -= 1;
    while(l <= r){
        ll now = min(B[l] - add, B[r] - add);
        add += now; R += (r - l + 1) * now;
        while(l <= r && B[l] - add <= 0) l += 1;
        while(l <= r && B[r] - add <= 0) r -= 1;
    }
    cout << add << " " << R << "\n";
}

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

2. 반 협동게임

멀리 있는 학생부터 매칭하면 됩니다. 매칭의 비용은 Fenwick Tree 등을 이용해 $O(\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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int N, A[303030], T[303030];
vector<int> G[303030];
void Add(int x){ for(x+=3; x<303030; x+=x&-x) T[x]++; }
int Get(int x){ int ret = 0; for(x+=3; x; x-=x&-x) ret += T[x]; return ret; }

void Solve(){
    cin >> N;
    for(int i=1; i<=N; i++) cin >> A[i], G[A[i]].push_back(i);

    vector<pair<int,int>> V;
    for(int i=1; i<=N; i++){
        for(int j=0; j*2<G[i].size(); j++) V.emplace_back(G[i][j], G[i][G[i].size()-j-1]);
    }
    sort(V.begin(), V.end(), [](auto a, auto b){ return a.second - a.first > b.second - b.first; });

    ll R = 0;
    for(auto [s,e] : V){
        R += (e - Get(e-1)) - (s - Get(s-1));
        Add(s); Add(e);
    }
    cout << R << "\n";

    memset(T, 0, sizeof T);
    for(int i=1; i<=N; i++) G[i].clear();
}

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

3. ABC

$K = \infty$인 경우와 $K \neq \infty$인 경우를 나눠서 해결합니다. $K = \infty$인 경우를 먼저 보겠습니다.

만약 어떤 SCC에 A, B, C 간선이 모두 있으면 정답은 $\infty$입니다. 그렇지 않은 경우, 각각의 SCC를 하나의 정점으로 압축한 DAG를 생각해 봅시다.
DAG의 각 정점을 3개의 정점으로 분할합니다. 정점 $(v, e)$는 마지막으로 $e$ 글자를 붙여서 $v$에 도달했다는 것을 의미합니다. 만약 SCC 안에 간선이 있다면 $(v,A) \rightarrow (v,B)$와 같은 간선을 적절히 추가하고, 글자를 붙이지 않는 경우는 $(v,e) \rightarrow (u,e)$ 형태의 가중치가 0인 간선을 추가하면 됩니다.
이렇게 만든 그래프는 DAG이므로 선형 시간에 최장 거리를 구할 수 있습니다.

$K \neq \infty$인 경우는 조금 더 복잡합니다.
그래프의 각 정점을 $3K$개로 분할합니다. 정점 $(v,e,s)$는 마지막으로 $e$ 글자를 붙여서 $v$에 도달했고, 지금까지 글자를 $s$번 붙이지 않았다는 것을 의미합니다. 만약 이렇게 해서 만든 그래프에 A, B, C 간선이 모두 들어간 SCC가 존재하면 정답은 $\infty$입니다.
그렇지 않은 경우, 즉 각 SCC에 최대 2가지 종류의 간선만 존재하는 경우를 생각해 봅시다. 잘 생각해 보면 self loop가 존재하지 않기 때문에 그래프에 사이클이 존재하지 않는다는 것을 알 수 있습니다. DAG이므로 선형 시간에 최장 거리를 구하면 됩니다.

$K \neq \infty$이면 $K \leq 2$이므로 $K$를 상수라고 생각하면, 두 가지 경우 모두 $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
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
#include <bits/stdc++.h>
using namespace std;

int N, M, K, C[909090], D[909090], In[909090];
vector<tuple<int,int,int>> E;
vector<int> G[909090], G2[909090], S[909090], V;
vector<pair<int,int>> T[303030];

inline int ID(int v, int ch, int skip){ return (v - 1) * 9 + ch * 3 + skip; }
inline void AddEdge(int s, int e){ G[s].push_back(e); G2[e].push_back(s); In[e] += 1; }
void DFS1(int v){
    C[v] = -1;
    for(auto i : G[v]) if(!C[i]) DFS1(i);
    V.push_back(v);
}
void DFS2(int v, int c){
    C[v] = c; S[c].push_back(v);
    for(auto i : G2[v]) if(C[i] == -1) DFS2(i, c);
}
int GetSCC(int lo, int hi){
    int pv = 0; V.clear();
    for(int i=lo; i<=hi; i++) if(!C[i]) DFS1(i);
    reverse(V.begin(), V.end());
    for(auto i : V) if(C[i] == -1) DFS2(i, ++pv);
    return pv;
}

void Clear(int lo, int hi, int sz){
    memset(C+lo, 0, sizeof(C[0])*(hi-lo+1));
    memset(D+lo, 0, sizeof(D[0])*(hi-lo+1));
    memset(In+lo, 0, sizeof(In[0])*(hi-lo+1));
    for(int i=lo; i<=hi; i++) G[i].clear(), G2[i].clear();
    for(int i=1; i<=sz; i++) S[i].clear();
}

void SolveFinite(){
    for(const auto &[s,e,c] : E){
        for(int i=0; i<3; i++) AddEdge(ID(s,(c+2)%3,i), ID(e,c,i));
        for(int i=0; i<3; i++) for(int j=0; j<2; j++) AddEdge(ID(s,i,j), ID(e,i,j+1));
    }
    int lo = ID(1,0,0), hi = ID(N,2,2), sz = GetSCC(lo, hi), res = 0;
    for(int i=1; i<=sz; i++) if(S[i].size() >= 3) { cout << -1 << endl; Clear(lo, hi, sz); return; }

    queue<int> Q;
    for(int i=lo; i<=hi; i++) if(In[i] == 0) Q.push(i);
    while(!Q.empty()){
        int v = Q.front(); Q.pop();
        if(v % 3 <= K) res = max(res, D[v] - v % 3);
        for(auto i : G[v]){
            D[i] = max(D[i], D[v] + 1);
            if(!--In[i]) Q.push(i);
        }
    }
    cout << res << endl;
    Clear(lo, hi, sz);
}

void SolveInfinite(){
    for(const auto &[s,e,c] : E) AddEdge(s, e);
    int lo = 1, hi = N, sz = GetSCC(1, N), res = 0;

    vector<int> deg(sz*3+10, 0);
    auto id = [&](int v, int c){ return (v - 1) * 3 + c; };
    auto add_edge = [&](int s, int e, int w){ T[s].emplace_back(e, w); deg[e] += 1; };

    for(const auto &[s,e,c] : E){
        if(C[s] == C[e]) add_edge(id(C[s],(c+2)%3), id(C[s],c), 1);
        else{
            for(int i=0; i<3; i++) add_edge(id(C[s],i), id(C[e],i), 0);
            add_edge(id(C[s],(c+2)%3), id(C[e],c), 1);
        }
    }

    queue<int> Q;
    for(int i=id(1,0); i<=id(sz,2); i++) if(!deg[i]) Q.push(i);
    while(!Q.empty()){
        int v = Q.front(); Q.pop();
        res = max(res, D[v]);
        for(auto [i,w] : T[v]){
            D[i] = max(D[i], D[v] + w);
            if(!--deg[i]) Q.push(i);
        }
    }
    if(*max_element(deg.begin(), deg.end()) > 0) cout << -1 << endl;
    else cout << res << endl;

    Clear(lo, hi, sz);
    lo = id(1, 0); hi = id(sz, 2);
    memset(D+lo, 0, sizeof(D[0])*(hi-lo+1));
    for(int i=lo; i<=hi; i++) T[i].clear();
}

void Solve(){
    cin >> N >> M >> K; E.reserve(M);
    for(int i=0; i<M; i++){
        int s, e; char c; cin >> s >> e >> c;
        E.emplace_back(s, e, c-'A');
    }
    if(K != -1) SolveFinite();
    else SolveInfinite();
    E.clear();
}

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

4. 직사각형

보통 이런 문제는 $r_1, r_2$를 $O(N^2)$에 고정하고, 적당한 방법을 통해 $c_1, c_2$를 잘 계산하는 방식으로 해결할 수 있습니다. 하지만 이 문제는 이런 방식으로 접근했을 때 $O(N^4)$ 미만으로 푸는 방법이 안 보여서 다른 방식으로 접근했습니다.

직사각형에 포함되는 수의 최솟값 $i$를 고정합시다. $i$만 포함된 직사각형에서 시작해서, 수를 하나씩 추가하면서 직사각형을 확장하는 방식으로 진행할 것입니다.
직사각형의 크기는 $1\times 1$부터 시작해서 최대 $N\times N$까지 확장되므로, 고정된 $i$에 대해 직사각형의 확장은 $O(N)$번 발생합니다. 따라서 전체 확장 횟수는 $O(N^3)$으로 문제를 해결하기에 충분합니다. 직사각형이 확장되는 타이밍과 직사각형의 최솟값/최댓값의 변화를 빠르게 계산하는 방법을 알아봅시다.

만약 현재 직사각형이 꽉찬 직사각형인 경우 (최댓값 + 1)을 추가하고, 그렇지 않은 경우에는 마지막으로 추가한 수부터 현재 직사각형 영역의 최댓값까지의 수를 전부 추가합니다.
한 번에 수를 여러 개 추가할 때 직사각형 크기의 변화는, 추가하는 수가 연속적이라는 것을 이용해 RMQ를 날리면 됩니다. Sparse Table을 이용해 $O(N^2 \log N^2)$ 전처리를 하면 $O(1)$에 RMQ를 할 수 있습니다.
최솟값과 최댓값의 변화를 관리하는 것은, 매번 한 줄씩 확장된다는 점을 이용해 각 행과 열에 RMQ를 날리면 됩니다. Sparse Table을 $2N$개 관리하면 RMQ를 $O(1)$에 처리할 수 있습니다.

직사각형을 한 번 확장하는데 $O(1)$이 걸리므로 전체 문제를 $O(N^3)$에 해결할 수 있습니다.

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

// range minimum query
template<typename T, class O> struct SparseTable {
    vector<vector<T>> a;
    void resize(int sz){
        int lg = __lg(sz);
        a = vector<vector<T>>(lg+1, vector<int>(sz));
    }
    void set(int x, T v){ a[0][x] = v; }
    void build(){
        for(int i=1; i<a.size(); i++) for(int j=0; j<a[i].size(); j++) if(j+(1<<(i-1)) < a[i].size()) a[i][j] = min(a[i-1][j], a[i-1][j+(1<<(i-1))], O());
    }
    T get(int s, int e){
        int k = __lg(e-s+1);
        return min(a[k][s], a[k][e-(1<<k)+1], O());
    }
};

int N, S, A[256][256], R[1<<16], C[1<<16];
SparseTable<int, less<>> MinR[257], MinC[257];
SparseTable<int, greater<>> MaxR[257], MaxC[257];

void Solve(){
    cin >> N; S = N * N;
    for(int i=0; i<N; i++) for(int j=0; j<N; j++) cin >> A[i][j], A[i][j] -= 1;
    for(int i=0; i<N; i++) for(int j=0; j<N; j++) R[A[i][j]] = i, C[A[i][j]] = j;

    MinR[N].resize(S); MaxR[N].resize(S); MinC[N].resize(S); MaxC[N].resize(S);
    for(int i=0; i<S; i++) MinR[N].set(i, R[i]), MaxR[N].set(i, R[i]), MinC[N].set(i, C[i]), MaxC[N].set(i, C[i]);

    for(int i=0; i<N; i++) MinR[i].resize(N), MaxR[i].resize(N), MinC[i].resize(N), MaxC[i].resize(N);
    for(int i=0; i<N; i++) for(int j=0; j<N; j++) MinR[i].set(j, A[i][j]), MinC[j].set(i, A[i][j]);
    for(int i=0; i<N; i++) for(int j=0; j<N; j++) MaxR[i].set(j, A[i][j]), MaxC[j].set(i, A[i][j]);
    for(int i=0; i<=N; i++) MinR[i].build(), MaxR[i].build(), MinC[i].build(), MaxC[i].build();

    int res = 0;
    for(int i=0; i<S; i++){
        int r1 = R[i], r2 = R[i], c1 = C[i], c2 = C[i], mn = i, mx = i, lst = i;
        while(true){
            int sz = (r2 - r1 + 1) * (c2 - c1 + 1);
            if(mn < i) break;
            if(lst == mx && sz == mx - mn + 1) res += 1;
            if(lst + 1 == S) break;
            lst = max(lst+1, mx);
            int r_mn = MinR[N].get(mn, lst), r_mx = MaxR[N].get(mn, lst);
            int c_mn = MinC[N].get(mn, lst), c_mx = MaxC[N].get(mn, lst);
            while(r_mn < r1) r1--, mn = min(mn, MinR[r1].get(c1, c2)), mx = max(mx, MaxR[r1].get(c1, c2));
            while(r_mx > r2) r2++, mn = min(mn, MinR[r2].get(c1, c2)), mx = max(mx, MaxR[r2].get(c1, c2));
            while(c_mn < c1) c1--, mn = min(mn, MinC[c1].get(r1, r2)), mx = max(mx, MaxC[c1].get(r1, r2));
            while(c_mx > c2) c2++, mn = min(mn, MinC[c2].get(r1, r2)), mx = max(mx, MaxC[c2].get(r1, r2));
        }
    }
    cout << res << endl;
}

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

5. 황금 카드

Subtask 1(73점)은 Bit DP를 이용해 $O(KN2^N)$에 해결할 수 있습니다. Subtask 2부터는 모릅니다.
아래 코드는 Subtask 1 코드입니다.

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;
using ll = long long;
constexpr ll MOD = 998244353;

ll Pow(ll a, ll b){
    ll res = 1;
    for(; b; b >>= 1, a = a * a % MOD) if(b & 1) res = res * a % MOD;
    return res;
}

ll N, K, P, A[50505], D[55][1<<10], R[55];

void Solve(){
    cin >> N >> K; P = 0;
    for(int i=0; i<N; i++) cin >> A[i], P += A[i];
    if(N > 10 || K > 50){ cout << 0 << endl; return; }

    memset(D, 0, sizeof D); D[0][0] = 1;
    for(int i=0; i<K; i++){
        for(int j=0; j<(1<<N); j++){
            for(int k=0; k<N; k++){
                D[i+1][j|(1<<k)] += D[i][j] * A[k] % MOD * Pow(P, MOD-2) % MOD;
            }
        }
    }

    memset(R, 0, sizeof R);
    for(int i=1; i<=K; i++){
        for(int j=0; j<(1<<N); j++){
            R[i] = (R[i] + __builtin_popcount(j) * D[i][j]) % MOD;
        }
        R[i] = R[i] * Pow(P, i) % MOD;
    }

    ll res = 0;
    for(int i=1; i<=K; i++) res ^= R[i];
    cout << res << endl;
}

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