gumgood blog
CP Algorithm

COCI 2006/2007 contest #1 개인 풀이

By Sangwon Lee Posted Jan 31, 2019

1. BOJ 2052 나머지

각 나머지에 대해 marking 해놓는다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#include<cstdio>

bool chk[42];

int main(){
    for(int i=0;i<10;++i){
        int t;
        scanf("%d",&t);
        chk[t%42] = true;
    }

    int ans = 0;
    for(int i=0;i<42;++i)
        ans += chk[i];
    printf("%d",ans);
    return 0;
}

2. BOJ 3053 택시 기하학

유클리드 기하에서 원 넓이는 $\pi r^2$, 택시 기하에서의 원 넓이는 $2r^2$ (한 변의 길이가 $\sqrt{2} r$인 정사각형 모양)

1
2
3
4
5
6
7
8
9

#include<stdio.h>
#define PI 3.14159265358979323846
int main()
{
    double r;
    scanf("%lf",&r);
    printf("%lf\n%lf\n",PI*r*r,2*r*r);
    return 0;
}

3. BOJ 3054 피터팬 프라임

단순 구현 문제

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

#include<cstdio>
#include<string>
using namespace std;

string p[5] = {"..#..", ".#.#.", "#...#", ".#.#.", "..#.."};
string w[5] = {"..*..", ".*.*.", "*...*", ".*.*.", "..*.."};

int main(){
    char str[16] = {0};
    scanf("%s",str);

    string ans[5] = {".", ".", "#", ".", "."};
    for(int i=0;str[i];++i){
        if((i+1)%3){
           for(int j=0;j<5;++j)
               for(int k=1;k<5;++k)
                   ans[j].push_back(p[j][k]);
        }else{
            for(int j=0;j<5;++j){
                ans[j].pop_back();
                for(int k=0;k<5;++k)
                    ans[j].push_back(w[j][k]);
            }
        }
        ans[2][4*i+2] = str[i];
    }

    for(int i=0;i<5;++i)
        puts(ans[i].c_str());
    return 0;
}

4. BOJ 3055 탈출

문제를 보고 BFS를 떠올릴 수 있다. 고슴도치는 다음 시간에 물이 찰 예정인 칸으로는 이동할 수 없다. 따라서 BFS과정에서 물이 먼저 움직이고 고슴도치가 움직이면서 탈출할 수 있는지를 체크한다. “먼저 움직인다”라는 것은 BFS에서 queue에 먼저 들어가는 것으로 구현해줄 수 있다.

전체 시간복잡도는 $O(RC)$

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

#include<cstdio>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
typedef pair<int,int> ii;
typedef pair<ii,ii> iiii;
const int dx[] = {0,0,-1,1};
const int dy[] = {-1,1,0,0};

int r, c;
char map[50][51];

int solve(){
    queue<iiii> q;
    int v[50][50] = {0};
    int bx, by, sx, sy;
    for(int i=0;i<r;++i)
        for(int j=0;j<c;++j){
            if(map[i][j]=='D')
                bx = i, by = j;
            else if(map[i][j]=='S')
                sx = i, sy = j;
            else if(map[i][j]=='*')
                q.push(iiii(ii(i,j),ii(0,2))), v[i][j] = 2;
        }
    q.push(iiii(ii(sx,sy),ii(0,1)));
    v[sx][sy] = 1;
    while(!q.empty()){
        int x = q.front().first.first;
        int y = q.front().first.second;
        int t = q.front().second.first;
        int w = q.front().second.second;
        q.pop();
        if(w==1 && x==bx && y==by)
            return t;
        for(int i=0;i<4;++i){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx<0 || nx>=r) continue;
            if(ny<0 || ny>=c) continue;
            if(map[nx][ny]=='X') continue;
            if(map[nx][ny]=='D' && w==2) continue;
            if(v[nx][ny] >= w) continue;
            v[nx][ny] = w;
            q.push(iiii(ii(nx,ny),ii(t+1,w)));
        }
    }
    return -1;
}

int main(){
    scanf("%d%d\n",&r,&c);
    for(int i=0;i<r;++i)
        scanf("%s",map[i]);

    int ans = solve();
    if(ans<0) puts("KAKTUS");
    else printf("%d",ans);

    return 0;
}

5. BOJ 3056 007

Dynamic Programming + Bitmask로 해결할 수 있다.

$0 \sim n-1$번 요원이 순서대로 미션을 할당받는다고 하자. $i-1$번 요원까지 미션을 할당받았을 때, $i$번 요원은 남은 미션들 중 하나를 수행하게 된다. 할당된 임무 목록을 $state$에 bitmasking하면 다음과 같이 정의할 수 있다.

  • $dp[i][state]$ = ($0 \sim i$번 요원까지 할당된 임무 목록이 $state$일 때, 이를 모두 성공적으로 끝낼 확률)

이 때 $i$는 필요없는 정보인 것을 알 수 있는데, $state$의 켜진 bit 수와 같기 때문이다. 즉, $state$만으로 몇 명의 요원까지 미션을 할당받았는지 알 수 있다는 말이다. 다음과 같이 다시 정의하자.

  • $dp[state]$ = (할당된 임무 목록이 $state$일 때, 이를 모두 성공적으로 끝낼 확률 )

이 때, 임무를 하나 더 할당했을 때 $state$가 되는 임무 목록들을 $prev$라고 하자. $state$가 포함하는 미션이 $i$개이고, $j$번 미션을 할당하는 경우, 다음과 같이 계산할 수 있다.

\[dp[state] = \underset{bit \in \forall prev}{\max}(dp[bit] \cdot p[i][j])\] 
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

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

int n;
double p[20][20];

double dp[1<<20];

double solve(){
    for(int i=0;i<n;++i)
        dp[1<<i] = p[0][i];
    for(int i=1;i<n;++i)
        for(int bit=0;bit<(1<<n);++bit){
            int cnt = 0;
            for(int j=bit;j;j/=2)
                cnt += j%2;
            if(cnt!=i) continue;

            for(int j=0;j<n;++j)
                if((bit & (1<<j))==0)
                    dp[bit|(1<<j)] = max(dp[bit|(1<<j)], dp[bit]*p[i][j]);
        }
    return dp[(1<<n)-1];
}

int main(){
    scanf("%d",&n);
    for(int i=0;i<n;++i)
        for(int j=0;j<n;++j){
            scanf("%lf",&p[i][j]);
            p[i][j] /= 100.0f;
        }
    printf("%.9lf",solve()*100.0f);
    return 0;
}

6. BOJ 3057 디버그 / BOJ 1751 디버그

모든 정방행렬에 대해 180도 회전시켜보고 같은지 확인해야 한다. $N = min(R,C)$라하면, 모든 좌표에 대해 대해 정방행렬은 최대 $N$개 존재할 수 있으므로 검사해야 할 정방행렬은 $N^3$개 존재한다. 각 정방행렬을 돌려서 비교하는데 $O(N^2)$으로 합쳐서 $O(N^5)$에 TLE를 받을 수 있다. 정방행렬을 돌려서 확인하는 과정을 최적화시켜보자.

크기가 $k$인 정방행렬이 스퀘어 킬러일 때, 이를 감싸는 테두리가 180도 돌려도 같다면 크기가 $k+2$인 정방행렬이 존재하는 것이다. 즉, 각 정방행렬에 대해 스퀘어 킬렁인지를 저장해두고 테두리만 확인해주면 $O(N)$에 정방행렬인지 판별이 가능하다.

어떤 정방행렬의 가장 아래-오른쪽 원소를 기준으로 dp식을 정의하자.

  • $dp[x][y][k]$ = (가장 아래-오른쪽 원소가 $(x,y)$이고 크기가 $k$인 정방행렬이 스퀘어 킬러이면 true)

테두리를 확인하는 함수를 다음과 같이 정의하면

  • $cmp(i,j,k)$ = ($dp[x][y][k]$에 해당하는 행렬의 테두리가 180도 돌려도 같으면 true)

점화식을 얻을 수 있다.

  • $dp[x][y][k] = dp[x-1][y-1][k-2] \ \And \ cmp(i,j,k)$

이렇게 하면 $O(N^4)$에 해결할 수 있다. 여기서 더 줄일 수도 있는데, 모든 원소는 bool이므로 64bit 자료형에 넣고 bitwise로 비교하면 $O(N^4 / 64)$에 해결할 수 있다.

참고로 3057번과 1751번의 차이는 크기가 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

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;

int r, c, m[300][300];
bool dp[300][300][300];

ll row[300][300], rrow[300][300];
ll col[300][300], rcol[300][300];

bool chk(int x,int y,int size){
    int si = x-size+1, ei = x;
    int sj = y-size+1, ej = y;
    if(si<0 || sj<0) return false;

    int bit;
    for(int k=0;k<size;k+=bit){
        bit = min(60,size-k);
        ll a = (row[si][sj+k] & ((1LL<<bit)-1));
        ll b =(rrow[ei][ej-k] & ((1LL<<bit)-1));
        if(a != b) return false;
        ll c = (col[si+k][sj] & ((1LL<<bit)-1));
        ll d =(rcol[ei-k][ej] & ((1LL<<bit)-1));
        if(c != d) return false;
    }
    return true;
}

int solve(){
    for(int i=r-1;i>=0;--i)
        for(int j=c-1;j>=0;--j){
            if(j==c-1) row[i][j] = m[i][j];
            else row[i][j] = 2LL*row[i][j+1] + m[i][j];
            if(i==r-1) col[i][j] = m[i][j];
            else col[i][j] = 2LL*col[i+1][j] + m[i][j];
        }
    for(int i=0;i<r;++i)
        for(int j=0;j<c;++j){
            if(j==0) rrow[i][j] = m[i][j];
            else rrow[i][j] = 2LL*rrow[i][j-1] + m[i][j];
            if(i==0) rcol[i][j] = m[i][j];
            else rcol[i][j] = 2LL*rcol[i-1][j] + m[i][j];
        }

    int ans = 1;
    int upp = min(r,c);
    for(int i=0;i<r;++i)
        for(int j=0;j<c;++j)
            dp[i][j][0] = dp[i][j][1] = true;
    for(int i=1;i<r;++i)
        for(int j=1;j<c;++j)
            for(int k=2;k<=upp;++k)
                if(dp[i-1][j-1][k-2] && chk(i,j,k)){
                        dp[i][j][k] = true;
                        ans = max(ans, k);
                }
    return ans>1 ? ans : -1;
}

int main(){
    scanf("%d%d",&r,&c);
    for(int i=0;i<r;++i)
        for(int j=0;j<c;++j)
            scanf("%1d",&m[i][j]);
    printf("%d",solve());
}
coci
Recently Updated
Trending Tags
cs231n deep_learning lecture vision coci data_structure python google kickstart programmers
All tags