일기형식으로 글을 써보겠습니다.

시간은 일요일 오후 6시.

아침부터 알고리즘 강의를 10~1, 2~5시를 하고나서 저녁도 못먹고 참가하는 대회이고, 졸려 죽겠어서 참가할지 말지 고민을 엄청많이 했지만, 일단 참가를 하기로 결정했다.

배고파죽겠다.

대회는 6시이고 지금 시간은 5:50 일단 밥은 6시부터 먹을 수 있을듯하니, 밥을 먹으면서 문제를 풀면서 대회를 참가해야 겠다.

6시 대회가 시작되었다.

A번 문제를 열었다.

첫 문장을 보니 해리포터랑 볼드모트가 무슨 마법을 서로를 향해서 쏜다는 문제인 것 같은데, 뭔 소린지 읽기가 귀찮아서 힌트를 봤다.

속도가 같으면, 복도 중간에서 만난다는 얘기가 써있었다. 아 이문제는 서로 마법을 쏘는데, 그 마법이 만나는 지점을 구하는 문제라는 것을 알았다.

예제를 보니, 첫 번째 예제 100 50 50은 정답이 50이라 중간인게 분명하고, 두 번째 예제 199 60 40은 119.4라는 절반 100보다 애매하게 큰 수가 나온걸 봐서 6:4 내분하는 점인 것 같다.

일단 코드를 짜보고 틀리면 다시 문제를 읽기로 결정하고 코드를 작성했다.

#include <cstdio>
using namespace std;
int main() {
    double l,p,q;
    scanf("%lf%lf%lf",&l,&p,&q);
    printf("%.10lf\n",l*p/(p+q));
    return 0;
}

맞았다!

이제 B를 읽어보자.

B는 뭔가 사람을 고용해서 뭘 바꾸고 뭘 바꾼다는거 같은데, 내용이 길어서 문제 이해를 못하겠으니 예제를 보기로 결정했다.

매우 상세한 예제 설명이 적혀있다. 설명과 예제를 보니 아! 단어에 적힌 알파벳을 입력으로 주어진 쌍 M개로 알파벳을 서로 교환하는 문제라는 것을 알았다.

일단 코드를 작성했다.

#include <cstdio>
#include <algorithm>
using namespace std;
char w[222];
char s[222222];
char ww[222];
int main() {
    int n,m;
    scanf("%d %d\n",&n,&m);
    scanf("%s\n",s);
    for (int i='a'; i<='z'; i++) {
        w[i] = i;
    }
    for (int i=0; i<m; i++) {
        char x, y;
        scanf("%c %c\n",&x,&y);
        swap(w[x],w[y]);
    }
    for (int i=0; i<n; i++) {
        printf("%c",w[s[i]]);
    }
    puts("");

    return 0;
}

정답이 나오질 않는다 ㅠㅠ 종이에 직접 w배열에 어떤 값이 들어가는지 적어보니 구현을 잘못했다. 아래와 같이 수정해서 맞았다.

#include <cstdio>
#include <algorithm>
using namespace std;
char w[222];
char s[222222];
char ww[222];
int main() {
    int n,m;
    scanf("%d %d\n",&n,&m);
    scanf("%s\n",s);
    for (int i='a'; i<='z'; i++) {
        w[i] = i;
    }
    for (int i=0; i<m; i++) {
        char x, y;
        scanf("%c %c\n",&x,&y);
        int t1,t2;
        for (int k='a'; k<='z'; k++) {
            if (w[k] == x) {
                t1 = k;
            }
            if (w[k] == y) {
                t2 = k;
            }
        }
        swap(w[t1],w[t2]);
    }
    for (int i=0; i<n; i++) {
        printf("%c",w[s[i]]);
    }
    puts("");

    return 0;
}

C번을 읽어보니 어떤 배열을 주어진 규칙에 따라서 새로운 배열 B로 만드는 문제였다.

• B[0] = A[0]
• B[N-1] = A[N-1]
• B[i] = {A[i-1], A[i], A[i+1]}중 많은 값

새로운 배열 B를 만들고, 그 B를 A로 결정하고, A와 B가 같아질 때까지 배열 변경을 계속해서 진행한다.

N이 500,000인데, 한 번 바꾸는걸 처리하는데 총 N번이 걸리고 답의 최대값은 아마도 N정도가 걸릴 것이기 때문에, N^2으로는 시간 초과를 받게 된다.

일단, N이 작은 경우에 대해서 모든 답을 구해보고 규칙을 찾기로 결정했다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int f(int x, int y, int z) {
    vector<int> a = {x,y,z};
    sort(a.begin(),a.end());
    return a[1];
}
void check(int n, int kk) {
    vector<int> a;
    int k = kk;
    for (int i=0; i<n; i++) {
        a.push_back(k%2);
        k/=2;
    }
    reverse(a.begin(),a.end());
    for (int i=0; i<n; i++) {
        printf("%d",a[i]);
    }
    printf(" -> ");
    int step = 0;
    while (true) {
        vector<int> b(n);
        b[0] = a[0];
        b[n-1] = a[n-1];
        for (int i=1; i<n-1; i++) {
            b[i] = f(a[i-1],a[i],a[i+1]);
        }
        bool ch = true;
        for (int i=0; i<n; i++) {
            if (a[i] != b[i]) {
                ch = false;
            }
        }
        if (ch) break;
        a = b;
        step += 1;
        for (int i=0; i<n; i++) {
            printf("%d",a[i]);
        }
        printf(" -> ");
    }
    printf("%d\n",step);
}
int main() {
    int n;
    cin >> n;
    for (int k=0; k<(1<<n); k++) {
        check(n,k);
    }
    return 0;
}

위의 소스는 입력으로 받은 모든 경우에 대해서 답을 구해보기로 했다.

N=3 인 경우의 답을 구해보았다.

답이 바뀌는 경우는 2가지 경우 밖에 없었다.

010 -> 000 -> 1
101 -> 111 -> 1

이제 N = 4일때 답을 구해보았다.

0000 -> 0
0001 -> 0
0010 -> 0000 -> 1
0011 -> 0
0100 -> 0000 -> 1
0101 -> 0011 -> 1
0110 -> 0
0111 -> 0
1000 -> 0
1001 -> 0
1010 -> 1100 -> 1
1011 -> 1111 -> 1
1100 -> 0
1101 -> 1111 -> 1
1110 -> 0
1111 -> 0

쳐다보니 0과 1이 반복해서 3번 이상 나타나면 변화가 시작되는 것 같다.

N = 5일때 답을 구해보았다.

00000 -> 0
00001 -> 0
00010 -> 00000 -> 1
00011 -> 0
00100 -> 00000 -> 1
00101 -> 00011 -> 1
00110 -> 0
00111 -> 0
01000 -> 00000 -> 1
01001 -> 00001 -> 1
01010 -> 00100 -> 00000 -> 2
01011 -> 00111 -> 1
01100 -> 0
01101 -> 01111 -> 1
01110 -> 0
01111 -> 0
10000 -> 0
10001 -> 0
10010 -> 10000 -> 1
10011 -> 0
10100 -> 11000 -> 1
10101 -> 11011 -> 11111 -> 2
10110 -> 11110 -> 1
10111 -> 11111 -> 1
11000 -> 0
11001 -> 0
11010 -> 11100 -> 1
11011 -> 11111 -> 1
11100 -> 0
11101 -> 11111 -> 1
11110 -> 0
11111 -> 0

놀라운 것을 찾아냈다. 01010과 10101을 제외한 나머지 정답은 모두 0 또는 1이다. 그런데, 답이 1번만에 바뀌는 경우는 010, 101, 0101, 1010 가 등장하는 것이었고, 01010은 2번만에 바뀌는 것이었다.

여기서 101 -> 111, 010->000, 1010 -> 1100, 0101 -> 0011 로 변한다는 것을 알았다.

길이가 10101처럼 늘어나면, 101->111과 같이 11111로 변하지만, 횟수가 2번이 된다는 것도 알았다.

변경이 되려면, 길이가 3이상이면서 1과 0이 번갈아 나오는 부분 문자열을 찾아야 하고, 그 길이가 홀수와 짝수에 따라서 바뀌는 방법이 바뀐다.

• 101, 10101과 같이 1로 시작하는 홀수 길이 문자열은 모두 1로 변하게 되고, 변경되는 횟수는 길이/2번이다.
• 010, 01010과 같이 0로 시작하는 홀수 길이 문자열은 모두 0로 변하게 되고, 변경되는 횟수는 길이/2번이다.
• 1010,101010과 같이 1로 시작하는 짝수길이 문자열은 앞의 절반은 1로, 뒤의 절반은 0으로 변경되며, 변경되는 횟수는 길이/2-1번이다.
• 0101,010101과 같이 0로 시작하는 짝수길이 문자열은 앞의 절반은 0로, 뒤의 절반은 1으로 변경되며, 변경되는 횟수는 길이/2-1번이다.

이제 N = 10인 경우를 일부만 프린트해보고 위의 방법이 맞는지 검사해보았다.

1110010100 -> 1110001000 -> 1110000000 -> 2
1110010101 -> 1110001011 -> 1110000111 -> 2
1110010110 -> 1110001110 -> 1
1110010111 -> 1110001111 -> 1
1110011000 -> 0
1110011001 -> 0
1110011010 -> 1110011100 -> 1
1110011011 -> 1110011111 -> 1
1110011100 -> 0
1110011101 -> 1110011111 -> 1
1110011110 -> 0
1110011111 -> 0
1110100000 -> 1111000000 -> 1
1110100001 -> 1111000001 -> 1

맞다!

구현을 해서 제출을 해보자.

#include <cstdio>
using namespace std;
int a[555555];
int b[555555];
int n;
int main() {
    scanf("%d",&n);
    for (int i=0; i<n; i++) {
        scanf("%d",&a[i]);
        b[i]=a[i];
    }
    int l = 0;
    int ans = 0;
    while (l+2 < n) {
        if (a[l] == a[l+2] && a[l] != a[l+1]) {
            int r = l+2;
            while (r+1 < n) {
                if (a[r] != a[r+1]) {
                    r += 1;
                } else {
                    break;
                }
            }
            int len = r-l+1;
            if (len%2==0) {
                int t1 = l;
                int t2 = r;
                while (t1 < t2) {
                    b[t1] = a[l];
                    b[t2] = a[r];
                    t1++;
                    t2--;
                }
            } else {
                for (int k=l; k<=r; k++) {
                    b[k] = a[l];
                }
            }
            int cnt = (len-1)/2;
            if (ans < cnt) ans = cnt;
            l=r+1;
        } else {
            l+=1;
        }
    }
    printf("%d\n",ans);
    for (int i=0; i<n; i++) {
        printf("%d ",b[i]);
    }
    puts("");
    return 0;
}

와우 맞았다. 대회가 끝나고 나서 알게된 사실이지만, 문제에 불가능한 경우는 -1을 출력하라는 말이 있었다. 문제를 문제와 입력,출력 예제만 보고 풀었기 때문에, (입력 형식, 출력 형식 설명을 안 읽었다) -1을 출력한다는 조건을 보지 못해서 불가능한 경우가 있는지에 대한 생각을 해본적이 없다. 물론, 불가능한 경우는 없다.

이제 D를 풀어보자.

문제에 소수점이 많고, 수식이 필요할 것 같아서 나중에 풀기로 결정하고 E를 열었다.

1, 2, 3, ., #으로 이루어진 N*M 크기의 배열이 있을 때, 1, 2, 3을 모두 연결하는데 필요한 다리의 최소 길이를 구하는 문제다. .만 다리로 바꿀 수 있고, #은 바꿀 수 없다.

각 칸과 1, 2, 3과의 거리를 알아야 하는데, 그걸 하기 위해서, 1, 2, 3을 기준으로 모든 칸에 대해서 BFS를 돌려서 거리를 구했다.

d[k][i][j] = (i, j)과 숫자 k 사이의 최단 거리

그럼 이제 모든 칸에 대해서, 1, 2, 3과의 거리를 구한 다음에, 2를 빼준 것이 그 칸에서 모이는 다리를 연결하는 비용이다.

코드를 작성하고 제출을 했다.

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <numeric>
#include <list>
#include <deque>
#include <string>
#include <sstream>
using namespace std;
char a[1111][1111];
int d[3][1111][1111];
bool c[1111][1111];
int n,m;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int arr[4][4];
int main() {
    scanf("%d %d",&n,&m);
    for (int i=0; i<n; i++) {
        scanf("%s",a[i]);
    }
    for (int w=1; w<=3; w++) {
        queue<pair<int,int>> q;
        memset(c,false,sizeof(c));
        for (int l1=0; l1<n; l1++) {
            for (int l2=0; l2<m; l2++) {
                if (a[l1][l2] == w+'0') {
                    q.push(make_pair(l1,l2));
                    c[l1][l2] = true;
                }
            }
        }
        while (!q.empty()) {
            auto p = q.front();
            q.pop();
            int x = p.first;
            int y = p.second;
            for (int k=0; k<4; k++) {
                int nx = x+dx[k];
                int ny = y+dy[k];
                if (0 <= nx && nx < n && 0 <= ny && ny < m) {
                    if (c[nx][ny] == false && a[nx][ny] != '#') {
                        d[w-1][nx][ny] = d[w-1][x][y]+1;
                        c[nx][ny] = true;
                        q.push(make_pair(nx,ny));
                    }
                }
            }
        }
    }
    int ans = 0;
    for (int l1=1; l1<=2; l1++) {
        for (int l2=l1+1; l2<=3; l2++) {
            for (int i=0; i<n; i++) {
                for (int j=0; j<m; j++) {
                    if (d[l1-1][i][j] != 0 && a[i][j] == l2+'0') {
                        if (arr[l1][l2] == 0) {
                            arr[l1][l2] = d[l1-1][i][j];
                        } else if (arr[l1][l2] > d[l1-1][i][j]) {
                            arr[l1][l2] = d[l1-1][i][j];
                        }
                    }
                }
            }
            //printf("%d %d %d\n",l1,l2,arr[l1][l2]);
            if (arr[l1][l2] == 0) {
                printf("-1\n");
                return 0;
            }
        }
    }
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            if (a[i][j] != '.') {
                continue;
            }
            bool ok = true;
            int cur = 0;
            for (int k=0; k<3; k++) {
                if (d[k][i][j] == 0) {
                    ok = false;
                }
                cur += d[k][i][j];
            }
            cur -= 2;
            if (ok && ans > cur) {
                ans = cur;
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}

맞았다!

채점을 받으니 틀렸다.

문제를 대충읽어서 틀리고 말았다. 인접한 숫자끼리는 다리 없이 지나갈 수 있었다.

인접한 숫자끼리 다리 없이 지나갈 수 있는 것을 처리한 소스는 아래와 같고, 아래 소스는 맞은 소스이다.

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <numeric>
#include <list>
#include <deque>
#include <string>
#include <sstream>
using namespace std;
char a[1111][1111];
int d[3][1111][1111];
bool c[1111][1111];
int n,m;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int arr[4][4];
int main() {
    scanf("%d %d",&n,&m);
    for (int i=0; i<n; i++) {
        scanf("%s",a[i]);
    }
    for (int w=1; w<=3; w++) {
        queue<pair<int,int>> q;
        memset(c,false,sizeof(c));
        for (int l1=0; l1<n; l1++) {
            for (int l2=0; l2<m; l2++) {
                if (a[l1][l2] == w+'0') {
                    q.push(make_pair(l1,l2));
                    c[l1][l2] = true;
                }
            }
        }
        while (!q.empty()) {
            auto p = q.front();
            q.pop();
            int x = p.first;
            int y = p.second;
            for (int k=0; k<4; k++) {
                int nx = x+dx[k];
                int ny = y+dy[k];
                if (0 <= nx && nx < n && 0 <= ny && ny < m) {
                    if (c[nx][ny] == false && a[nx][ny] != '#') {
                        d[w-1][nx][ny] = d[w-1][x][y]+1;
                        c[nx][ny] = true;
                        q.push(make_pair(nx,ny));
                    }
                }
            }
        }
    }
    int ans = -1;
    for (int l1=1; l1<=2; l1++) {
        for (int l2=l1+1; l2<=3; l2++) {
            for (int i=0; i<n; i++) {
                for (int j=0; j<m; j++) {
                    if (d[l1-1][i][j] != 0 && a[i][j] == l2+'0') {
                        if (arr[l1][l2] == 0) {
                            arr[l1][l2] = d[l1-1][i][j];
                        } else if (arr[l1][l2] > d[l1-1][i][j]) {
                            arr[l1][l2] = d[l1-1][i][j];
                        }
                    }
                }
            }
        }
    }
    if (arr[1][2] != 0 && arr[1][3] != 0) {
        if (ans == -1 || ans > arr[1][2] + arr[1][3] - 2) {
            ans = arr[1][2] + arr[1][3] - 2;
        }
    }
    if (arr[1][2] != 0 && arr[2][3] != 0) {
        if (ans == -1 || ans > arr[1][2] + arr[2][3] - 2) {
            ans = arr[1][2] + arr[2][3] - 2;
        }
    }
    if (arr[1][3] != 0 && arr[2][3] != 0) {
        if (ans == -1 || ans > arr[1][3] + arr[2][3] - 2) {
            ans = arr[1][3] + arr[2][3] - 2;
        }
    }
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            if (a[i][j] != '.') {
                continue;
            }
            bool ok = true;
            int cur = 0;
            for (int k=0; k<3; k++) {
                if (d[k][i][j] == 0) {
                    ok = false;
                }
                cur += d[k][i][j];
            }
            cur -= 2;
            if (ok && (ans == -1 || ans > cur)) {
                ans = cur;
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}