solved.ac class 7++ 도전기 1

작성일 | In

　어제 class 6++ 달성한 데에 이어, 바로 class 7++ 달성에 도전합니다. 어제는 회전하는 캘리퍼스 기본문제인 고속도로와 스프라그-그런디 정리 기본문제인 다각형 게임을 풀긴 했지만, 그 외에 풀이는 알지만 ‘구현이 귀찮아서’ 구현을 나중으로 미루게 된 문제가 다수 속출하자, 오늘부터 class 문제는 시간을 재고 풀기로 했습니다.

　오늘은 아직 안 푼 class 7문제 중 풀이를 아는 문제 4개를 골라, 125분 안에 모두 해결하는 것을 목표로 했습니다.. 만 중간에 점심먹으러 탈주하는 바람에 사실상 80분정도만 한 것 같습니다. 아무튼 오늘의 문제 목록은 다음과 같습니다.

　A. BOJ 1648 - 격자판 채우기
　B. BOJ 3878 - 점 분리
　C. BOJ 8462 - 배열의 힘
　D. BOJ 11405 - 책 구매하기

　A. BOJ 1648 - 격자판 채우기 (Solved at 22 min)

　티어: 플래티넘 III

　매 열마다 2x1 크기의 도미노를 먼저 배치한 후, 그 뒤에 1x2 크기의 도미노를 배치한다고 생각해봅시다. 이때 i번째 열의 2x1 도미노 배치가 완료된 후에도 i번 째 열의 j번째 행에 도미노가 배치가 안 되어 있다면, i행 j열과 i+1행 j열에는 반드시 1x2 도미노가 배치되어야 합니다.

　이 점을 이용하여 비트dp를 돌리면 \( O(N 2^{2M}) \) 에 해결이 가능합니다. 사실 N과 M 모두 최대 14라 최악의 경우 연산횟수가 40억까지 갈 수 있을 것처럼 보이지만, 실제로는 2x1 크기의 도미노를 배치하는 경우의 수가 \( 2^M \) 가지에 한참 못미쳐서 통과한 것 같습니다. 실제로 로컬에서도 14 14가 몇 초 안에 돌기도 해서 믿음의 제출을 할 수 있었습니다.

　나중에 확인해본 결과, 한 행이 i칸인 열에 2x1 크기의 도미노를 배치하는 경우의 수는 i+1번째 피보나치 수와 같다는 결론을 얻었고, 15번째 피보나치 수는 610이므로, 시간복잡도는 \( O(610N 2^M) \) 이고, 이렇게 되면 N=M=14일 때 연산횟수가 약 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
#include<cstdio>

const int mod=9901;

int dp[15][20000];

int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=0;i<(1<<(n-1));++i){
        int bit=0;
        bool flag=false;
        for(int j=0;j<n-1;++j){
            if(~i&(1<<j))continue;
            if((bit&(1<<j))||(bit&(1<<(j+1)))){
                flag=true;
                break;
            }
            bit|=(1<<j);
            bit|=(1<<(j+1));
        }
        if(flag)continue;
        dp[1][bit]=1;
    }
    for(int i=1;i<m;++i){
        for(int j=0;j<(1<<n);++j){
            if(!dp[i][j])continue;
            int cbit=((1<<n)-1)^j,nbit;
            for(int k=0;k<(1<<(n-1));++k){
                nbit=cbit;
                bool flag=false;
                for(int l=0;l<n-1;++l){
                    if(~k&(1<<l))continue;
                    if((nbit&(1<<l))||(nbit&(1<<(l+1)))){
                        flag=true;
                        break;
                    }
                    nbit|=(1<<l);
                    nbit|=(1<<(l+1));
                }
                if(flag)continue;
                dp[i+1][nbit]+=dp[i][j];
                dp[i+1][nbit]%=mod;
            }
        }
    }
    printf("%d",dp[m][(1<<n)-1]);
}

　C. BOJ 8462 - 배열의 힘 (Solved at 40 min)

　티어: 플래티넘 II

　간단한 Mo’s 문제라서 제 icpc 팀의 팀노트를 참고해서 풀었습니다. 거의 기본 유형이라 설명은 생략하고 코드만 남기겠습니다.

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

using namespace std;
using ll=long long;

struct Q{
    int l,r,idx;
};

int n,rt,t;
int arr[100010];
ll cnt[1000010];
ll ans[100010],ret;
Q query[100010];

inline void f(int idx,bool add){
    ret-=cnt[arr[idx]]*cnt[arr[idx]]*arr[idx];
    if(add)++cnt[arr[idx]];
    else --cnt[arr[idx]];
    ret+=cnt[arr[idx]]*cnt[arr[idx]]*arr[idx];
}

int main(){
    scanf("%d %d",&n,&t);
    rt=(int)sqrt(n);
    for(int i=1;i<=n;++i)scanf("%d",arr+i);
    for(int i=0;i<t;++i){
        scanf("%d %d",&query[i].l,&query[i].r);
        query[i].idx=i;
    }
    sort(query,query+t,[](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<t;++i){
        while(query[i].l<l)f(--l,1);
        while(query[i].r>r)f(++r,1);
        while(query[i].l>l)f(l++,0);
        while(query[i].r<r)f(r--,0);
        ans[query[i].idx]=ret;
    }
    for(int i=0;i<t;++i)printf("%lld\n",ans[i]);
}

　D. BOJ 11405 - 책 구매하기 (CPE 1회, WA 3회)

　티어: 플래티넘 IV

　이 문제는 간단한 MCMF 문제라서 마찬가지로 제 icpc 팀의 팀노트를 참고해서 풀었는데, 예제부터 오답을 냈습니다. 이거가지고 한참을 고민하다가 예제를 분석해보니, ‘온라인 서점은 책을 한권씩만 택배로 보낸다’를 한 사람당 각 온라인 서점에서 한 권씩만 살 수 있다고 이해해서 생긴 문제였습니다.

　이 부분을 고치고 나니 예제가 잘 나와서 제출했더니, 컴파일 에러가 떴습니다. memset을 거의 사용 안하다시피해서 몰랐는데 memset쓰면 cstring이나 memory.h를 include해줘야 하더군요.. 그래서 해당 부분을 고쳤는데 이번엔 WA가 났습니다. 팀노트 MCMF를 베끼는 과정에서 잘못된 부분이 있었나 확인했는데 그것도 아니라서 한참을 고민하다가 그냥 점심을 먹으러 갔는데, 나중에 돌아와서 보니 main쪽에서 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
93
94
#include<cstdio>
#include<memory.h>
#include<vector>
#include<queue>
#include<algorithm>
#define S 0
#define T 201
#define BOOK 100

using namespace std;

struct edge{
    int pos,cap,rev,cost;
};

vector<edge> graph[210];
int dist[210],pa[210],pe[210];
bool inq[210];

void clear(){
    for(int i=0;i<210;++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});
}

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 n,m,tmp;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%d",&tmp);
        add_edge(BOOK+i,T,tmp,0);
    }
    for(int i=1;i<=m;++i){
        scanf("%d",&tmp);
        add_edge(S,i,tmp,0);
    }
    for(int i=1;i<=m;++i){
        for(int j=1;j<=n;++j){
            scanf("%d",&tmp);
            add_edge(i,BOOK+j,1e9,tmp);
        }
    }
    printf("%d",match(S,T));
}

　B. BOJ 3878 - 점 분리 (Not Solved)

　티어: 플래티넘 I

　대충 검정 점끼리, 흰 점끼리 convex hull을 돌리고, 두 convex hull에 대해 선분 교차 판정을 하기만 하면 되는 문제인 줄 알았는데, n이나 m이 1 경우 볼록다각형 내부의 점 판정을 해야하더군요..

　아직 모르는 알고리즘이라서 이 부분은 따로 공부해서 팀노트에 추가할 예정입니다.

　처음 7++ 도전할때는 24문제 남은 상태였는데, 어제 2문제, 오늘 3문제 해결해서 이제 19문제 남았네요! 앞으로 남은 문제들도 알고리즘을 새로 배워서 풀어야 하는 경우를 제외하고는 오늘처럼 시간 재고 풀어보도록 하겠습니다 :)