2023 SNUPC Div.1 후기

2023 서울대학교 프로그래밍 경시대회

 

호기롭게 Div.1을 신청하고 나서 꼴등하는 건 아닌가 조금 걱정했지만, 다행히 참가자가 많지 않아서 4솔 14등으로 본상 수상에 성공했다. 25,000원 정도 하는 샤오미 보조배터리를 받았는데 아이폰이라 나는 못 쓴다.

 

 

A. 재민이의 생일

 

제일 쉬운 문제를 열었는데 복잡도가 심상치 않다. $O(500\,000^{\frac{4}{3}})$ 이상을 3초 안에 돌려야 하는데 쉽지 않아 보인다. 일단 multiset을 운용하면서 복잡도에 로그를 붙이는 풀이를 짰는데 TLE를 받았다. 그래, 이런 걸 막고 싶었겠지. 한참 고민하다가 구글에 2d range minimum query를 치니까 $O(NM\log{N}\log{M})$ 전처리에 $O(1)$ 쿼리를 해주는 코드가 있더라. 허겁지겁 복붙해와서 min, max 두 개를 만들고 다 해보는 코드를 짜니까 MLE를 받았다. 굉장히 말린 것 같아서 우선 B를 풀고 다시 넘어왔다. 메모리를 줄이기 위해 rmq는 하나만 만들고, 조금 다른 방식으로 쿼리를 날리는 코드를 짰더니 WA를 받았다. 설마 해서 rmq가 잘 작동하는지를 확인했는데 side effect를 발견했다. 이를 수정했더니 쿼리 개수에 상수가 붙어서 다시 TLE가 났다. 멘탈이 나갈 뻔 했지만 현재 답을 가지고 쿼리의 후보군을 줄이는 커팅을 했더니 2.9초로 아슬아슬하게 AC를 받았다. 소위 말해 뚫었다.

#pragma GCC optimize("O3,Ofast")
#include <bits/stdc++.h>
using namespace std;

// https://www.geeksforgeeks.org/2d-range-minimum-query-in-o1/

int n, m, k, ln, lm;
vector<vector<int>> a;
vector<vector<vector<vector<int>>>> table;

void build_sparse_table()
{
    // Copy the values of the original matrix
    // to the first element of the table
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            table[i][j][0][0] = a[i][j];
        }
    }
 
    // Building the table
    for (int k = 1; k <= ln; k++) {
        for (int i = 0; i + (1 << k) - 1 < n; i++) {
            for (int j = 0; j < m; j++) {
                table[i][j][k][0] = min(
                    table[i][j][k - 1][0],
                    table[i + (1 << (k - 1))][j][k - 1][0]);
            }
        }
    }
 
    for (int k = 1; k <= lm; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j + (1 << k) - 1 < m; j++) {
                table[i][j][0][k] = min(
                    table[i][j][0][k - 1],
                    table[i][j + (1 << (k - 1))][0][k - 1]);
            }
        }
    }
 
    for (int k = 1; k <= ln; k++) {
        for (int l = 1; l <= lm; l++) {
            for (int i = 0; i + (1 << k) - 1 < n; i++) {
                for (int j = 0; j + (1 << l) - 1 < m; j++) {
                    table[i][j][k][l] = min(
                        min(table[i][j][k - 1][l - 1],
                            table[i + (1 << (k - 1))][j]
                                 [k - 1][l - 1]),
                        min(table[i][j + (1 << (l - 1))]
                                 [k - 1][l - 1],
                            table[i + (1 << (k - 1))]
                                 [j + (1 << (l - 1))][k - 1]
                                 [l - 1]));
                }
            }
        }
    }
}
 
// Function to find the maximum value in a submatrix
int rmq(int x1, int y1, int x2, int y2)
{
    // log2(x2-x1+1) gives the power of 2
    // which is just less than or equal to x2-x1+1
    int k = log2(x2 - x1 + 1);
    int l = log2(y2 - y1 + 1);
 
    // Lookup the value from the table which is
    // the maximum among the 4 submatrices
    return min(min(table[x1][y1][k][l],
                   table[x2 - (1 << k) + 1][y1][k][l]),
               min(table[x1][y2 - (1 << l) + 1][k][l],
                   table[x2 - (1 << k) + 1]
                        [y2 - (1 << l) + 1][k][l]));
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m >> k;
    a.resize(n);
    for(int i = 0; i < n; i++) a[i].resize(m);
    ln = log2(n), lm = log2(m);
    table.resize(n);
    for(int i = 0; i < n; i++) table[i].resize(m);
    for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) table[i][j].resize(ln + 1);
    for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) for(int l = 0; l <= ln; l++) table[i][j][l].resize(lm + 1);
    table.shrink_to_fit();
    for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) cin >> a[i][j];
    build_sparse_table();
    int mx = -1, mn = 1e9;
    for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) mn = min(mn, a[i][j]);
    vector<pair<int, pair<int, int>>> v;
    vector<pair<int, int>> p;
    for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) v.push_back({a[i][j], {i, j}});
    sort(v.begin(), v.end());
    for(int i = 0; i < v.size(); i++) p.push_back(v[i].second);
    int st = 0;
    for(int x = 1; x <= k; x++) if(k % x == 0) {
        int y = k / x;
        if(x > n || y > m) continue;
        while(st < p.size() && a[p[st].first][p[st].second] <= mx + mn) st++;
        for(int t = st; t < p.size(); t++) {
            auto &[i, j] = p[t];
            mx = max(mx, a[i][j] - rmq(max(i - x + 1, 0), max(j - y + 1, 0), min(i + x - 1, n - 1), min(j + y - 1, m - 1)));
        }
    }
    cout << mx << '\n';
}

 

 

B. 조교의 기묘한 시험

 

해야 하는 것은 명확하다. set 등으로 각 정수별 인덱스들을 잘 관리하고, 3번 쿼리를 누적합으로 만들어서 오프라인 쿼리를 잘 해주면 된다. A에서 너무 뇌절을 해서 이게 쉽게 느껴졌다.

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 1;

int t[N], x[N], a[N]; ll b[N], s[N];
vector<int> e[N];
set<int> v[2 * N], st;

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int q, k = 0; cin >> q;
    for(int i = 1; i <= q; i++) {
        cin >> t[i] >> x[i];
        if(t[i] == 1) {
            a[++k] = x[i];
            if(!v[x[i]].size()) e[k].push_back(i), st.insert(x[i]);
            if(v[x[i]].size() == 1) st.erase(x[i]), e[*v[x[i]].begin()].push_back(i);
            v[x[i]].insert(k);
        }
        if(t[i] == 2) {
            if(v[a[x[i]]].size() == 1) e[x[i]].push_back(i), st.erase(a[x[i]]);
            v[a[x[i]]].erase(x[i]);
            if(v[a[x[i]]].size() == 1) e[*v[a[x[i]]].begin()].push_back(i), st.insert(a[x[i]]);
        }
        if(t[i] == 3) {
            s[i] = 1;
            if(st.size()) b[*v[*prev(st.end())].begin()] += x[i];
        }
    }
    for(int i = 1; i <= q; i++) s[i] += s[i - 1];
    for(int i = 1; i <= k; i++) {
        if(e[i].size() & 1) e[i].push_back(q);
        for(int j = 0; j < e[i].size(); j += 2) b[i] += s[e[i][j + 1]] - s[e[i][j]];
    }
    for(int i = 1; i <= k; i++) cout << b[i] << '\n';
}

 

 

E. 사과 바나나 나무

두 컴포넌트를 만드는 것은 간선 하나를 기준으로 자른다고 생각할 수 있다. 그리고 이는 서브트리 하나와 나머지로 구분하는 것과 같다. 이동을 구체적으로 어떻게 하는지는 모르겠지만, 대충 서브트리의 루트로 모아주는 횟수와 같은 횟수로 잘 될 것이라 추측할 수 있다. 이제 dfs를 돌면서 각 노드마다 답을 구하기 위해 필요한 값들을 전처리하고, 다시 dfs를 돌면서 값들을 잘 관리하면서 계산하면 된다. 노드에서 노드로 이동할 때 값들이 어떻게 바뀌는지 잘 생각해야 해서 두 번째 dfs가 까다롭다.

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 1;

int t[N], a[N], b[N], sz[N];
ll aa[N], bb[N], mn = 1e18;
vector<int> ad[N];

void dfs(int u, int p) {
    (t[u] ? a[u] : b[u]) = 1; sz[u] = 1;
    for(auto &v : ad[u]) if(v ^ p) {
        dfs(v, u);
        a[u] += a[v], b[u] += b[v], sz[u] += sz[v];
        aa[u] += aa[v] + a[v], bb[u] += bb[v] + b[v];
    }
}

void _dfs(int u, int p, ll at, ll bt) {
    if(sz[u] == a[1]) mn = min(mn, at - aa[u] + bb[u]);
    if(sz[u] == b[1]) mn = min(mn, aa[u] + bt - bb[u]);
    for(auto &v : ad[u]) if(v ^ p) {
        _dfs(v, u, at + a[1] - 2 * a[v], bt + b[1] - 2 * b[v]);
    }
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n; cin >> n;
    string s; cin >> s;
    for(int i = 0; i < n; i++) t[i + 1] = s[i] == 'A';
    for(int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        ad[u].push_back(v), ad[v].push_back(u);
    }
    dfs(1, 0); _dfs(1, 0, aa[1], bb[1]);
    cout << (mn < 1e18 ? mn : -1) << '\n';
}

 

 

H. SNUPC 게임

 

열심히 규칙을 찾아보자. 일단 S, N, U가 0일 때의 승패는 P의 홀짝성에 의존한다. 비슷하게 S, N이 0이고 U가 1일 때 P가 홀수라면 U를 P로 보냄으로써 기하가 이길 수 있다. 나머지 경우는 기하나 정수가 질 것 같으면 U에서 S로 보내는 식으로 게임의 선후를 바꿀 수 있고, 그래서 게임이 끝나지 않는다.

 

#include <bits/stdc++.h>
using namespace std;

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int tc; cin >> tc;
    while(tc--) {
        int a, b, c, d, e; cin >> a >> b >> c >> d >> e;
        if(a + b + c > 1) cout << "hanbyeol\n";
        else if(c == 1 && d % 2) cout << "geometry\n";
        else if(a + b + c == 1) cout << "hanbyeol\n";
        else if(d % 2) cout << "geometry\n";
        else cout << "number_theory\n";
    }
}

 

 

A에서 억까 당하지 않았다면 하는 아쉬움이 많이 남는다. 그래도 다른 문제들을 거의 실수 없이 풀었다는 점에서는 긍정적이다.