solved.ac class 7++ 도전기 5 (완)

작성일 | In

이전 포스트
solved.ac class 7++ 도전기 1
solved.ac class 7++ 도전기 2
solved.ac class 7++ 도전기 3
solved.ac class 7++ 도전기 4

github

　드디어 class 7++ 등반을 마쳤습니다! 사실 마친지는 좀 됐는데, 중간고사 공부와 ICPC 대비를 하느라 글 적는게 좀 늦었습니다. 지난번에 글 올리고 났을 때 네 문제가 남은 상태였는데, 이번에는 따로 시간을 재고 풀진 않았습니다. 문제 목록은 다음과 같습니다.

　A. BOJ 3295 - 단방향 링크 네트워크
　B. BOJ 3683 - 고양이와 개
　C. BOJ 14959 - Slot Machines
　D. BOJ 18251 - 내 생각에 A번인 단순 dfs 문제가 이 대회에서 E번이 되어버린 건에 관하여 (Easy)

　A. BOJ 3295 - 단방향 링크 네트워크

　티어: 플래티넘 II

　SCC쪽으로 신나게 뇌절했던 문제인데, 정작 정해는 이분 매칭이었습니다. 모델링은 다음과 같이 하면 됩니다.

  1. 각 정점을 2개로 쪼갭니다. 각각을 정점 A, 정점 B라고 하겠습니다.
  2. Source와 정점 A를, Sink와 정점 B를 연결합니다. 이제 정점 A는 정점의 outdegree를, 정점 B는 정점의 indegree를 의미합니다. 이때, 링과 선형 배열 모두 indegree와 outdegree가 최대 1이므로, capacity는 1입니다.
  3. 모든 간선에 대해, 출발점의 A정점과 도착점의 B정점을 연결합니다. 간선은 한 번만 쓰일 수 있으므로, capacity는 당연히 1입니다.

　이렇게 모델링을 하면 매칭된(유량이 흐른) 간선의 개수가 곧 답이 됩니다. k개의 노드로 이루어진 선형 배열은 정확히 k-1개의 간선으로 이루어져있고, k개의 노드로 이루어진 링은 정확히 k개의 간선으로 이루어져있으며, 각각 분해했을 때 k-1점과 k점을 얻는 것이 맞으므로, 해당 풀이가 정당함을 알 수 있습니다. 개인적으로 정말 깔끔하고 좋은 문제라고 생각합니다.

　코드 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

#include<cstdio>
#include<memory.h>
#include<vector>
#include<queue>
#include<algorithm>
#define S 0
#define T 2001
#define N 2010
#define OUT 1000
#define inf ((int)2e9)

using namespace std;
using ll=long long;
using pii=pair<int,int>;

struct edge{int pos,cap,rev;};
vector<edge> graph[N];
void clear(){
    for(int i=0;i<N;++i)graph[i].clear();
}
void add_edge(int s,int e,int x){
    graph[s].push_back({e,x,(int)graph[e].size()});
    graph[e].push_back({s,0,(int)graph[s].size()-1});
}
int dist[N],work[N];
bool bfs(int src,int sink){
    memset(dist,0,sizeof(dist));
    memset(work,0,sizeof(work));
    queue<int> q;
    q.push(src);
    dist[src]=1;
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(auto &e:graph[x]){
            if(e.cap>0 &&!dist[e.pos]){
                dist[e.pos]=dist[x]+1;
                q.push(e.pos);
            }
        }
    }
    return dist[sink]>0;
}
int dfs(int x,int sink,int f){
    if(x==sink) return f;
    for(;work[x]<graph[x].size();++work[x]){
        edge e=graph[x][work[x]];
        if(e.cap>0&&dist[e.pos]==dist[x]+1){
            int w=dfs(e.pos,sink,min(f,e.cap));
            if(w){
                graph[x][work[x]].cap-=w;
                graph[e.pos][e.rev].cap+=w;
                return w;
            }
        }
    }
    return 0;
}
ll match(int src,int sink){
    ll ret=0;
    while(bfs(src,sink)){
        int r;
        while((r=dfs(src,sink,inf)))ret+=r;
    }
    return ret;
}

int main(){
    int s,e,n,m;
    char ch;
    int t;
    for(scanf("%d",&t);t--;){
        clear();
        scanf("%d %d",&n,&m);
        for(int i=1;i<=n;++i)add_edge(S,i,1);
        for(int i=1;i<=n;++i)add_edge(OUT+i,T,1);
        for(int i=0;i<m;++i){
            scanf("%d %d",&s,&e);
            ++s;++e;
            add_edge(s,OUT+e,1);
        }
        printf("%lld\n",match(S,T));
    }
}

　B. BOJ 3683 - 고양이와 개

　티어: 플래티넘 III

　이 문제에서 가장 먼저 주목해야 할 점은 시청자들을 딱 두 가지로 분류할 수 있다는 점입니다. 고양이를 좋아하는 시청자와, 개를 좋아하는 시청자. 이 특성으로 인해 두 시청자가 같은 동물에 대해 다른 투표(다음 라운드 진출/탈락)하는 경우는 서로 다른 종류의 시청자끼리만 가능해지고, 이로 인해 이 문제에서도 이분 매칭을 사용할 수 있게 됩니다. 모델링은 다음과 같이 하면 됩니다.

  1. Source와 고양이를 좋아하는 시청자들을, Sink와 개를 좋아하는 시청자들을 연결합니다. 이때, capacity는 당연히 1입니다.
  2. 투표 결과가 충돌하는(둘다 동시에 이루어질 수 없는) 참가자 조합을 모두 간선으로 연결합니다. 마찬가지로 capacity는 당연히 1입니다.

　모델링을 이렇게 하면, 답은 총 시청자 수 - 최대 매칭 수가 됩니다.

　코드 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98

#include<cstdio>
#include<memory.h>
#include<vector>
#include<queue>
#include<algorithm>
#define S 0
#define T 501
#define N 510
#define inf ((int)2e9)

using namespace std;
using ll=long long;
using pii=pair<int,int>;

vector<pii> a,b;
struct edge{int pos,cap,rev;};
vector<edge> graph[N];
void clear(){
    a.clear();b.clear();
    for(int i=0;i<N;++i)graph[i].clear();
}
void add_edge(int s,int e,int x){
    graph[s].push_back({e,x,(int)graph[e].size()});
    graph[e].push_back({s,0,(int)graph[s].size()-1});
}
int dist[N],work[N];
bool bfs(int src,int sink){
    memset(dist,0,sizeof(dist));
    memset(work,0,sizeof(work));
    queue<int> q;
    q.push(src);
    dist[src]=1;
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(auto &e:graph[x]){
            if(e.cap>0 &&!dist[e.pos]){
                dist[e.pos]=dist[x]+1;
                q.push(e.pos);
            }
        }
    }
    return dist[sink]>0;
}
int dfs(int x,int sink,int f){
    if(x==sink) return f;
    for(;work[x]<graph[x].size();++work[x]){
        edge e=graph[x][work[x]];
        if(e.cap>0&&dist[e.pos]==dist[x]+1){
            int w=dfs(e.pos,sink,min(f,e.cap));
            if(w){
                graph[x][work[x]].cap-=w;
                graph[e.pos][e.rev].cap+=w;
                return w;
            }
        }
    }
    return 0;
}
ll match(int src,int sink){
    ll ret=0;
    while(bfs(src,sink)){
        int r;
        while((r=dfs(src,sink,inf)))ret+=r;
    }
    return ret;
}

int main(){
    int c,d,v,anum,bnum,n,m;
    char ch;
    int t;
    for(scanf("%d",&t);t--;){
        clear();
        scanf("%d %d %d",&c,&d,&v);
        for(int i=0;i<v;++i){
            getchar();
            ch=getchar();
            scanf("%d ",&anum);
            getchar();
            scanf("%d",&bnum);
            if(ch=='C')a.push_back({anum,bnum});
            else b.push_back({anum,bnum});
        }
        n=a.size();m=b.size();
        for(int i=1;i<=n;++i)add_edge(S,i,1);
        for(int i=1;i<=m;++i)add_edge(n+i,T,1);
        for(int i=0;i<n;++i){
            for(int j=0;j<m;++j){
                if(a[i].first==b[j].second||a[i].second==b[j].first){
                    add_edge(i+1,n+j+1,1);
                }
            }
        }
        printf("%lld\n",v-match(S,T));
    }
}

　B. BOJ 14959 - Slot Machines

　티어: 플래티넘 III

　길이 n의 수열 중 처음 k개의 수는 진짜 랜덤이고, 이후 주기 p로 같은 숫자가 반복될 때 k와 p를 찾는 문제입니다. 이러한 k와 p가 여러개일 경우, k+p를 최소화해야 하고, 이마저도 같으면 p를 최소화해야 합니다.

　우선 수열이 숫자로 주어지 있기 때문에 발견하기 쉽진 않지만, 반복되는 주기(패턴의 길이)를 찾는다는 점에서 문자열 매칭문제로 치환할 수 있다는 것을 발견할 수 있습니다. 그리고 이런 문제에서 자주 등장하는 알고리즘은 역시 KMP입니다. (Z 알고리즘으로도 가능할 것 같긴 한데, 직접 구현해보진 않았습니다.) 다만 문제는, KMP는 해당 문자열의 ‘prefix’와 얼마나 일치하는지를 따지는 알고리즘인데, 주어진 수열의 prefix는 ‘진짜 랜덤’으로 주어지는 수들이라는 점입니다.

　해결책은, 처음 k개를 제외한 뒷부분은 어디에서 시작하든 주기 p로 반복되고 있기 때문에, 문자열을 뒤집은 뒤에 KMP를 돌리면 됩니다. KMP를 돌리면 pi배열(0번부터 i번까지 봤을 때, prefix와 suffix가 얼마나 일치하는지)은 다음과 같은 형태를 보이게 됩니다.

github

　코드 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

#include<iostream>
#include<sstream>
#include<string>
#define fastio() ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)

using namespace std;

int arr[1000010],brr[1000010];
int n,m;
int p[1000010];
void init(){
    cin>>n;
    for(int i=0;i<n;++i){
        string s;
        cin>>s;
        int idx=0;
        while(idx<s.size()&&s[idx]=='0')++idx;
        if(idx==s.size())continue;
        arr[i]=stoi(s.substr(idx,s.size()-idx));
        brr[n-i-1]=arr[i];
    }
    for(int i=1,j=0;i<n;++i){
        while(j>0&&brr[i]!=brr[j])j=p[j-1];
        if(brr[i]==brr[j])p[i]=++j;
    }
}
void solve(){
    int mx=0,midx=0;
    for(int i=0;i<n;++i){
        if(p[i]>mx){
            mx=p[i];
            midx=i;
        }
    }
    cout<<(n-midx-1)<<" "<<(midx-p[midx]+1);
}

int main(){
    fastio();
    init();
    solve();
}

　B. BOJ 18251 - 내 생각에 A번인 단순 dfs 문제가 이 대회에서 E번이 되어버린 건에 관하여 (Easy)

　티어: 플래티넘 III

　여러모로 열받는 문제였습니다. 풀이는 안떠오르는데 문제에 있는 사진은 ‘꽁으로 주는 문제 선물이에요~’ 이러질 않나, ‘이게 왜 E번이야?’를 시전하질 않나.. 게다가 문제 이름 맨 뒤에 붙은 Easy도 Hard 버전이 따로 있는게 아니라 진짜 말그대로 쉽다는 의미로 붙은거더군요. 후… 정작 답을 떠올리고 나니 간단한게 맞아서 더더욱 열받는 문제였습니다.

　첫 번째 관찰은 포화이진트리가 주어지기 때문에, 트리의 높이는 최대 \( \log N \)이라는 점입니다. 즉, 직사각형의 두 (가로) 변의 모든 가능한 높이 쌍에 대해 최대 누적합을 매번 \( O(N) \)에 구하는 것으로, \( O(N \log^2{N}) \)에 해결할 수 있게 됩니다. 이것만으로도 이 문제를 충분히 해결할 수 있습니다.

　다만, 볼 필요가 없는 몇몇 노드를 생략하는 방법으로 시간복잡도를 \( O(N \log N) \)으로 줄일 수 있습니다. 예를 들어 직사각령의 아래쪽 가로변의 높이를 2로 설정했다면, 높이가 1인 노드의 개수가 \( \frac {N}{2}\)이므로, 전체의 절반에 해당하는 노드만 봐도 됩니다. 또한, 높이를 3으로 설정했다면, 높이가 2인 노드의 개수 또한 남은 노드 수의 절반이므로, 봐야하는 노드 수가 또 절반으로 줄어듭니다. 이런 식으로 봐야할 노드 수를 줄이면, 시간복잡도는 \( O(N \log N + \frac {N}{2} \log N + \frac {N}{4} \log N \ldots) = O(2N \log N) = O(N \log N) \)이 된다는 것을 알 수 있습니다.

　코드 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

#include<cstdio>
#include<vector>
#include<algorithm>
#define inf ((ll)2e9)

using namespace std;
using ll=long long;
using pll=pair<ll,ll>;

ll arr[300000];
vector<pll> v;

void inorder(int idx,int d,int n){
    if(idx>n/2){
        v.push_back({d,arr[idx]});
        return;
    }
    inorder(idx*2,d-1,n);
    v.push_back({d,arr[idx]});
    inorder(idx*2+1,d-1,n);
}

int main(){
    int n,k=0,tmp;
    ll mx=-inf,ans=0,cur;
    scanf("%d",&n);
    tmp=n;
    while(tmp){
        ++k;
        tmp>>=1;
    }
    for(int i=1;i<=n;++i)scanf("%lld",arr+i),mx=max(mx,arr[i]);
    if(mx<=0){
        printf("%lld",mx);
        return 0;
    }
    inorder(1,k-1,n);
    for(int i=0;i<k;++i){
        for(int j=i;j<k;++j){
            cur=0;
            for(int l=(1<<i)-1;l<n;l+=(1<<i)){
                if(v[l].first<=j){
                    cur+=v[l].second;
                    ans=max(ans,cur);
                    if(cur<0)cur=0;
                }
            }
        }
    }
    printf("%lld",ans);
}

　이로써 풀지 못했던 class 7의 모든 문제에 대한 풀이글 작성을 마쳤습니다. 이제 class 8++ 등반을 시작할 예정이긴 한데, 문제 하나하나가 다 쉽지 않아서 지금처럼 문제 여러개를 한 번에 올리는 게 아니라, 하나씩 따로따로 올리게 될 것 같습니다. 그러면 class 8++ 등반하기 시리즈에서 뵙도록 하겠습니다 :)