solved.ac class 7++ 도전기 4

작성일 | In

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

　오랜만에 class 7++ 등반으로 찾아왔습니다! 오늘 포스팅할 문제들은 사실 이미 거의 한달 전에 푼 것들인데 이제야 올리네요. 블로그주인 일해라 ICPC 예선 전후로 좀 정신없었어서 클래스 7++등반에 신경을 못 썼었는데 이제 다시 등반을 시작해볼까 합니다.

　클래스 7 문제 5개를 120분 안에 푸는 것을 목표로 했으며, 문제 목록은 다음과 같습니다.

　A. BOJ 3640 - 제독
　B. BOJ 10266 - 시계 사진들
　C. BOJ 10277 - JuQueen
　D. BOJ 14572 - 스터디 그룹
　E. BOJ 16404 - 주식회사 승범이네

　A. BOJ 3640 - 제독 (Solved at 13 min)

　티어: 플래티넘 II

　그래프 모델링은 solved.ac class 7++ 도전기 3에서 설명한 ‘도시 왕복하기 2’ 문제와 동일합니다. 다만 디테일한 부분에서 다음과 같은 사소한 차이가 있습니다.

  1. 목적지가 고정되어있지 않다. (도시 왕복하기 2에서는 2번 정점으로 고정)
  2. 출발지와 도착지에서의 초록 간선의 유량은 2이다. (도시 왕복하기 2에서는 inf)
    • 몇 번 왕복할 수 있는지를 계산하는 도시 왕복하기 2와 다르게, 이 문제에서는 두 전함이 목적지까지 딱 한번만 가기 때문입니다.
  3. 간선에 cost가 존재한다.
    • 이로 인해 이 문제에서는 단순 flow가 아닌 MCMF를 사용해야 합니다.
　코드 
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

#include<cstdio>
#include<memory.h>
#include<vector>
#include<queue>
#include<algorithm>
#define S 0
#define T 2001
#define VERTEX 1000
#define N 2010

using namespace std;

struct edge{int pos,cap,rev,cost;};
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,int c){
    graph[s].push_back({e,x,(int)graph[e].size(),c});
    graph[e].push_back({s,0,(int)graph[s].size()-1,-c});
}

int dist[N],pa[N],pe[N];
bool inq[N];

bool spfa(int src,int sink){
    memset(dist,0x3f,sizeof(dist));
    memset(inq,0,sizeof(inq));
    queue<int> q;
    dist[src]=0;
    inq[src]=1;
    q.push(src);
    bool ok=0;
    while(q.size()){
        int x=q.front();
        q.pop();
        if(x==sink)ok=1;
        inq[x]=0;
        for(int i=0;i<graph[x].size();++i){
            edge e=graph[x][i];
            if(e.cap>0&&dist[e.pos]>dist[x]+e.cost){
                dist[e.pos]=dist[x]+e.cost;
                pa[e.pos]=x;
                pe[e.pos]=i;
                if(!inq[e.pos]){
                    inq[e.pos]=1;
                    q.push(e.pos);
                }
            }
        }
    }
    return ok;
}

int match(int src,int sink){
    int ret=0;
    while(spfa(src,sink)){
        int cap=1e9;
        for(int pos=sink;pos!=src;pos=pa[pos]){
            cap=min(cap,graph[pa[pos]][pe[pos]].cap);
        }
        ret+=dist[sink]*cap;
        for(int pos=sink;pos!=src;pos=pa[pos]){
            int rev=graph[pa[pos]][pe[pos]].rev;
            graph[pa[pos]][pe[pos]].cap-=cap;
            graph[pos][rev].cap+=cap;
        }
    }
    return ret;
}

int main(){
    int v,e,a,b,c;
    while(scanf("%d %d",&v,&e)!=EOF){
        clear();
        add_edge(S,1,2,0);
        add_edge(VERTEX+v,T,2,0);
        for(int i=1;i<=v;++i){
            if(i==1||i==v)add_edge(i,VERTEX+i,2,0);
            else add_edge(i,VERTEX+i,1,0);
        }
        for(int i=0;i<e;++i){
            scanf("%d %d %d",&a,&b,&c);
            add_edge(VERTEX+a,b,1,c);
        }
        printf("%d\n",match(S,T));
    }
}

　D. BOJ 14572 - 스터디 그룹 (Solved at 59 min)

　티어: 플래티넘 V

　그룹원이 늘어날수록 그룹원 수와 그룹 내의 학생들이 아는 모든 알고리즘의 수는 증가하는 반면, 그룹 내의 모든 학생들이 아는 알고리즘 수는 감소합니다. 즉, 그룹원이 늘어날수록, 효율성 \( E \)는 좋아지기만 한다는 것을 알 수 있고, 이는 그리디 알고리즘을 사용하기 적절한 상황입니다.

　하지만 그룹 내에서 가장 잘 하는 학생과 가장 못하는 학생의 실력차가 \( D \) 이하여야 한다는 조건 때문에, 모든 학생을 다 그룹원으로 받아들일 순 없습니다. 대신 이 조건을 추가해도 그룹원이 늘어날수록 효율성이 좋아진다는 성질은 여전하기 때문에, 각 학생의 실력 \( d_i \)에 대해 실력이 \( d_i \)이상 \( d_i+D \)이하인 학생을 모두 그룹원으로 받아들였을 때의 효율성을 구하고, 이중 최댓값을 취하면 됩니다.

　물론 효율성을 그냥 구하면 시간복잡도가 \( O(N^2) \)이 돼서 터지기 때문에, 학생들을 \( d_i \)에 대한 오름차순으로 정렬한 후, 투 포인터를 사용하면 \( O(N \log N+KN) \)에 문제를 해결할 수 있습니다. 이때 \( K \)가 붙은 이유는 각 구간에 대해, 그룹 내에 모든 학생들이 알고 있는 알고리즘 수는 \( O(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

#include<cstdio>
#include<queue>
#include<algorithm>

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

struct Node{
    int d;
    vector<int> v;
    bool operator<(Node& other){return d<other.d;}
};

priority_queue<pii,vector<pii>,greater<>> pq;
Node arr[100010];
int cnt[40];

int main(){
    int n,k,d,m,tmp,pos=0,ans=0;
    scanf("%d %d %d",&n,&k,&d);
    for(int i=0;i<n;++i){
        scanf("%d %d",&m,&arr[i].d);
        for(int j=0;j<m;++j){
            scanf("%d",&tmp);
            arr[i].v.push_back(tmp);
        }
    }
    sort(arr,arr+n);
    for(int i=0;i<n;++i){
        while(pos<i&&arr[i].d-arr[pos].d>d){
            for(auto j:arr[pos].v)--cnt[j];
            ++pos;
        }
        for(auto j:arr[i].v)++cnt[j];
        int a=0;
        for(int j=1;j<=k;++j)if(cnt[j]&&cnt[j]<=i-pos)++a;
        ans=max(ans,a*(i-pos+1));
    }
    printf("%d",ans);
}

　E. BOJ 16404 - 주식회사 승범이네 (Solved at 98 min)

　티어: 플래티넘 III

　우선 판매원을 정점, 사수-부사수 관계를 간선으로 보고, 사수 정점을 부사수 정점의 부모 정점으로 나타냈을 때, 1번 정점이 루트인 트리를 형성함을 알 수 있습니다. 그리고 1번 쿼리가 수행됐을 때, \( i \)번 직원이 \( w \)만큼 이익/손해를 봤을때, ‘subtree’(부사수)에 속하는 정점들도 똑같이 \( w \)만큼 이익/손해를 보는 형태인데, 이는 오일러 경로 테크닉을 사용하기 좋은 형태입니다.

　오일러 경로 테크닉을 사용하면 1번 쿼리를 세그먼트 트리의 구간 쿼리로, 2번 쿼리를 점 쿼리로 변환할 수 있고, 이는 레이지 세그를 사용하여 풀 수 있습니다. 레이지 안 쓰는 풀이도 있는데 이건 나중에 추가하도록 하겠습니다.

　코드 
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<vector>
#include<algorithm>
#define N (1<<17)
#define cur seg[pos]
#define left seg[pos*2]
#define right seg[pos*2+1]

using namespace std;
using ll=long long;

struct Node{
    int s,e;
    vector<int> v;
};

struct Seg{
    int s,e;
    ll lazy,sum;
};

int n,cnt;
Node arr[100010];
Seg seg[N<<1];

void lazy(int pos){
    if(cur.s!=cur.e&&cur.lazy){
        for(auto i:{pos*2,pos*2+1}){
            seg[i].lazy+=cur.lazy;
            seg[i].sum+=cur.lazy*(left.e-left.s+1);
        }
        cur.lazy=0;
    }
}

void update(int pos,int s,int e,ll val){
    lazy(pos);
    if(cur.s>e||s>cur.e)return;
    if(cur.s>=s&&e>=cur.e){
        cur.lazy+=val;
        cur.sum+=val*(cur.e-cur.s+1);
        lazy(pos);
        return;
    }
    update(pos*2,s,e,val);
    update(pos*2+1,s,e,val);
    cur.sum=left.sum+right.sum;
}

ll query(int pos,int idx){
    lazy(pos);
    if(cur.s>idx||idx>cur.e)return 0;
    if(cur.s==cur.e)return cur.sum;
    return query(pos*2,idx)+query(pos*2+1,idx);
}

int dfs(int idx){
    arr[idx].s=arr[idx].e=++cnt;
    for(auto i:arr[idx].v)arr[idx].e=dfs(i);
    return arr[idx].e;
}

int main(){
    int n,m,s,a,b,c;
    scanf("%d %d",&n,&m);
    scanf("%*d");
    for(int i=2;i<=n;++i){
        scanf("%d",&s);
        arr[s].v.push_back(i);
    }
    dfs(1);
    for(int pos=N;pos<2*N;++pos)cur.s=cur.e=pos-N+1;
    for(int pos=N-1;pos;--pos)cur.s=left.s,cur.e=right.e;
    for(int i=0;i<m;++i){
        scanf("%d",&a);
        if(a==1){
            scanf("%d %d",&b,&c);
            update(1,arr[b].s,arr[b].e,c);
        }
        else{
            scanf("%d",&b);
            printf("%lld\n",query(1,arr[b].s));
        }
    }
}

　C. BOJ 10277 - JuQueen (Solved at 118 min)

　티어: 플래티넘 II

　평범한 구간 쿼리 세그문제인데, groupchange 쿼리나 change 쿼리 수행도중 어떤 core의 frequency값이 0 미만이나 \( N \) 초과가 되면 즉시 해당 쿼리를 중단한다는 점이 유일한 차이입니다.

　해결 방법은 간단합니다. groupchange/change 쿼리를 하기에 앞서, \( S \)값(change 쿼리의 경우 \( X \)값)이 양수이면 구간 내에서 가장 큰 값, 음수이면 구간 내에서 가장 작은 값을 찾습니다. \( S \)이 음수든 양수든 로직은 동일하기 때문에 양수라고 가정하고, 이때 구간 내의 최댓값을 \( M \)이라고 하겠습니다. \( M+S \le N\)이라면 주어진 구간에 S를 그대로 더하고, \( M+S > N \)이라면 주어진 구간에 \( N-M \)을 더하면 됩니다.

　구간 쿼리니까 레이지 세그를 사용하셔도 되고, 위의 ‘주식회사 승범이네’ 문제와 마찬가지로 레이지 없이 푸는 방법도 있습니다.

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

#include<iostream>
#include<string>
#include<algorithm>
#define N (1<<23)
#define inf 1e9
#define cur seg[pos]
#define left seg[pos*2]
#define right seg[pos*2+1]
#define fastio() ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)

using namespace std;

struct Node{
    int s,e,m,M,lazy;
};

Node seg[N<<1];

void lazy(int pos){
    if(cur.s!=cur.e&&cur.lazy){
        for(auto i:{pos*2,pos*2+1}){
            seg[i].lazy+=cur.lazy;
            seg[i].m+=cur.lazy;
            seg[i].M+=cur.lazy;
        }
        cur.lazy=0;
    }
}

void update(int pos,int s,int e,int val){
    lazy(pos);
    if(cur.s>e||s>cur.e)return;
    if(cur.s>=s&&e>=cur.e){
        cur.lazy+=val;
        cur.m+=val;
        cur.M+=val;
        lazy(pos);
        return;
    }
    update(pos*2,s,e,val);
    update(pos*2+1,s,e,val);
    cur.m=min(left.m,right.m);
    cur.M=max(left.M,right.M);
}

int query(int pos,int s,int e,bool flag){
    lazy(pos);
    if(cur.s>e||s>cur.e)return flag?-inf:inf;
    if(cur.s>=s&&e>=cur.e)return flag?cur.M:cur.m;
    return flag?max(query(pos*2,s,e,flag),query(pos*2+1,s,e,flag)):
        min(query(pos*2,s,e,flag),query(pos*2+1,s,e,flag));
}

int main(){
    fastio();
    int c,n,o,st,ed,val;
    string s;
    cin>>c>>n>>o;
    for(int pos=N;pos<N*2;++pos)cur.s=cur.e=pos-N;
    for(int pos=N-1;pos;--pos)cur.s=left.s,cur.e=right.e;
    for(int i=0;i<o;++i){
        cin>>s;
        if(s[0]=='s'){
            cin>>val;
            cout<<query(1,val,val,1)<<"\n";
        }
        else if(s[0]=='g'){
            cin>>st>>ed>>val;
            if(!val){
                cout<<"0\n";
                continue;
            }
            if(val>0)val=min(val,n-query(1,st,ed,1));
            else val=max(val,-query(1,st,ed,0));
            cout<<val<<"\n";
            update(1,st,ed,val);
        }
        else{
            cin>>st>>val;
            if(!val){
                cout<<"0\n";
                continue;
            }
            if(val>0)val=min(val,n-query(1,st,st,1));
            else val=max(val,-query(1,st,st,0));
            cout<<val<<"\n";
            update(1,st,st,val);
        }
    }
}

　B. BOJ 10266 - 시계 사진들 (WA 1회, TLE 1회)

　티어: 플래티넘 V

　우선 시계 바늘의 각도가 0 이상 359,999 이하의 정수로 정의되기 때문에, 우리는 두 시계 사진을 길이 360,000의 문자열로 나타낼 수 있습니다. 이때 각도가 \( i \)인 시계 바늘이 존재한다면 문자열의 \( i \)번 인덱스는 1, 아니라면 0입니다. 이렇게 시계를 문자열로 변환하고 나면, 두 문자열이 아래 사진과 같이 매칭되는지를 확인하면 됩니다.

github

　우선 1번 시계를 나타내는 문자열을 문자열 \( A \)(위), 2번 시계를 나타내는 문자열을 문자열 \( B \)(아래)라고 하겠습니다. 이때 위 사진에서 생략된 정의는 다음과 같습니다.

  1. 문자열 \( A \)의 suffix가 문자열 \( B \)의 prefix가 길이 \( d_1 \)만큼 일치한다. (위 사진의 빨간색 영역)
  2. 문자열 \( A \)의 prefix가 문자열 \( B \)의 suffix가 길이 \( d_2 \)만큼 일치한다. (위 사진의 파란색 영역)
  3. \( d_1+d_2 = N \)(문자열의 길이)이다.

　여기서 \( d_1 \)은 KMP를 돌리면 찾을 수 있고, 문자열 \( B \)의 \( d_1 \)번째 인덱스부터 \( N-1 \)번째 인덱스가 문자열 \( A \)의 \( 0 \)번째 인덱스부터 \( N-d_1-1 \)번째 인덱스까지 일치하는지 확인하면 2번, 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
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

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

using namespace std;

string s,t;
int n;
int p[360010],q[360010];
int a[360010],b[360010];
int arr[200010],brr[200010];

void init(){
    n=360000;
    for(int i=1,j=0;i<n;++i){
        while(j>0&&s[i]!=s[j])j=p[j-1];
        if(s[i]==s[j])p[i]=++j;
    }
    for(int i=1,j=0;i<n;++i){
        while(j>0&&t[i]!=t[j])j=q[j-1];
        if(t[i]==t[j])q[i]=++j;
    }
}

bool solve(){
    for(int i=0,j=0;i<n;++i){
        while(j>0&&t[i]!=s[j])j=p[j-1];
        if(t[i]==s[j])++j;
        a[i]=j;
    }
    for(int i=a[n-1],j=0;i<n;++i,++j)if(s[i]!=t[j])return false;
    return true;
}

int main(){
    fastio();
    int pos=0;
    cin>>n;
    for(int i=0;i<n;++i)cin>>arr[i];
    for(int i=0;i<n;++i)cin>>brr[i];
    sort(arr,arr+n);sort(brr,brr+n);
    s="";t="";
    for(int i=0;i<360000;++i){
        if(pos<n&&arr[pos]==i)s+="1",++pos;
        else s+="0";
    }
    pos=0;
    for(int i=0;i<360000;++i){
        if(pos<n&&brr[pos]==i)t+="1",++pos;
        else t+="0";
    }
    init();
    if(solve())cout<<"possible";
    else cout<<"impossible";
}

　이제 class 7++까지 4문제 남았는데.. 여태까지는 class 7 문제들 중 풀이가 떠오른 문제들을 골라서 시간 재고 풀었는데, 남은 문제들은 거의 다 충분히 생각해도 풀이가 안 떠오르는 문제들이다 보니 이 문제들은 따로 시간을 재고 풀지는 않을 것 같네요. 빠른 시일내에 class 7++ 등반을 끝내고 class 8++ 등반으로 찾아뵙겠습니다!