Codeforces Round #640 (Div. 4) 풀이 및 후기

https://codeforces.com/contest/1352

Dashboard - Codeforces Round #640 (Div. 4) - Codeforces

[후기]

 

Programming contest 후기로는 첫 게시물이다. contest라고 하기엔 너무 자주 있긴 하지만, 그래도 시간 재고 스코어보드도 볼 수 있는 기회이니 앞으로도 꾸준히 많이 참여하는 것이 목표이다. 

 

codeforces contest를 많이 참여해보진 않았지만, 난이도는 Div.2와 비교했을 때 매우 쉬운 편이었다고 생각한다. 

(최상위권은 7문제를 20~30분만에 다 풀었더라.... 정말 대단..)

 

문제 풀면서 받은 느낌은, 뭔가 알고리즘을 이용하는 느낌은 많이 들지는 않았고, 특히 예시로 보여준 테스트 케이스보다 훨씬 쉬운 답들이 많이 존재해서 단순 구현 문제가 대부분이었던 것 같다.

물론, 아직 알고리즘을 많이 몰라서 그렇게 느꼈을 수도 있다.

 

23:35 ~ 01:35 총 2시간 동안 진행됐고, 대회 시간 이내에는 A~E를 Accepted 받았었는데, Hack 시간이 끝나고 나니 E번 문제가 마지막 testcase에서 틀렸다고 나와서 다시 제출해서 Accepted를 받았다.

G랑 E는 대회 시간이 끝나고 얼마 지나지않아 해결했는데, 시간이 30분 정도만 더 있으면 좋았겠다는 생각을 했다. 

 

[풀이]

 

A. Sum of Round Numbers

 

https://codeforces.com/contest/1352/problem/A

Problem - A - Codeforces

주어지는 수를 제일 왼쪽 자리를 제외한 모든 자리가 0인 수 들로 분할하는 문제이다. 

각 자리수별로 0이 아니면 0을 붙여주는 쉬운 문제이다.

 

#include<iostream>
#define FOR(i, N) for(int i = 1; i<=N; i++)
 
using namespace std;
 
int main(void) {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    int t; cin >> t;
    int n;
    int arr[5];
    while (t--) {
        cin >> n;
        int div = 10000;
        int cnt = 0;
        while (div && n>0) {
            if (n / div > 0) {
                int temp = (n/div)*div;
                arr[cnt++] = temp;
                n -= temp;
            }
            div /= 10;
        }
        cout << cnt << '\n';
        FOR(i, cnt) cout << arr[i-1] << ' ';
        cout << '\n';
    }
}

B. Same Parity Summands

 

https://codeforces.com/contest/1352/problem/B

Problem - B - Codeforces

n과 k가 입력으로 들어오고, n을 k개의 홀수들, 혹은 k개의 짝수들로만 분할이 가능한지를 물어보는 문제이다. 

 

#include<iostream>
 
using namespace std;
 
int main(void) {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int t; cin >> t;
    while (t--) {
        int n, k; cin >> n >> k;
        if (n < k) cout << "NO\n";
        else {
            if (n % 2 == 1) {
                if (k % 2 == 0) cout << "NO\n";
                else {
                    cout << "YES\n";
                    for (int i = 1; i <= k; i++) {
                        if (i == k) cout << n << '\n';
                        else {
                            cout << 1 << ' ';
                            n--;
                        }
                    }
                }
            }
            else {
                if ((n < (k * 2) && k%2 == 1)) cout << "NO\n";
                else if (n < (k * 2) && k % 2 == 0) {
                    cout << "YES\n";
                    for (int i = 1; i <= k; i++) {
                        if (i == k) cout << n << '\n';
                        else {
                            cout << 1 << ' ';
                            n--;
                        }
                    }
                }
                else {
                    cout << "YES\n";
                    for (int i = 1; i <= k; i++) {
                        if (i == k) cout << n << '\n';
                        else {
                            cout << 2 << ' ';
                            n -= 2;
                        }
                    }
                }
            }
 
        }
    }
}

 

C. K-th Not Divisible by n

 

https://codeforces.com/contest/1352/problem/C

Problem - C - Codeforces

n의 배수가 아닌 수들의 집합에서 K번째 수를 구하는 문제이다. 

자연수 전체 집합에서 K앞에 있는 n의 배수의 개수를 구해준 후, 그 개수만큼 K에 더해주고, 더해진 구간 안에 또 n의 배수가 있다면 그 개수만큼 K에 구해주는 방식으로 구하였다. 

문제 분류를 보니 binary search라고 나와있는데, 무식하지만 이게 더 간단해 보인다....

 

#include<iostream>
 
using namespace std;
 
int main(void) {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int t; cin >> t;
    while (t--) {
        ll n, k; cin >> n >> k;
        ll t1 = k;
        ll t2 = k +k/n;
        while (1) {
            if (t1/n == t2/n) {
                cout << t2 << '\n';
                break;
            }
            ll temp = t2;
            t2 += ((t2 / n) - (t1 / n));
            t1 = temp;
        }
    }
}

 

D. Alice, Bob and Candies

 

https://codeforces.com/contest/1352/problem/D

Problem - D - Codeforces

수열이 주어질 때, 수열의 양쪽 끝에서부터 두 사람이 각각 원소들을 더해오는데, 이전 차례에 상대가 더한 값보다 더 큰 경우, 더하는 것을 멈추고 이를 하나의 step으로 한다. 

구하고자 하는 것은 두 사람이 총 더한 값과, 수행된 전체 step의 수이다. 

 

단순 구현 문제이다.

#include<iostream>
 
#define FOR(i, N) for(int i = 1; i<=N; i++)
 
using namespace std;
 
int main(void) {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int t; cin >> t;
    while (t--) {
        int a = 0;
        int b = 0;
        int n; cin >> n;
        vector<int> v(n);
        FOR(i, n) cin >> v[i - 1];
        int s = 0;
        int e = n - 1;
        int cnt = 0;            
        int alice = 0;
        int bob = 0;
        while (s <= e) {
 
            int check = 0;
            alice = 0;
            while (alice <= bob && s <= e) {
                a += v[s];
                alice += v[s++];
                check = 1;
            }
            if (check == 1) cnt++;
            check = 0;
            bob = 0;
            while (bob <= alice && s<=e) {
                b += v[e];
                bob += v[e--];
                check = 1;
            }
            if (check == 1) cnt++;
        }
        cout << cnt << ' ' << a << ' ' << b << ' ' << '\n';
    }
}

 

E. Special Elements

 

https://codeforces.com/contest/1352/problem/E

Problem - E - Codeforces

수열 A가 주어질 때, 2개 이상의 연속된 A의 원소의 합으로 나타낼 수 있는 A의 원소의 개수를 구하는 문제이다. 

각 원소마다 start = 1와 end = 2를 잡고 [start, end]구간의 합이 해당 원소보다 작으면 end++, 크면 start++을 해주는 방식으로 two pointer를 이용하여 해결해 주었다. 

처음에 통과못한 이유는, 원소가 하나가 들어왔을 때도 end를 2로 잡고 시작하여 2개의 원소 합으로 원소를 나타낼 수 있다고 판단하게 되었다. 

 

#include<iostream>
#include<algorithm>
#include<stack>
#include<cmath>
#include<functional>
#include<string>
#include<vector>
#include<cstring>
#include<utility>
 
#define FOR(i, N) for(int i = 1; i<=N; i++)
 
using namespace std;
int arr[8001];
int prefix[8001];
int main(void) {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        memset(arr, 0, sizeof(arr));
        FOR(i, n) cin >> arr[i];
        int ans = 0;
        FOR(i, n) {
            int s = 1;
            int e = 2;
            if (e > n) break;
            int sum = arr[s] + arr[e];
            while (1) {
                if (arr[i] == sum) {
                    ans++;
                    break;
                }
                else if (arr[i] < sum) {
                    sum -= arr[s++];
                    if (s == e) {
                        if (e<n)    sum += arr[++e];
                        else break;
                    }
                }
                else {
                    if (e < n)     sum += arr[++e];
                    else break;
                }
            }
        }
        cout << ans << '\n';
    }
}

 

F. Binary String Reconstruction

 

https://codeforces.com/contest/1352/problem/F

Problem - F - Codeforces

n0은 "00", n1은 "10" 또는 "01", n2는 "11"이고, n0, n1, n2의 개수가 주어진다.

이 개수를 만족하도록 0과 1로 문자열을 생성하는 것이다.

어차피 0과 1이 만나는 부분만 주의해주면 되므로, "00"을 먼저 n0의 개수에 맞게 적어주고, 

그다음은 "11"을 적은 후, n1이 모자라는 만큼 "01" 또는 "10"을 추가해준다. 

단순 구현 문제이다. 

 

#include<iostream>
 
#define FOR(i, N) for(int i = 1; i<=N; i++)
 
using namespace std;
 
int main(void) {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int t; cin >> t;
    while (t--) {
        int n1, n2, n0; cin >> n0 >> n1 >> n2;
        if (n0 >= 1) FOR(i, n0 + 1) cout << "0";
        if (n2 >= 1)     FOR(i, n2 + 1) cout << "1";
 
        if (n0 == 0 && n2 == 0) {
            if (n1 % 2) FOR(i, (n1 / 2) + 1) cout << "01";
            else {
                cout << "1";
                FOR(i, n1 / 2) cout << "01";
            }
        }
 
        else if (n0 >= 1 && n2 == 0) {
            if (n1 % 2) {
                cout << "1";
                FOR(i, (n1 - 1) / 2) cout << "01";
            }
            else FOR(i, n1 / 2) cout << "10";
        }
 
        else if (n0 == 0 && n2 >= 1) {
            if (n1 % 2) {
                cout << "0";
                FOR(i, n1 / 2) cout << "10";
            }
            else FOR(i, n1 / 2) cout << "01";
        }
        else {
            n1--;
            if (n1 % 2) {
                cout << "0";
                FOR(i, n1 / 2) cout << "10";
            }
            else FOR(i, n1 / 2) cout << "01";
        }
        cout << '\n';
    }
}

 

G. Special Permutation

 

https://codeforces.com/contest/1352/problem/G

Problem - G - Codeforces

이웃한 원소간의 차가 2 이상 4 이하가 되도록 1~n까지의 순열(permutation)을 구한다. 차가 2씩 발생하도록 홀수를 먼저 오름차순으로 나열한 후, 그다음 짝수를 내림차순으로 나열한다. 

홀수와 짝수가 바뀌는 지점은 1이 차이가 나므로 이 부분만 따로 주의해서 구해준다.  (20~24줄)

 

#include<iostream>
 
using namespace std;
 
int main(void) {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        if (n <= 3) cout <<-1<<'\n';
        else if (n == 4) cout << "3 1 4 2" << '\n';
        else {
            int odd = 1;
            while (odd <= n) {
                cout << odd << ' ';
                odd += 2;
            }
            odd -= 2;
            int even = 2;
            while (odd - even > 4) even += 2;
            cout << even << ' ';
            if (even + 4 <= n) cout << even+4 << ' ';
            if (even + 2 <= n) cout << even + 2 << ' ';
            even -= 2;
            while (even >= 1) {
                cout << even << ' ';
                even -= 2;
            }
            cout << '\n';
        }
    }
}