solved.ac class 7++ 도전기 3

작성일 | In

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

　다시 class 7++ 등반으로 돌아왔습니다! 사실 오늘 포스팅 할 문제들은 거의 1주일 전에 푼 건데 이제서야 글을 쓰네요. 오늘은 class 7 문제중 4문제를 90분 안에 푸는 것을 목표로 했으며, 문제 목록은 다음과 같습니다.

　A. BOJ 1671 - 상어의 저녁식사
　B. BOJ 2316 - 도시 왕복하기 2
　C. BOJ 2673 - 교차하지 않는 원의 현들의 최대집합
　D. BOJ 2912 - 백설공주와 난쟁이

　A. BOJ 1671 - 상어의 저녁식사 (Solved at 16 min)

　티어: 플래티넘 III

　플로우 느낌이 물씬 나는 문제입니다. 그래프 모델링을 다음과 같이 하면 플로우로 풀 수 있습니다.

github

  1. 정점
    • S: Source, 즉 시작 정점입니다.
    • T: Sink, 즉 끝 정점입니다.
    • 상어 한마리를 나타내는 정점이 2개입니다.
      • 1A와 1B는 각각 상어 1을 나타내고, 2A와 2B는 각각 상어 2를 나타냅니다.
  2. 간선
    • 빨간색 간선
      • Source와 모든 상어 A정점을 연결합니다.
      • 모든 상어는 최대 한 번 잡아먹힐 수 있으므로, capacity는 1입니다.
    • 초록색 간선
      • 상어 i번의 크기, 속도, 지능이 상어 j번의 크기, 속도, 지능보다 작거나 같다면, 상어 i번의 A정점과 상어 j번의 B정점을 연결합니다.
      • 마찬가지로 상어는 최대 한 번 잡아먹힐 수 있으므로, capacity는 1입니다.
    • 파란색 간선
      • 모든 상어 B정점과 Sink를 연결합니다.
      • 모든 상어는 최대 두 마리의 상어를 잡아먹을 수 있으므로, capacity는 2입니다.

　다만, 이대로 두면, 크기, 속도, 지능이 같은 상어끼리 서로 잡아먹는 문제가 생깁니다. 따라서 이러한 상어들끼리는 우선순위를 임의로 부여하고, 우선순위가 큰 상어만 우선순위가 작은 상어를 잡아먹을 수 있도록 합니다. 이에 따라, 초록색 간선의 정의를 다음과 같이 수정합니다.

  • 초록색 간선
    • 상어 i번의 크기, 속도, 지능, 우선순위가 상어 j번의 크기, 속도, 지능, 우선순위보다 작거나 같다면, 상어 i번의 A정점과 상어 j번의 B정점을 연결합니다.
    • 마찬가지로 상어는 최대 한 번 잡아먹힐 수 있으므로, capacity는 1입니다.

　그래프 모델링을 다음과 같이 하면 무난하게 AC를 받을 수 있습니다.

　코드 
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
99
100
101
102

#include<cstdio>
#include<memory.h>
#include<vector>
#include<queue>
#include<map>
#include<tuple>
#include<algorithm>
#define SHARK 50
#define S 0
#define T 101

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

struct shark{
    int a,b,c,p;
    bool operator<(shark& other){
        if(tie(a,b,c)==tie(other.a,other.b,other.c)){
            return p<other.p;
        }
        else if(a<=other.a&&b<=other.b&&c<=other.c)return true;
        return false;
    }
};

shark arr[60];
struct edge{int pos,cap,rev;};
vector<edge> graph[110];
map<info,int> m;

void clear(){for(int i=0;i<110;++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[110],pnt[110];
bool bfs(int src,int sink){
    memset(dist,0,sizeof(dist));
    memset(pnt,0,sizeof(pnt));
    queue<int> q;
    q.push(src);
    dist[src]=1;
    while(q.size()){
        int x=q.front();
        q.pop();
        for(auto& i:graph[x]){
            if(i.cap>0&&!dist[i.pos]){
                dist[i.pos]=dist[x]+1;
                q.push(i.pos);
            }
        }
    }
    return dist[sink]>0;
}

int dfs(int x,int sink,int f){
    if(x==sink)return f;
    for(;pnt[x]<graph[x].size();++pnt[x]){
        edge e=graph[x][pnt[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][pnt[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,2e9))ret+=r;
    }
    return ret;
}

int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        add_edge(S,i,1);
        add_edge(SHARK+i,T,2);
        scanf("%d %d %d",&arr[i].a,&arr[i].b,&arr[i].c);
        arr[i].p=++m[{arr[i].a,{arr[i].b,arr[i].c}}];
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            if(i==j)continue;
            if(arr[i]<arr[j])add_edge(i,SHARK+j,1);
        }
    }
    printf("%lld",n-match(S,T));
}

　B. BOJ 2316 - 도시 왕복하기 2 (Solved at 25 min)

　티어: 플래티넘 III

　이 문제도 플로우입니다. 모델링은 다음과 같습니다.

github

  1. 정점
    • S: Source
    • T: Sink
    • 도시 하나를 나타내는 정점이 2개입니다.
      • 1A와 1B는 각각 도시 1을 나타내고, 2A와 2B는 각각 도시 2를 나타냅니다.
  2. 간선
    • 빨간색 간선
      • Source와 모든 1번 도시의 A정점을 연결합니다.
      • 경로가 있는 한, 계속 왕복할 수 있으므로, capacity는 inf입니다.
    • 초록색 간선
      • 모든 도시의 A정점과 B정점을 연결합니다.
      • 1번 도시와 2번 도시는 제한이 없으므로 capacity는 inf, 나머지 도시는 한 번만 방문할 수 있으므로 capacity는 1입니다.
    • 초록색 간선
      • 2번 도시의 B정점과 Sink를 연결합니다.
      • 경로가 있는 한, 계속 왕복할 수 있으므로, capacity는 inf입니다.
    • 보라색 간선
      • 입력으로 주어진 그래프의 간선입니다. (그림의 난잡함을 방지하기 위해, 입력으로 주어진 간선들 중 하나만 표현했습니다.)
      • ‘1 3’이 주어진 경우, 3번 도시의 B정점과 1번 도시의 A정점을 연결하고, 1번 도시의 B정점과 3번 도시의 A정점을 연결하는 식입니다.

　이렇게 모델링하면 이 문제도 무난하게 AC를 받을 수 있습니다. 다만 저는 간선 양방향인거 고려 안해서 한번 틀렸네요 ㅋㅋ;;

　코드 
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

#include<cstdio>
#include<memory.h>
#include<vector>
#include<queue>
#include<map>
#include<tuple>
#include<algorithm>
#define inf ((int)2e9)
#define S 0
#define T 801
#define OFFSET 400

using namespace std;
using ll=long long;

struct edge{int pos,cap,rev;};
vector<edge> graph[810];

void clear(){for(int i=0;i<810;++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[810],pnt[810];
bool bfs(int src,int sink){
    memset(dist,0,sizeof(dist));
    memset(pnt,0,sizeof(pnt));
    queue<int> q;
    q.push(src);
    dist[src]=1;
    while(q.size()){
        int x=q.front();
        q.pop();
        for(auto& i:graph[x]){
            if(i.cap>0&&!dist[i.pos]){
                dist[i.pos]=dist[x]+1;
                q.push(i.pos);
            }
        }
    }
    return dist[sink]>0;
}

int dfs(int x,int sink,int f){
    if(x==sink)return f;
    for(;pnt[x]<graph[x].size();++pnt[x]){
        edge e=graph[x][pnt[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][pnt[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 n,m,s,e;
    scanf("%d %d",&n,&m);
    add_edge(S,1,inf);
    add_edge(OFFSET+2,T,inf);
    add_edge(1,OFFSET+1,inf);
    add_edge(2,OFFSET+2,inf);
    for(int i=3;i<=n;++i)add_edge(i,OFFSET+i,1);
    for(int i=0;i<m;++i){
        scanf("%d %d",&s,&e);
        add_edge(OFFSET+s,e,1);
        add_edge(OFFSET+e,s,1);
    }
    printf("%lld",match(S,T));
}

　C. BOJ 2673 - 교차하지 않는 원의 현들의 최대집합 (Solved at 43 min)

　티어: 플래티넘 IV

　우선 \( arr[i][j] \)는 현의 양끝점이 각각 i, j인 현이 있으면 1, 없으면 0으로 정의하고, \( dp[i][j] \)를 i번 점부터 j번 점 사이에 서로 교차하지 않는 현들의 최대 개수로 정의합니다. 이렇게 두면, \( dp[i][j] \)를 다음과 같이 구할 수 있습니다. (이때, 모든 인덱스에 mod 100을 취해줍니다.)

  1. \( arr[i][j]=1 \)인 경우
    • \( dp[i][j]=dp[i+1][j-1]+1 \)
      • \( dp[i-1][j]\)와 \( dp[i][j-1] \) 모두 \( dp[i+1][j-1] \)와 최대 1까지밖에 차이가 나지 않기 때문에 정당합니다.
  2. \( arr[i][j]=0 \)인 경우
    • \( dp[i][j]=\max_{i \le k < j} dp[i][k]+ dp[k+1][j] \)

　\(j-i\)가 1일때부터 100일때까지 위와 같은 방식으로 구하고, \( dp[0][99], dp[1][0], \ldots ,dp[99][98] \) 중 최댓값을 출력하면 \( O(N^3) \)에 문제를 해결할 수 있습니다.

　코드 
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
#include<cstdio>
#include<algorithm>

using namespace std;

int arr[110][110];
int dp[110][110];

int main(){
    int n,s,e,ans=0;
    scanf("%d",&n);
    for(int i=0;i<n;++i){
        scanf("%d %d",&s,&e);
        arr[s-1][e-1]=arr[e-1][s-1]=1;
    }
    for(int i=0;i<100;++i)dp[i][(i+1)%100]=arr[i][(i+1)%100];
    for(int i=2;i<100;++i){
        for(int j=0;j<100;++j){
            for(int k=0;k<i;++k)
                dp[j][(j+i)%100]=max(dp[j][(j+i)%100],dp[j][(j+k)%100]+dp[(j+k+1)%100][(j+i)%100]);
            dp[j][(j+i)%100]=max(dp[j][(j+i)%100],dp[(j+1)%100][(j+i-1)%100]+arr[j][(j+i)%100]);
        }
    }
    for(int i=0;i<100;++i)ans=max(ans,dp[(i+1)%100][i]);
    printf("%d",ans);
}

　D. BOJ 2912 - 백설공주와 난쟁이 (Not Solved)

　티어: 플래티넘 III

　구간 내에 가장 많이 등장한 색상이 총 몇 번 등장했는지는 Mo’s로 풀 수 있음이 잘 알려져 있습니다. 관련 문제도 있고요. 그런데 문제는 가장 많이 등장한 색상이 어떤 색상인지도 구해야 한다는 것이었습니다.

　이문제를 \( O(M \sqrt N) \)에 풀 생각을 하느라 결국 시간내에 못 풀었고, 시간 끝나고 고민하면서도 \( O( M \sqrt N \log C) \)풀이를 1초에 욱여넣으려다 TLE가 나기도 했는데… 이 부분은 각 색깔이 몇 번 등장했는지를 저장해 두고, 쿼리가 끝날 때마다 각 색깔이 몇 번 등장했는지 일일히 세주면 \( O(MC) \)에 해결할 수 있고, Mo’s가 \( O(M \sqrt N) \)이므로, \( O(M \sqrt N +MC) \)에 문제를 해결할 수 있습니다.

　+이외에도 머지 소트 트리 + 랜덤을 이용한 풀이가 있는 것 같습니다.

　코드 
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
#include<cstdio>
#include<cmath>
#include<algorithm>

using namespace std;

struct Q{int l,r,idx;};
Q query[10010];
int ans[10010];
int aidx[10010];
int cnt[10010],arr[300010];
int ret;
inline void f(int idx, bool add){
    if(add)++cnt[arr[idx]];
    else --cnt[arr[idx]];
}
void MO(int n, int q,int c){
    int rt=(int)sqrt(n);
    sort(query,query+q,[=](auto& x,auto& y){
        if(x.r/rt!=y.r/rt) return x.r/rt < y.r/rt;
        return x.l<y.l;
    });
    int l=1,r=0;
    for(int i=0;i<q;++i){
        while(query[i].l<l) f(--l,true);
        while(query[i].r>r) f(++r,true);
        while(query[i].l>l) f(l++,false);
        while(query[i].r<r) f(r--,false);
        for(int j=1;j<=c;++j){
            if(cnt[j]>(query[i].r-query[i].l+1)/2){
                ans[query[i].idx]=1;
                aidx[query[i].idx]=j;
                break;
            }
        }
    }
}

int main(){
    int n,c,q;
    scanf("%d %d",&n,&c);
    for(int i=1;i<=n;++i)scanf("%d",arr+i);
    scanf("%d",&q);
    for(int i=0;i<q;++i)scanf("%d %d",&query[i].l,&query[i].r),query[i].idx=i;
    MO(n,q,c);
    for(int i=0;i<q;++i){
        if(ans[i])printf("yes %d\n",aidx[i]);
        else printf("no\n");
    }
}