제2회 청소년 IT경시대회 고등부 (알고리즘 부문) 풀이

일단 대회 자체는 3월 중순인가? 그때 있었다. 근데 왜 지금 쓰냐면 업솔빙하기 귀찮아서 미루고 있다가 여름학교 때 갑자기 생각나서 다 풀었다.

 

일단 본 대회 때는 은상이었다. 3개 중에 1개 풀었는데 은상인것도 재밌지만 1번과 2,3번의 난이도 격차가 커서 그럴 만도 하다. 근데 솔직히 2번 안잡고 3번 쭉 잡았으면 2개는 풀었을듯

난이도는 굳이 따지자면 개인적으로 KOI 고등부보다는 쉽다. 근데 애초에 문제 스타일이 좀 달라서 직접 비교하기는 좀 힘들다.

 

1번 - 즐거운 회의 (KITPA 2회 고등부 1번)

문제 링크

 

티어

solved.ac Gold V (20240815 기준)

 

알고리즘 분류

solved.ac : prefix_sum

작성자 풀이 : graph_theory

 

풀이

친한 관계를 그래프의 간선으로 생각하자. 어떤 시각 t에서 간선 u-v의 가중치는 u와 v가 모두 시각 t에 회의에 있다면 1, 아니면 0이다. 어떤 사람이 들어오고 나가는 것을 시간 순서대로 처리한 후, 그 시간대의 가중치 합을 구해주면 된다.

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define all(x) x.begin(),x.end()
typedef pair<ll,ll> pi;
using namespace std;
const ll inf = 1e18;
vector<ll> adj[202020];
ll n, m, t;
vector<ll> event[202020];
bool chk[202020];
int main(){
    fast;
    cin>>n>>m>>t;
    for(int i = 1 ; i <= n ; i++){
        ll a,b; cin>>a>>b; event[a].push_back(i), event[b].push_back(-i);
    }
    for(int i = 0 ; i < m ; i++){
        ll a,b; cin>>a>>b; adj[a].push_back(b); adj[b].push_back(a);
    }
    ll ans = 0;
    for(int i = 0 ; i < t ; i++){
        for(auto j : event[i]){
            if(j>0){
                for(auto k : adj[j])if(chk[k])ans++;
                chk[j]=1;
            }
            else{
                j=-j;
                for(auto k : adj[j])if(chk[k])ans--;
                chk[j]=0;
            }
        }
        cout<<ans<<"\n";
    }
}

 

 

2번 - 리스트 가상화

문제 링크

 

티어

solved.ac Diamond V (20240815 기준)

 

알고리즘 분류

solved.ac : sqrt_decomposition

작성자 풀이 : sqrt_decomposition, linked_list

 

풀이

일단 주어지는 쿼리가 굉장히 관리하기 까다로운 형태이다. 뭔가 자료구조에 넣어서 관리하기는 힘들다. 그래서 우리는 항목을 몇 개의 그룹으로 묶어서 관리할 것이다. 그룹의 크기는 최대 B이며, 위치 순서대로 묶을 것이다. k번째 그룹은 다음과 같은 정보를 관리한다.

bucket[k] := k번째 그룹에 들어있는 모든 항목의 높이 합

l[k] := linked list(삽입, 삭제가 O(1), random access가 O(N))이며, 순서대로 그룹에 들어있는 항목을 관리

이렇게 구성하면 우리는 1, 2, 3번 쿼리를 모두 처리할 수 있다.

1번 쿼리는 임의의 위치에 항목을 삽입해야 한다. 먼저 이 항목이 들어갈 그룹의 번호를 찾자. 이는 O(s/B)에 할 수 있다. s는 현재 존재하는 항목 수이다. 들어갈 그룹의 번호를 x라 하면, l[x]에 맞는 위치에 이 항목을 넣어준다. 만약 이 항목을 넣어서 그룹 크기가 B+1이 되었다면(포화 상태), l[x]에서 가장 뒤에 있는 항목을 l[x+1]로 옮겨준다. 만약 l[x+1]도 이렇게 포화 상태가 된다면 포화 상태가 되지 않을 때까지 반복해서 옮긴다. 이 과정 역시 O(s/B)가 걸린다.

2번 쿼리인 삭제도 비슷하게 처리할 수 있다. 대신 거꾸로 뒤에서 항목을 가져와야 한다. 그리고 이를 처리하면서 bucket[x]도 계속 갱신해줘야 한다.

이 정보들을 가지고 3번 쿼리를 처리할 수 있다. 쿼리로 구간 [l,r]이 들어왔다면 그룹은 다음과 같은

(i)이 구간에 완전히 포함되는 그룹

(ii)전혀 겹치지 않는 그룹

(iii)완전히 포함되진 않지만 겹치는 그룹

3가지로 나뉜다. (i)인 경우 그룹에 대한 답을 O(1)에 계산할 수 있으며 (ii)는 무시하면 되고, (iii)은 그룹 내부를 일일히 봐주면 된다. 그룹 당 O(B)가 걸리지만, (iii)인 그룹 개수는 2개 이하여서 결국 O(B)가 걸린다.

그룹의 개수는 O(s/B)이므로 3번 쿼리를 처리하는 데 드는 시간복잡도는 O(s/B + B)이다.

1번, 2번 쿼리의 시간복잡도는 O(s/B), 3번 쿼리의 시간복잡도는 O(s/B + B)이므로, 전체 시간복잡도는 O(Q(s/B + B)) 정도가 된다. 이제 B를 적절히 잡아서 이를 최소화해주면 된다. 이는 결국 s/B + B를 최소화하면 되며, s <= N+Q이므로 B = sqrt(N+Q)로 잡아주면 6초 안에 충분히 통과할 수 있는 시간복잡도가 나온다. 

문제 조건이 더러워서(..) 3번 쿼리를 구현할 때 굉장히 까다롭다. 구현 간단하게 하려고 2를 곱한다던지 별짓을 다해봤는데 그냥 정석대로 하는게 실수가 없었다. 조건을 잘 봐가면서 구현하자.

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define all(x) x.begin(),x.end()
typedef pair<ll,ll> pi;
using namespace std;
const ll inf = 1e18;
ll n, q;
vector<ll> h;
const ll sz = 700;
ll bucket[404040/sz];
list<ll> l[404040/sz];
void insert(ll i, ll h){    //i : 0-indexed
    ll num = 0;
    while(l[num].size() < i)i -= (int)l[num++].size();
    auto it = l[num].begin(); while(i--)++it;
    l[num].insert(it,h); bucket[num] += h;
    while(l[num].size() > sz){
        l[num+1].push_front(l[num].back());
        bucket[num+1] += l[num].back();
        bucket[num] -= l[num].back();
        l[num].pop_back();
        num++;
    }
}
void erase(ll i){
    ll num = 0;
    while(l[num].size() <= i)i -= (int)l[num++].size();
    auto it = l[num].begin(); while(i--)++it;
    bucket[num] -= *it; l[num].erase(it);
    while(l[num+1].size()){
        l[num].push_back(l[num+1].front());
        bucket[num] += l[num+1].front();
        bucket[num+1] -= l[num+1].front();
        l[num+1].pop_front();
        num++;
    }
}
ll query(ll s, ll e){
    ll sum = 0;
    ll ret = 0;
    for(int i = 0 ; l[i].size() ; i++){
        if(s <= sum and sum+bucket[i] <= e){
            ret += l[i].size();
            sum += bucket[i];
        }
        else if((sum <= s and s < sum+bucket[i]) or (sum < e and e <= sum+bucket[i]) or(sum <= s and e <= sum+bucket[i])){
            for(auto j : l[i]){
                if((s <= sum and sum < e) or (s < sum+j and sum+j <= e) or (sum <= s and e <= sum+j))ret++;
                sum += j;
            }
        }
        else sum += bucket[i];
    }
    return ret;
}
int main(){
    fast;
    cin>>n>>q;
    h.resize(n);
    for(int i = 0 ; i < n ; i++){
        cin>>h[i];
        insert(i,h[i]);
    }
    while(q--){
        ll op, i, j; cin>>op>>i;
        if(op==1){ i--;
            cin>>j;
            insert(i,j);
        }
        if(op==2){ i--;
            erase(i);
        }
        if(op==3){
            cin>>j;
            cout<<query(i,j)<<"\n";
        }
    }
}

 

 

3번 - 캐시 메모리 정하기

문제 링크

 

티어

solved.ac Diamond V (20240815 기준)

 

알고리즘 분류

solved.ac : segtree, lazyprop

작성자 풀이 : segtree(금광세그)

 

lazyprop으로 풀 수도 있는 것 같은데 잘 모르겠다. 

 

풀이

이 문제는 발상적인 난이도가 조금 있고, 그 외에는 사전지식이 필요하다.

시작하기 전에, 답에다가 Y * B[i]를 일단 더해두고 캐시 메모리에 옮기는 작업을 (Y-X) * B[i]를 뺀다고 생각하자.

중요한 것은 배열 A에서 연속한 구간을 골라야 한다는 것이다. 이 연속한 구간의 시작 지점을 고정해보자.

시작 지점을 고정하면 굉장히 좋은 것은 배열 A의 가중치를 고정할 수 있다는 것이다. 시작 지점을 i로 고정했다고 생각하면, A[j] (1<=j<=N)의 가중치 W[j]는 다음과 같다.

W[j] = -k (j<i거나, i <= k < j, A[j] = A[k]인 k가 존재하는 경우)

W[j] = -k + (Y-X)*B[A[j]] (그 외의 경우)

이런 식으로 가중치를 부여하면 이 문제가 배열 W의 최대 연속합을 구하는 문제로 환원되며, 이는 최대 연속합 세그먼트 트리(a.k.a 금광세그)로 해결할 수 있음이 잘 알려져있다. 관련된 자료가 많으니 여기서는 설명을 생략한다.

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define all(x) x.begin(),x.end()
typedef pair<ll,ll> pi;
using namespace std;
const ll inf = 1e18;
ll n, m, k, x, y;
vector<ll> A, B;
struct Node{
    ll lm, rm, m, sum;
};
vector<ll> pos[202020];
struct segtree{
    vector<Node> tree;
    segtree(): tree(808080){}
    Node merge(Node a, Node b){
        return {max(a.lm, a.sum+b.lm), max(b.rm, b.sum+a.rm), max({a.m, b.m, a.rm+b.lm}), a.sum+b.sum};
    }
    void upd(ll node, ll s, ll e, ll i, ll d){
        if(e<i or i<s)return;
        if(s==e)tree[node] = {d,d,d,d};
        else{
            ll mid = s+e>>1;
            upd(node<<1,s,mid,i,d); upd(node<<1|1,mid+1,e,i,d); tree[node] = merge(tree[node<<1], tree[node<<1|1]);
        }
    }
} seg;
int main(){
    fast;
    cin>>n>>m>>k>>x>>y;
    A.resize(m+1); B.resize(n+1);
    ll sum = 0;
    for(int i = 1 ; i <= m ; i++)cin>>A[i], pos[A[i]].push_back(i); for(int i = 1 ; i <= n ; i++)cin>>B[i], sum += B[i];
    vector<ll> idx(n+1);
    for(int i = 1 ; i <= m ; i++){
        if(pos[A[i]][0] == i)seg.upd(1,1,m,i,-k + B[A[i]] * (y-x));
        else seg.upd(1,1,m,i,-k);
    }
    ll ans = 0;
    for(int i = 1 ; i <= m ; i++){
        ans = max(ans, seg.tree[1].m);
        if(idx[A[i]]+1 < pos[A[i]].size()){
            seg.upd(1,1,m,i,-k);
            seg.upd(1,1,m,pos[A[i]][++idx[A[i]]],-k + B[A[i]] * (y-x));
        }
    }
    cout<<sum*y - ans;
}

 

체감 난이도는 1번 < 3번 < 2번이다. 2번은 진짜 더러워서 대회 중엔 멍때리다 끝났다.