SCPC 2024 Round 1

7월 5일 15시 ~ 7월 6일 15시 동안 진행되었다.
 
대학생이 된 후 처음으로 치르는 메이저 대회였다.
현대모비스는 PS 폼이 별로인 시점에 2년연속티켓페널티를 물기 싫음 + 마침 더 재밌는 일정 + 기출 안 풂 (대회를 대비하는 과정에서 해당 대회에 대한 애정이 생기는 편)
의 사유로, 예선만 대충 치렀다. 팀원들은 대회 가서 괴물같은 모습들을 뽐내고 온 듯 하다... ㅊㅊ
 

Screencast를 youtube에 올렸다.
https://youtu.be/VuXg1AEQsXo
 
문제들에 대한 감상은, 내 기준으로 딱 1 라운드 용으로 재밌게 몸풀기 할 수 있는 난이도였다고 생각한다.
무엇보다 지문이 두세줄로 끝나는 것이 너무 좋았다. GOAT
 
간략하게 풀이를 적자면,

1. A보다 B가 좋아: A와 A 사이에는 최소 2개의 B가 들어가야 한다. 이를 달성시키면 된다.
2. 배달: 네 점의 둘레는 오직 양 끝 점에 의해서만 결정된다. 즉, 가운데 두 개를 버리면 된다는 의미인데, 이걸 전체로 놓고 보면 가운데에 위치한 N/2개의 점들만 무시하면 된다는 말이 된다.
3. 보안망 점검: 해야 할 것은 명확하고, 가장 깔끔하게 구현하는 것이 중요하다면 중요. 원을 가로지르는 간선 위의 두 정점의 차수가 3이라는 성질을 이용해 간선을 식별한다. 그리고 그 간선을 제거하면 순수한 사이클만이 남게 되는데, 여기서 그 특정 두 정점의 거리를 찾으면 문제가 해결된다. 한쪽 방향의 거리가 있고, 반대쪽 방향의 거리를 갖고서 각 부분에서 두 간선을 뽑는 경우의 수를 구하면 된다.
4. 딱 맞게: max를 갖는 쌍만 주목하면 된다는 점에 착안한다. 우선 배열 두 개를 모두 정렬하자. 여기서 max 쌍을 하나 특정하고 나면, 나머지 쌍들은 L 이하로 잘 구성만 된다면 생각할 필요가 없다. 즉, 모든 쌍 $(i,j)$에 대해 $\mathbb{swap}(a_i,b_j)$ 딱 한 번만 시행한 상황을 전부 확인하는 것이 답을 구하기에 충분하다. 이때, 구간 $(i,j)$는 한 칸씩 밀려나간 형태가 된다. 이건 단순한 형태이므로 누적합으로 처리할 수 있게 된다. 그럼 $(i,j)$ 쌍의 후보만 줄이면 되는데, 이는 모든 $i$에 대해 적절한 $j$를 이진탐색으로 찾음으로서 해결할 수 있다.
5. 스퀘어: 일단 문제가 풍기는 강한 mo's 알고리즘의 냄새를 맡을 수 있다. 못 맡았다면 mo's를 공부해보자. 우선 $K$를 $\sqrt N$을 기준으로 나누어 생각할 수 있는데, $K>\sqrt N$일 경우 '스퀘어'를 최대 한 번 시행할 수 있다. 따라서, $a_i>\sqrt N$인 원소들 간의 교류는 전혀 없게 된다. 그렇다면 $x\le \sqrt N$들을 우선 오름차순으로 확인하며 해야할 처리를 잘 해주자. 동시에 $x^2>\sqrt N$들에 영향을 미치는 작업을 잘 진행하자. 동시에 $a_i>\sqrt N$인 원소들은 저 과정과 구분하여 단순히 개수만 잘 세어주자. 이렇게 하면 풀 수 있다. 말이 복잡하지만 코드를 보면 이해가 쉬울 것이다.

 
A보다 B가 좋아 코드

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int,int>;

const int N = 3e5+3;
int n;
char s[N];

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int testCase; cin >> testCase; for (int tc = 1; tc <= testCase; ++tc)
    {
        cin >> n >> &s[1];
        
        int p = -10, ans = 0;
        
        for (int i=1; i<=n; ++i) {
            if (s[i] == 'A') {
                if (i-p <= 2) {
                    ans += 3-(i-p);
                }
                p = i;
            }
        }
        
        cout << "Case #" << tc << '\n';
        cout << ans << '\n';
    }
}

 
배달 코드

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int,int>;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int testCase; cin >> testCase; for (int tc = 1; tc <= testCase; ++tc)
    {
        int n; cin >> n;
        vector<ll> a(n); for (auto &e : a) cin >> e;
        
        sort(begin(a),end(a));
        
        ll ans = 0;
        for (int i=0; i<n/4; ++i) {
            ans -= a[i];
            ans += a[n-1-i];
        }
        
        cout << "Case #" << tc << '\n';
        cout << ans*2 << '\n';
    }
}

 
보안망 점검 코드

#include <bits/stdc++.h>
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
using namespace std;
using ll = long long;
using ii = pair<int,int>;

const int N = 3e5+3;
int n;
vector<int> adj[N];

int dfs(int obj, int step, int s, int e = 0) {
    if (obj == s) {
        return step;
    }
    for (auto u : adj[s]) {
        if (u != e) {
            int tmp = dfs(obj, step+1, u, s);
            if (tmp) return tmp;
        }
    }
    return 0;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int testCase; cin >> testCase; for (int tc = 1; tc <= testCase; ++tc)
    {
        cin >> n;
        for (int i=0; i<=n; ++i) {
            int u, v;
            cin >> u >> v;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        
        int x=-1, y=-1;
        
        for (int i=1; i<=n; ++i) {
            if (size(adj[i]) == 3) { x = i; break; }
        }
        for (int i=n; i>=1; --i) {
            if (size(adj[i]) == 3) { y = i; break; }
        }
        
        adj[x].erase(find(begin(adj[x]),end(adj[x]), y));
        adj[y].erase(find(begin(adj[y]),end(adj[x]), x));
        
        int c = dfs(y,0,x);
        
        ll ans = 1ll*c*(c-1)/2;
        c = max(n-c,0);
        ans += 1ll*c*(c-1)/2;
        
        cout << "Case #" << tc << '\n';
        cout << ans << '\n';
        
        for (int i=1; i<=n; ++i) adj[i].clear();
    }
}

 
딱 맞게 코드

#include <bits/stdc++.h>
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
using namespace std;
using ll = long long;
using ii = pair<int,int>;

const int N = 1e5+3;
int n, l;
int a[N], b[N];
int du[N]; // [/]
int ud[N]; // [\]
int pfx[N]; // [|]
int sfx[N];

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int testCase; cin >> testCase; for (int tc = 1; tc <= testCase; ++tc)
    {
        cin >> n >> l;
        for (int i=1; i<=n; ++i) cin >> a[i];
        for (int i=1; i<=n; ++i) cin >> b[i];
        
        sort(a+1,a+n+1), sort(b+1,b+n+1);
        
        for (int i=2; i<=n; ++i) {
            du[i] = du[i-1] + (abs(a[i]-b[i-1]) > l);
            ud[i] = ud[i-1] + (abs(b[i]-a[i-1]) > l);
        }
        for (int i=1; i<=n; ++i) pfx[i] = pfx[i-1] + (abs(a[i]-b[i]) > l);
        sfx[n+1] = 0;
        for (int i=n; i>=1; --i) sfx[i] = sfx[i+1] + (abs(a[i]-b[i]) > l);
        
        int ans = -1;
        for (int i=1; i<=n; ++i) {
            int j;
            j = lower_bound(b+1,b+n+1,a[i]+l+1)-b-1;
            
            // a[i]와 b[j]를 swap했을 때! [\] -> 그 사이는 /////
            if (1<=j&&j<=n) {
                if (i <= j && du[j]-du[i] == 0 && pfx[i-1] == 0 && sfx[j+1] == 0) {
                    ans = max(ans, b[j]-a[i]);
                }
                if (i >= j && ud[i]-ud[j] == 0 && pfx[j-1] == 0 && sfx[i+1] == 0) {
                    ans = max(ans, b[j]-a[i]);
                }
            }
            
            j = lower_bound(b+1,b+i+1,a[i]-l)-b;
            
            if (1<=j&&j<=n) {
                if (i <= j && du[j]-du[i] == 0 && pfx[i-1] == 0 && sfx[j+1] == 0) {
                    ans = max(ans, a[i]-b[j]);
                }
                if (i >= j && ud[i]-ud[j] == 0 && pfx[j-1] == 0 && sfx[i+1] == 0) {
                    ans = max(ans, a[i]-b[j]);
                }
            }
        }
        
        cout << "Case #" << tc << '\n';
        cout << ans << '\n';
    }
}

 
스퀘어 코드

#include <bits/stdc++.h>
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
using namespace std;
using ll = long long;
using ii = pair<int,int>;

const int N = 50003, B = 250, M=N;
int n, m;
int a[N];
struct Q{int l,r;} q[M];
ll res, ans[M];

int cnt[N], tmp[N];
int bigs_stepup_count;

void pop(int x) {
    if (x > n) return;
    if (x <= B) { cnt[x]--; return; }
    if (cnt[x]%x == 0) {
        bigs_stepup_count--;
    }
    --cnt[x];
}
void push(int x) {
    if (x > n) return;
    if (x <= B) { cnt[x]++; return; }
    ++cnt[x];
    if (cnt[x]%x == 0) {
        bigs_stepup_count++;
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int testCase; cin >> testCase; for (int tc = 1; tc <= testCase; ++tc)
    {
        cin >> n;
        for (int i=1; i<=n; ++i) cin >> a[i];
        cin >> m;
        for (int i=1; i<=m; ++i) cin >> q[i].l >> q[i].r;
        
        vector<int> idxs(m);
        iota(begin(idxs),end(idxs),1);
        sort(begin(idxs),end(idxs),[](int x, int y) {
            return make_pair(q[x].l/B,q[x].r) < make_pair(q[y].l/B,q[y].r);
        });
        
        int fr=0, ba=-1;
        for (int i : idxs) {
            auto [s,e] = q[i];
            while (fr<s) pop(a[fr++]);
            while (e<ba) pop(a[ba--]);
            while (s<fr) push(a[--fr]);
            while (ba<e) push(a[++ba]);
            
            fill(tmp+1,tmp+B+1,0);
            res = bigs_stepup_count;
            
            for (int j=2; j<=B; ++j) {
                cnt[j] += tmp[j];
                res += cnt[j]/j;
                if (j*j <= B) {
                    tmp[j*j] += cnt[j]/j;
                } else {
                    int diff = (cnt[j*j]+cnt[j]/j)/(j*j) - cnt[j*j]/(j*j);
                    res += diff;
                }
                cnt[j] -= tmp[j];
            }
            ans[i] = res;
        }
        
        fill(cnt,cnt+n+1,0);
        bigs_stepup_count=0;
        
        cout << "Case #" << tc << "\n";
        for (int i=1; i<=m; ++i) cout << ans[i] << '\n';
    }
}

 
여담) 술을 잔뜩 먹고 새벽 6~7시 즈음에 1,2,3번을 푼 뒤 좀 잤다가 일어나서 4,5번을 풀었다 ㅋㅋㅋ