Gumgood  
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

#include <algorithm>
#include <cstdio>
#include <vector>
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
69
70
71
72
73
74

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