SCPC 2023 1차 예선 대회 후기 + 풀이

4번의 서브태스크를 잘 긁어서 820/900점으로 마무리했다!

SCPC도 군대 이슈로 이번이 첫 도전이었는데, 나름 만족스러운 점수를 받은 것 같다.

최근에 현대모비스 알고리즘 경진대회, UCPC에서 연달아 광탈하면서 떨어졌던 자신감이 복구되는 듯했으나, 대회 후기들을 보니 3, 4, 5번 문제가 각각 KMP, Z알고리즘, CHT(컨벡스 헐 트릭)으로 웰노운이었다는 소식에 다시 우울해졌다. ㅠㅠ

나는 세 알고리즘 모두 이름만 들어봤지 응용하는 방법은 모르고 풀었기에, 그들만의 웰노운이 아닌 좀 더 친숙한 알고리즘으로 풀이를 소개할 수 있을 것 같다.

 

풀이

---

1. 증강현실 배달 안경

$O(N)$의 풀이가 1초 이내에 동작하기 때문에, 별 고민 없이 모든 경우에 대해 완전탐색을 해주었다.

코드

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

void solve(){
    int n,a,b;cin>>n>>a>>b;
    int ans=0;
    for(int i=0;i<=n/a;i++)
        if((n-i*a)%b==0)
            ans=max(ans,i+(n-i*a)/b);
    cout<<ans<<endl;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    int tc;cin>>tc;
    for(int i=1;i<=tc;i++){
        cout<<"Case #"<<i<<endl;
        solve();
    }
    return 0;
}

 

---

2. 딸기 수확 로봇

로봇이 원점에서 시작하므로, 최적으로 움직이는 경우는 아래의 두 가지이다.

1. 오른쪽(+)으로 갔다가, 원점으로 되돌아와서 왼쪽(-)으로 최대한 가기
2. 왼쪽(-)으로 갔다가, 원점으로 되돌아와서 오른쪽(+)으로 최대한 가기

1번의 경우를 예로 들면, 오른쪽에 있는 특정 딸기의 위치$(=X)$까지 간 다음, 이분 탐색을 사용해서 남은 이동 거리$(D-2X)$로 왼쪽으로 어디까지 갈 수 있는지 찾아주면 된다.

시간복잡도는 특정 딸기를 고르는 데 $O(N)$, 이분 탐색에 $O(logN)$이므로 $O(NlogN)$.

코드

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

void solve(){
    int n,d;cin>>n>>d;
    vector<int> pl,mi;
    int zero=0;
    for(int i=0;i<n;i++) {
        int x;cin>>x;
        if(x>0)pl.push_back(x);
        else if(x<0)mi.push_back(-x);
        else zero++;
    }
    sort(pl.begin(),pl.end());
    sort(mi.begin(),mi.end());
    int ans=zero;
    for(int i=0;i<pl.size();i++){
        if(pl[i]>d)break;
        int dd=d-pl[i]*2;
        int x=upper_bound(mi.begin(),mi.end(),dd)-mi.begin()-1;
        ans=max(ans,zero+i+x+2);
    }
    for(int i=0;i<mi.size();i++){
        if(mi[i]>d)break;
        int dd=d-mi[i]*2;
        int x=upper_bound(pl.begin(),pl.end(),dd)-pl.begin()-1;
        ans=max(ans,zero+i+x+2);
    }
    cout<<ans<<endl;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    int tc;cin>>tc;
    for(int i=1;i<=tc;i++){
        cout<<"Case #"<<i<<endl;
        solve();
    }
    return 0;
}

 

---

3. 장난감

우선, 쇠구슬이 시간이 지날수록 적은 개수로 고르게 흩어진다는 관찰을 해야한다.

따라서 개수의 총합 $sum>=N$이면 충분히 시간이 지난 후에 모든 칸에 적어도 한 개의 쇠구슬이 존재하게 되므로, 시간에 따른 상태의 변화가 없게 된다. ($sum=0$일 때도 마찬가지)

그러면 흩어지는 작업을 어떻게 처리해야 할까?

쇠구슬이 움직일 때, 어떤 위치에 $x>1$개의 쇠구슬이 있었다면 1개의 쇠구슬만 시계방향으로 이동하고, 나머지 $x-1$개의 쇠구슬은 제자리에 남는다. 장난감이 원형이므로 이를 다르게 표현하면, 1개의 쇠구슬만 제자리에 두고 $x-1$개의 쇠구슬이 시계 반대방향으로 이동한다고 볼 수 있다.

이때 제자리에 남겨진 1개의 쇠구슬이, 바로 우리가 원하던 고르게 흩어진 쇠구슬이다!

이 작업은 그냥 시뮬레이션 코드를 작성하면 되는데, $sum<N$인 경우만 생각하므로 $O(N)$의 시간복잡도면 충분하다.

시뮬레이션 이후에는 모든 칸이 0 또는 1의 값만 가지게 되므로, 서브태스크 그룹 2의 상태와 같아졌다.

이제 이 배열의 최대 길이의 주기를 찾으면 되는데, 여기서 KMP를 알고 있다면 바로 적용해 주면 된다.

모른다면 완전탐색을 해야 하는데, 일단 길이 $N$인 배열의 주기는 $N$의 약수임이 자명하므로 $N$의 모든 약수 $f$에 대해서만 전부 시도하면 된다.

시간이 많이 빡빡할 것 같아서 이것저것 최적화를 해주었더니 0.4초 정도에 통과했다..

코드

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

void solve(){
    int n;cin>>n;
    vector<int> v(n);
    ll sum=0;
    for(int i=0;i<n;i++)cin>>v[i],sum+=(ll)v[i];

    //시간에 따른 변화 없음
    if(sum>=n||!sum){
        cout<<1<<endl;
        return;
    }

    //시뮬레이션
    for(int i=n+n;i>=0;i--){
        if(!v[i%n])continue;
        v[(i-1+n)%n]+=v[i%n]-1,v[i%n]=1;
    }

    vector<int> num;
    //최적화) 0,1중에 더 적은 숫자에 대해서만 주기성 체크.
    if(n>sum+sum){
        for(int i=0;i<n;i++)
            if(v[i])num.push_back(i);
    }
    else{
        for(int i=0;i<n;i++)
            if(!v[i])num.push_back(i);
    }

    int ans=n;
    vector<int> f;
    for(int i=2;i*i<=n;i++){
        if(n%i)continue;
        f.push_back(i);
        if(n/i!=i)f.push_back(n/i);
    }
    sort(f.begin(),f.end());
    for(auto len:f){
        vector<int> sets(len);
        for(auto i:num)
            sets[i%len]++;
        bool ok=1;
        for(auto i:sets)if(i!=0&&i!=n/len)ok=0;
        if(ok){ans=len;break;}
    }
    cout<<ans<<endl;
    return;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    int tc;cin>>tc;
    for(int i=1;i<=tc;i++){
        cout<<"Case #"<<i<<endl;
        solve();
    }
    return 0;
}

---

4. 최적의 프로세스 수행 순서 (만점 X)

몇 번의 시도 끝에 $O(N)$에 그리디하게 선택하는 풀이가 떠오르지 않아서, 나는 $O(N^{2})$의 코드를 제출하고 마무리했다. (라빈 카프 알고리즘이나 Z 알고리즘을 알면 모든 그룹의 테스트 케이스를 통과할 수 있다고 한다.)

bfs로 모든 경우를 탐색했는데, 큐에 담는 정보는 [x, y] : y번 째 프로세스까지 x개의 구간으로 나누는 데 성공했다는 뜻이다.

프로세스를 적게 나누는 순으로 탐색했기 때문에, $y==R$의 길이$-1$인 경우를 찾았다면 그 경우가 답이 된다.

코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;

void solve(){
    string r,p;cin>>r>>p;
    int rn=r.size(),pn=p.size();
    if(rn>10000||pn>10000){
        cout<<-1<<endl;
        return;
    }
    queue<pii> q;
    vector<bool> vis(rn);
    int ridx=0,pidx=0;
    while(ridx<rn&&pidx<pn&&r[ridx]==p[pidx])
        q.push({1,ridx}),vis[ridx]=1,ridx++,pidx++;
    while(!q.empty()){
        auto [len,e]=q.front();q.pop();
        if(e==rn-1){
            cout<<len<<endl;
            return;
        }
        ridx=e+1,pidx=0;
        while(ridx<rn&&pidx<pn&&r[ridx]==p[pidx]){
            if(!vis[ridx])vis[ridx]=1,q.push({len+1,ridx});
            ridx++,pidx++;
        }
    }
    cout<<-1<<endl;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    int tc;cin>>tc;
    for(int i=1;i<=tc;i++){
        cout<<"Case #"<<i<<endl;
        solve();
    }
    return 0;
}

 

---

5. 타이젠

우선 작업 수행 구간에서는 항상 액티브 상태$(=s1)$의 전력을 소모해야 하므로, 모두 더해서 $p[0]$만 곱해주면 된다.

이제 수면 구간에 대해서 잘 관찰해 보자.

1. 만약 수면 구간의 길이가 매우 짧다면(=0이라면), 단위 시간당 전력량이 아무 쓸모가 없으므로 액티브 상태를 유지하는 게 최선이다.(m개의 상태 중 index=0을 선택한다.)
2. 반면에 만약 수면 구간의 길이가 매우 길다면(=∞이라면), 단위 시간당 전력량이 가장 적은 상태를 선택함으로써 엄청난 이득을 챙길 수 있다.(m개의 상태 중 index=m-1을 선택한다.)

위의 관찰을 통해, 내가 길이 x인 수면 구간의 최선의 상태 y를 알고 있다면, 길이가 x보다 긴 수면 구간들은 답이 y 미만이 될 수 없으며, 길이가 x보다 짧은 수면 구간들은 답이 y 초과가 될 수 없다!

따라서 분할정복으로 답의 후보들을 적절히 줄여나가면, $O(MlogN)$의 시간복잡도로 모든 상태를 구할 수 있다.

코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
vector<ll> p,w;
vector<pll> sl;
ll ans;
int f(ll len,int s,int e){
    ll best=s;
    for(int i=s+1;i<=e;i++)
        if(len*p[best]+w[best]>len*p[i]+w[i])best=i;
    return best;
}

void divide(int ns,int ne,int s,int e){
    if(ns>ne)return;
    int mid=(ns+ne)/2;
    int best=f(sl[mid].first,s,e);
    ans+=sl[mid].first*p[best]+w[best];
    divide(ns,mid-1,s,best),divide(mid+1,ne,best,e);
}

void solve(){
    int n;cin>>n;
    vector<ll> v;
    ans=0;
    sl.clear();
    for(int i=0;i<n;i++){
        ll r,d;cin>>r>>d;
        if(!v.empty())sl.push_back({r-v.back(),(int)sl.size()});
        v.push_back(r),v.push_back(d);
        ans+=d-r;
    }
    int m;cin>>m;
    p.resize(m),w.resize(m);
    for(int i=0;i<m;i++)cin>>p[i];//시간당 전력 소비량
    for(int i=0;i<m;i++)cin>>w[i];//되돌리는 비용
    ans*=p[0];
    sort(sl.begin(),sl.end());
    divide(0,(int)sl.size()-1,0,m-1);
    cout<<ans<<endl;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    int tc;cin>>tc;
    for(int i=1;i<=tc;i++){
        cout<<"Case #"<<i<<endl;
        solve();
    }
    return 0;
}

(사실 이 문제는 나무 자르기라는 문제를 풀어본 적 있는 분들에게는 그냥 대놓고 "CHT 써주세요" 하는 문제였다고 한다.)

---

후기

대회를 마치고 많은 분들의 풀이를 보면서, 내가 모르는 알고리즘이 이렇게나 많았다는 것에 반성하게 되었다.

심지어 대회 이틀 전에 kmp를 공부할 계기가 있었는데도, 이해하기 어렵기도 하고 '설마 나오겠어?'라는 마음으로 미뤘더니 바로 당해버렸다. 대회가 끝나고 선배님이 3, 4번 문제 모두 해싱으로 풀 수 있다는 말씀과 함께 직접 작성하신 해싱과 관련된 좋은 글을 추천해 주셔서, 이제 미루지 말고 문자열도 공부해야겠다.

한편으로는 알고리즘을 모르는데도 문제들을 풀어냈다는 것에 뿌듯하기도 하다. 최근에 solved.ac 다이아 2티어를 달성하기 위해 열심히 공부 중이었는데, 그때 분할정복을 연습했던 덕분에 운 좋게 5번 문제를 맞힐 수 있었다.

2차 예선에 대비해서 여러 가지 최적화 기법이나 트릭들을 많이 알아두면 좋을 것 같다.