0. [C++] code jam


https://codingcompetitions.withgoogle.com/codejam/round/000000000019fd74


 1. 풀이


1) Pattern Matching

이 문제를 푸는 포인트는 출력하는 string을 3개로 나누어서 만들어주는 것이다.

나의 경우에는 pre, mid, end의 3개의 string을 만들어서 문자열을 관리해주었다.

i) pre와 end의 데이터 입력

입력받은 문자들에서 최장길이의 pre, end를 구해주면 된다. 

저장하는 데이터는 '*'라는 입력이 들어오는 시점까지 문자열이다.

저장된 데이터가 존재하는 경우라면, 현재 저장된 데이터와 지금 비교하는 데이터의 문자가 동일한지 확인을 하는 절차를 걸친다. 만일 데이터가 일치하지 않는다면 

'*'를 출력하고 함수를 마무리한다.


최종적으로 문자열 입력이 끝나면, end의 경우는 reverse 함수를 활용해서 문자열을 뒤집어준다.


ii) mid의 데이터 입력

mid의 경우는 양쪽의 데이터를 모두 입력받은 이후 나머지 데이터를 관리하는 부분으로, 그냥 탐색하고 남은 '*'를 제외한 모든 문자열을 집어넣어주었다.




2) Pascal Walk

이번 문제는 수열을 그려보면 상당히 특이한점을 발견할 수 있었는데, 바로 삼각형 수열의 i번째 층은 2^(i -1) 이라는 점이었다.

이 특징을 활용한다면, i번째 층까지 모든 데이터를 더한다면 그 값은 '2^i - 1'이 된다는 점이다.

즉, 우리가 찾는 수의 입력에 대해서 가장 처음에 우리가 어디 층까지 데이터를 탐색해야하는지 찾아주고, 가장 마지막 층부터 데이터를 추가해주면서 우리가 원하는 숫자에 맞춰주면 문제를 해결할 수 있었다.




3) Square Dance

이 문제가 가장 직관적으로 와닿았던 문제였다. 스테이지에서 현재 자신의 퍼포먼스 점수보다 주변 네 방향의 평균의 퍼포먼스 점수가 낮은 경우 탈락을 시키는 문제였다.


이 문제의 핵심 포인트는 

1. 탈락하는 동작은 한번에 동시에 이루어져야하고, 

2. 다음에 탈락할 인원을 다시 추려주어야 한다는 것이다.

3. 추가적으로 탈락한 인원의 경쟁자들의 compass? 에 대한 정보를 갱신해주어야 하는 것이다.


처음에 데이터를 마구잡이로 만들어서 관리하고, 경쟁자에 대한 탐색을 4개의 방향에 대해서 경쟁자가 나오는 시점까지 반복문을 활용한 탐색을 활용하여 시간초과가 발생하였다.

경쟁자에 대한 정보를 값이 아닌 위치 정보로 저장하는 방법으로 탐색의 속도를 획기적으로 빠르게 끌어올릴 수 있었다.


아, 추가적으로 처음 탈락하는 인원은 첫 비교에서 vector에 담아서 인원을 관리해주었다.

처음 이후부터는 탈락하는 인원의 주변 사람들의 데이터를 갱신하게 되는데, 이 갱신되는 데이터를 임의의 vector에 담아서 갱신이 전부 완료된 이후,

갱신된 인원을 탈락하는지 확인을 하는 동작을 수행하고, 탈락하게 되는 경우 다시 vector에 쌓아준 이후, 한번에 넘겨주는 방식을 택해주었다.

한번에 인원을 탈락시키는 것이 중요했었다.




 2. 소스코드


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
#include <vector>
#include<iostream>
#include <string>
#include<algorithm>
 
using namespace std;
 
int N;
vector<string> V;
 
void calc() {
    int n;
 
    string pre, mid, end;
    for (int i = 0; i < N; i++) {
        int here_length = V[i].length();
        int j, k, m;
        for (j = 0; j < here_length; j++) {
            if (V[i][j] == '*') break;
            if (pre.length() == j) pre.push_back(V[i][j]);
            if (pre[j] != V[i][j]) {
                cout << "*\n";
                return;
            }
        }
        for (k = here_length - 1, m = 0; j < here_length; m++, k--) {
            if (V[i][k] == '*') break;
            if (end.length() == m) end.push_back(V[i][k]);
            if (end[m] != V[i][k]) {
                cout << "*\n";
                return;
            }
        }
        for (; j < k; j++) if (V[i][j] != '*') mid.push_back(V[i][j]);
    }
 
    reverse(end.begin(), end.end());
    cout << pre << mid << end << "\n";
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    int t;
    cin >> t;
    for (int i = 1; i <= t; i++) {
        cin >> N;
 
        V.clear();
 
        for (int i = 0; i < N; i++) {
            string temp;
            cin >> temp;
            V.push_back(temp);
        }
 
        cout << "Case #" << i << ": ";
        calc();
    }
 
    return 0;
}
 
cs


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
#include <iostream>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;
 
long long N;
vector<pair<int, int> > V;
 
void calc() {
    for (int i = 1;; i++) {
        if (N >= (1LL << i)) continue;
        N -= i;
        int dir = 0;
        for (int j = i; j >= 1; j--) {
            if (N >= (1 << (j - 1)) - 1) {
                if (dir)
                    for (int k = j; k >= 1; k--) V.push_back({ j, k });
                else
                    for (int k = 1; k <= j; k++) V.push_back({ j, k });
                dir = !dir;
                N -= (1 << (j - 1)) - 1;
            }
            else {
                V.push_back({ j, dir ? j : 1 });
            }
        }
        reverse(V.begin(), V.end());
        while (N--) V.push_back({ ++i, 1 });
        return;
    }
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    int t;
    cin >> t;
    for (int i = 1; i <= t; i++) {
        cin >> N;
 
        cout << "Case #" << i << ": \n";    
     calc();
        for (auto a : V) cout << a.first << " " << a.second << "\n";
        V.clear();
 
    }
 
    return 0;
}
 
cs



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
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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include<iostream>
#include<algorithm>
#include<string.h>
#include<vector>
 
using namespace std;
 
int T, R, C;
long long ret;
int INF = 1000000007;
int arr[100001];
int competitor_pos[100001][4];
vector<int> retire;
vector<int> check;
bool visited[100001];
 
void calc_level(int here) {
    int sum = 0;
    int count = 0;
    for (int i = 0; i < 4; i++) {
        if (competitor_pos[here][i] != INF) {
            sum += arr[competitor_pos[here][i]];
            count++;
        }
    }
    if ((arr[here] * count) < sum) {
        retire.push_back(here);
    }
}
 
void calc() {
    retire.clear();
    // 경쟁력 비교
    for (int i = 0; i < R*C; i++) {
        competitor_pos[i][0] = INF;
        competitor_pos[i][1] = INF;
        competitor_pos[i][2] = INF;
        competitor_pos[i][3] = INF;
        if (i - C >= 0) {
            competitor_pos[i][0] = i - C;
        }
        if (i + C < R*C) {
            competitor_pos[i][3] = i + C;
        }
        if ((i + 1) % C && (i+1) < R*C) {
            competitor_pos[i][2] = i + 1;
        }
        if (i % C && i - 1 >= 0) {
            competitor_pos[i][1] = i - 1;
        }
        calc_level(i);
    }
 
    long long this_sum = ret;
 
    vector<int> next_round = retire;
    
    while (!next_round.empty()) {
        int here = next_round.back();
        next_round.pop_back();
 
        // 이번에 떨어지는 참가자의 경쟁력을 빼준다.
        this_sum -= arr[here];
        // 주변 참가자의 경쟁력을 갱신한다.
        if (competitor_pos[here][0] != INF) {
            competitor_pos[competitor_pos[here][0]][3] = competitor_pos[here][3];
            check.push_back(competitor_pos[here][0]);
        }
 
        if (competitor_pos[here][1] != INF) {
            competitor_pos[competitor_pos[here][1]][2] = competitor_pos[here][2];
            check.push_back(competitor_pos[here][1]);
        }
 
        if (competitor_pos[here][2] != INF) {
            competitor_pos[competitor_pos[here][2]][1] = competitor_pos[here][1];
            check.push_back(competitor_pos[here][2]);
        }
 
        if (competitor_pos[here][3] != INF) {
            competitor_pos[competitor_pos[here][3]][0] = competitor_pos[here][0];
            check.push_back(competitor_pos[here][3]);
        }            
 
        competitor_pos[here][0] = INF;
        competitor_pos[here][1] = INF;
        competitor_pos[here][2] = INF;
        competitor_pos[here][3] = INF;
 
        if (next_round.empty()) {
            ret += this_sum;
            retire.clear();
            for (int i = 0; i < check.size(); i++) {
                if (!visited[check[i]]) {
                    calc_level(check[i]);
                    visited[check[i]] = true;
                }
            }
            for (int i = 0; i < check.size(); i++) {
                visited[check[i]] = false;
            }
            check.clear();
            if (retire.empty())
                break;
            next_round = retire;
        }
    }
 
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> T;
    for (int i = 1; i <= T; i++) {
        cin >> R >> C;
        ret = 0;
        for (int j = 0; j < R*C; j++) {
            cin >> arr[j];
            ret += arr[j];
        }
 
        calc();
 
        cout << "Case #" << i << ": " << ret << "\n";
    }
 
    return 0;
}
cs




 3. 참고




질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!




저작자표시

'<code jam> > |2020| code jam' 카테고리의 다른 글

[C++] code jam 2020 Qualification Round  (0) 2020.04.08

 0. [C++] code jam 


https://codingcompetitions.withgoogle.com/codejam/round/000000000019fd27


 1. 풀이


1. Vestigium

이 문제는 'Latin square'를 분석하는 문제였다. 이에 대한 관련 글은 검색을 통해 알아보았는데, 간단하게 N*N의 배열에 가로 세로줄에 중복되지 않는 1~N까지의 수를 배치하는 배열이다.

이 문제에서 출력으로 Case #x: k r c를 출력해야 하는데, k는 대각선의 총 합, r은 가로줄에서 오류가 있는 줄의 총 합, c는 세로줄에서 오류의 총 합을 출력하면 된다.


이 문제의 풀이는 간단하게 모든 수를 방문하는 것으로 풀이하였다. bool 배열을 만들어서 각 줄의 중복을 관리하고, 중복이 발생하면 카운트를 해주며 다음 줄을 탐색하는 방식을 택하였다.



2. Nesting Depth

이 문제는 입력된 숫자에 맞게 자신의 좌 우에 괄호 쌍이 존재해야하는 문제였다.

Case #1: 0000
Case #2: (1)0(1)
Case #3: (111)000
Case #4: (1)

이와 같은 결과를 얻기 위해서 간단하게 입력을 string에 담고, string을 순서대로 따라가면서 현재 숫자의 입력에서 필요한 괄호의 개수만큼 그때 그때 괄호를 string에 추가해주는 방식을 택해주었다. 마지막으로 괄호를 닫는 과정은 코드에 주석으로 설명해놓았으니 코드를 읽어보시면 이해할것이라 생각하고 생략.




3. Parenting Partnering Returns

이 문제는 생각보다 너무 간단한데, 출력에서 시간 순서와 별개로 'C', 'J'를 입력 순서로 출력해주었어야 하는 부분이 틀린것을 알아차리는데까지 시간이 오래걸렸다.

이 문제를 해결하기 위해 pair<int, int> 활용을 통해 해결해주었다.


추가적으로 문제를 빠르게 해결하기 위해 input을 vector에 저장하여 시간순서대로 정렬해주었고, Cameron과 Jamie를 배치하는데 두명중 시간이 자유로운 사람을 우선적으로 배치하는 방식을 택해주었다. 또한 배치가 불가능한 경우라면, 탐색을 종료하고 IMPOSSIBLE을 출력하도록 코드를 구현해주었다.


4. ESAb ATAd

ㅎㅎ 문제를 이해하지 못했다... 이는 이후에 추가적으로 공부해보자.

문제를 다시 보면서 다른 사람의 코드를 읽는 것이 가능하던데, 혹시 이 글을 읽으시는 분이 계신다면 참고되셨으면 좋겠네요.



5. Indicium

이 문제는 1번 문제의 확장판이라 보면 된다.

각 줄에 숫자가 겹치지 않게 배치하는 과정에서 bfs, dfs를 활용하면 될 것이라고 예상은 하지만, 실제 구현은 실패하였다.



 2. 소스코드


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
#include<iostream>
#include<algorithm>
 
using namespace std;
 
int T, N;
int arr[101][101];
 
pair<int, int> calc() {
    pair<int, int> ret = { 0,0 };
    for (int i = 0; i < N; i++) {
        bool row[101] = { false };
        bool col[101] = { false };
        bool flag_row = false;
        bool flag_col = false;
        for (int k = 0; k < N; k++) {
            if (!row[arr[i][k]]) {
                row[arr[i][k]] = true;
            }
            else {
                if (!flag_row) {
                    ret.first++;
                    flag_row = true;
                }
            }
            if (!col[arr[k][i]]) {
                col[arr[k][i]] = true;
            }
            else {
                if (!flag_col) {
                    ret.second++;
                    flag_col = true;
                }
            }
        }
    }
 
    return ret;
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> T;
    for (int i = 1; i <= T; i++) {
        cin >> N;
        for (int j = 0; j < N; j++) {
            for (int k = 0; k < N; k++)
                cin >> arr[j][k];
        }
        int sol = 0;
        for (int j = 0; j < N; j++)
            sol += arr[j][j];
        pair<int, int> ret = calc();
 
        cout << "Case #" << i << ": " << sol << " " << ret.first << " " << ret.second << "\n";
    }
 
    return 0;
}
cs


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
#include<iostream>
#include<algorithm>
#include<string>
 
using namespace std;
 
int T;
string S;
 
void calc() {
    int num = 0;
    int this_num = 0;
    for (int i = 0; i < S.size(); i++) {
        if (S[i] >= '0' && S[i] <= '9') {
            this_num = S[i] - '0';
            //만일 이전 수보다 더 큰 수가 들어왔다면, '('를 추가로 입력해준다.
            if(num < this_num)
                for (int k = 0; k < this_num - num; k++) {
                    S.insert(i, 1, '(');
                }
            //만일 더 작은 수라면, 앞에 차이만큼 ')'를 입력해준다.
            else {
                for (int k = 0; k < num - this_num; k++) {
                    S.insert(i, 1, ')');
                }
            }
                num = this_num;
        }
    }
    for (int i = 0; i < this_num; i++) {
        S.push_back(')');
    }
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> T;
    for (int i = 1; i <= T; i++) {
        cin >> S;
 
        calc();
 
        cout << "Case #" << i << ": " << S << "\n";
    }
 
    return 0;
}
cs





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
59
60
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
 
using namespace std;
 
int T, N;
vector<pair<pair<int, int>, int> > V;
int arr[1001];
 
bool calc() {
    int end_C=0, end_J=0;
    for (int i = 0; i < V.size(); i++) {
        if (end_C <= V[i].first.first) {
            arr[V[i].second] = 1;
            end_C = V[i].first.second;
        }
        else if (end_J <= V[i].first.first) {
            arr[V[i].second] = 2;
            end_J = V[i].first.second;
        }
        else {
            return false;
        }
    }
    return true;
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> T;
    for (int i = 1; i <= T; i++) {
        cin >> N;
        V.clear();
        int temp1, temp2;
        for (int k = 0; k < N; k++) {
            cin >> temp1 >> temp2;
            V.push_back({ {temp1, temp2}, k });
        }
        sort(V.begin(), V.end());
        if (calc()) {
            cout << "Case #" << i << ": ";
            for (int k = 0; k < N; k++) {
                if (arr[k] == 1)
                    cout << 'C';
                else
                    cout << 'J';
            }
            cout << "\n";
        }
        else {
            cout << "Case #" << i << ": IMPOSSIBLE\n";
        }
    }
 
    return 0;
}
cs




 3. 참고


구종만, 「프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략」, 인사이트, 2012, p.216~236.



질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!




저작자표시

'<code jam> > |2020| code jam' 카테고리의 다른 글

[C++] code jam 2020 Round 1A(코드잼 2020)  (0) 2020.04.11

+ Recent posts

티스토리툴바