SCPC 2023 1차 예선 후기

7/28 15:00 ~ 7/29 15:00

간만의 포스팅입니다. 매년 나가보는 SCPC.

이번에는 며칠 밤을 샌 채로 대회를 쳐서 대충 풀겠다고 마음먹었다가 제출횟수가 나락으로 가버렸습니다.

난이도는 5번은 안풀었지만 대강 1<2<4=5<3쯤 될 것 같아요

올해는 배점이 재미없어졌습니다 :(

1. 증강현실 배달 안경

문제 요약

주어진 N, A, B에서 A*p + B*q = N에 대해 p+q를 최대화 할 때의 값은?

 

풀이

확장 유클리드를 사용해도 괜찮고, 작은 그룹이 더 많아야하므로 p' = N/A로 두고 투포인터 느낌으로 q'을 조금씩 늘려가면서 A*p' +B*q' == N일 때 값을 구하면 됩니다.

 

소스코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int M = 1e9+7, N = 1e5;

int f(int n, int p, int q){
    if(p>q) swap(p,q);
    for(int a = n/p, b = 0; a; --a){
        for(int A = a*p; A+(b+1)*q <= n; ++b);
        if(a*p+b*q == n) return a+b;
    }
    return -1;
}

int main(){
    scanf("%*d");
    for(int n, p, q, c=1; ~scanf("%d%d%d",&n,&p,&q); printf("Case #%d\n%d\n",c++,f(n,p,q)));
}

2. 딸기 수확 로봇

문제 요약

1차원 좌표 평면 상에 딸기가 있고 로봇은 원점에서 시작해서 최대 D만큼 움직여 어디서는 멈출 수 있다. 로봇이 딸기가 심어진 좌표를 지나면 딸기가 수확되는데, 딸기를 최대한 수확할 때 몇 개를 얻을 수 있는가?

 

풀이

경우의 수는 4가지입니다.

1. 원점기준 왼쪽으로 이동

2. 원점기준 오른쪽으로 이동

3. 원점기준 왼쪽갔다가 오른쪽으로 이동

4. 원점기준 오른쪽갔다가 왼쪽으로 이동

 

3, 4 케이스는 투포인터로 linear하게 구할 수 있겠지만, 시간복잡도도 널널하기에 이분탐색으로 위치를 구했습니다.

 

소스코드

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

ll f(){
    ll n, d;
    scanf("%lld%lld",&n,&d);
    vector<ll> v(n);
    for(auto&t:v) scanf("%lld",&t);
    sort(v.begin(), v.end());
    ll z1 = lower_bound(v.begin(), v.end(), 0LL) - v.begin(); // 0
    ll z2 = upper_bound(v.begin(), v.end(), 0LL) - v.begin(); // 0
    ll r = z2 - z1;
    for(ll i=0; i<n; ++i){
        if(abs(v[i]) > d) continue;
        if(v[i] < 0){
            r = max(r, z2 - i);
            ll j = upper_bound(v.begin(), v.end(), (d + v[i]) / 2) - v.begin();
            r = max(r, j - i);
        }
        else if(v[i] > 0){
            r = max(r, i - z1 + 1);
            ll j = lower_bound(v.begin(), v.end(), (v[i] - d) / 2) - v.begin();
            r = max(r, i - j + 1);
        }
    }
    return r;
}

int main(){
    int T;
    scanf("%d",&T);
    for(ll c=1; T--; ++c) printf("Case #%lld\n%lld\n",c,f());
}

3. 장난감

문제 요약

원형 큐에서 각 위치에 Ai개의 구슬이 있고, 한 시점에서 다음 시점으로 넘어갈 때 Ai 위치에 구슬이 있다면 다음 시점에 시계방향 다음 위치에 구슬을 넘기는 과정을 반복해서 사이클이 생길 때 그 길이를 구합니다.

 

풀이

두 스텝으로 해결했습니다.

1. 사이클 시작 시점 상태 구하기

2. 사이클 길이 구하기

 

1. 사이클 시작 시점은 구슬의 0인 부분을 최대한 채워가면 알 수 있습니다.

0인 부분이 가능한 대부분 채워지면 위상이 같은 상태로 회전을 하게 됩니다.

간단하게 관찰하자면, 0인 부분은 시계방향 가장 가까운 구슬 개수가 1 초과인 위치에서 구슬을 하나 얻어와 채울 수 있습니다.

이는 스택으로 잘 구현할 수 있으니 아래 코드를 확인해주세요

 

2. 사이클 길이는 kmp를 사용하면 쉽게 구할 수 있으나, 대회중에 생각을 못해서 소인수분해 해가면서 나눠봤었습니다.

n의 소인수 k에 대해 i + j * n / k (j = 0, ..., k) 위치의 값들이 모두 같으면 그만큼 사이클 길이를 나눠줄 수 있으므로

n을 k로 나눈 후 또 다른 k'에 대해 확인하는걸 반복합니다.

마지막으로 남은 n 값이 사이클 길이가 됩니다.

 

0이 없는 상태인 경우 시간이 지나도 상태가 유지되므로 사이클 길이는 1입니다.

 

소스코드

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

int M[500001];
vector<int> V;

ll f(){
    int n;
    scanf("%d",&n);
    vector<pair<int,int>> a, b;
    int q = -1, c = 0, w;
    for(int i=0; i<n; ++i){
        scanf("%d",&w);
        if(!w){ if(q==-1) q=i; ++c; }
        else if(w>1){
            if(q!=-1) a.push_back({q,c}), q=-1, c=0;
            int t = w - 1;
            if(a.size()){
                for(; a.size() && t;){
                    if(a.back().second <= t) t-=a.back().second, a.pop_back();
                    else a.back().second -= t, t=0;
                }
            }
            if(t) b.push_back({i,t});
        }
        else if(q!=-1) a.push_back({q,c}), q=-1, c=0;
    }
    if(q!=-1) a.push_back({q,c}), q=-1;
    for(c=0; c<b.size() && a.size();){
        if(a.back().second <= b[c].second) b[c].second -= a.back().second, a.pop_back();
        else a.back().second -= b[c].second, ++c;
    }
    if(!a.size()) return 1;
    vector<int> v(n,1);
    for(; c<b.size(); ++c) v[b[c].first] = b[c].second + 1;
    for(auto&[x,y]:a) for(c=0; c<y; ++c) v[x+c] = 0;

    auto g = [&](int k){for(int i=0; i<k; ++i) for(int j=1; j<V[c]; ++j) if(v[i]!=v[i+j*k]) return 0;return 1;};
    for(c=0; c<V.size() && V[c] <= n && n>1;){
        if(n%V[c]!=0) {++c; continue;}
        if(g(n/V[c])) n/=V[c];
        else ++c;
    }
    return n;
}

int main(){
    setbuf(stdout, NULL);
    //freopen("output.txt","w",stdout);
    for(int i=2; i<=500000; i += i>2?2:1){
        if(M[i]) continue;
        V.push_back(i);
        for(int j=i+i; j<=500000; j+=i) M[j]=1;
    }
    int T;
    scanf("%d",&T);
    for(ll c=1; T--; ++c) printf("Case #%lld\n%lld\n",c,f());
}

4. 최적의 프로세스 수행 순서

문제 요약

진행하고자 하는 프로세스 R이 있고 효율적인 프로세스 패턴 P가 있습니다.

R을 연속적으로 잘 분해해서 각 segment가 P의 접두사가 될 수 있게 할 때, segment의 수를 최소화하는 문제입니다.

 

풀이

문제를 보면 KMP를 떠올릴 수 있습니다.

P 문자열에 대해 failure function f를 만들고 j로 확인할 위치를 지정한다고 할 때, 아래 점화식을 얻을 수 있습니다.

D[0] = 0

D[i + 1] = D[i - f(j) - 1] + 1

답은 D[|R|]이 됩니다.

 

소스코드

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

ll f() {
    string s1, s2;
    cin >> s1 >> s2;

    vector<int> v(s1.size() + 1, -1); v[0] = 0;
    vector<int> f(s2.size() + 1,0); f[0] = -1;
    for (int i = 0, j = -1; i < s2.size(); f[++i] = ++j) while (~j && s2[i] != s2[j]) j = f[j];
    for (int i = 0, j = 0, t = 0; i < s1.size(); ++i) {
        while (~j && s1[i] != s2[j]) j = f[j]; ++j;
        if (v[i - j + 1] > -1)v[i + 1] = v[i - j + 1] + 1;
    }
    return v[s1.size()];
}

int main() {
    int T;
    cin >> T;
    for (ll c = 1; T--; ++c) cout << "Case #" << c << '\n' << f() << endl;
}

5. 타이젠

문제 요약 및 풀이

일반적인 CHT문제이므로 문제는 생략하겠습니다.

f(x = A[i]) = B[i] * x + C[i]에 대해 A는 활성 구간 사이의 휴식구간 길이, B는 Pi, C는 Wi로 생각하면 됩니다.

 

너무 피곤해서 자고 나니 시간이 안남아서.. 풀지 못했습니다 ㅠ