AtCoder Beginner Contest 202 - A부터 D까지 업솔빙

AISing Programming Contest 2021（AtCoder Beginner Contest 202） A부터 D까지 업솔빙

세번째로 풀어본 Atcoder 문제셋이다. A번 문제와 B번 문제는 너무 쉬워서 그냥 넘어가고, C번 문제에서 조금 시간을 끌었지만 한번 푼 이후로는 다시 안틀릴 거 같은 문제였다. 그리고 대망에 마지막 D번 문제, 맨날 코드포스만 연습하느라 DP관련 문제를 잘 안풀었는데 이 문제가 내 감각을 다시 일께워 준것 같아서 못풀었지만 업솔빙하면서 기분이 좋았다. 개인적으로 업솔빙을 잘했다고 느낀 문제는 이 문제가 처음이었다. 이번 대회를 참여하면서 배운 것은

1. 다이나믹 프로그래밍 점화식 짜기 복습
2. 파스칼의 삼각형과 다이나믹 프로그래밍의 관계
3. 조합론

문제 옆에 붙어있는 난이도는 Atcoder Problems 에서 추정한 것으로 작성했다는 것을 미리 알린다.

A - Three Dice (*4)

접기/펼치기

문제 설명
주사위를 세번 던져서 각 주사위의 맨 윗면에 $a, b, c$가 보인다.

각 주사위에 아랫면에 있는 숫자들의 합을 구하자.

각 주사위는 평범한 정육각형 주사위로, 서로 반대편에 있는 주사위 면의 합은 $7$이다.

제약

• $1 \le a, b, c \le 6$
• 모든 입력은 정수다.

문제 해설
친절히 문제에서 서로 반대편에 있는 주사위 면 눈금의 합이 7이라고 설명을 해줬다. 즉 각 주사위에 있는 반대편에 있는 눈금은 $7 - a$, $7 - b$, $7 - c$ 이다.
이 숫자들의 합은 $21 - (a + b + c)$ 이다.

정답 코드

#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int a, b, c; cin >> a >> b >> c;
    cout << 21 - (a + b + c);
    return 0;
}

B - 180° (*16)

접기/펼치기

문제 설명
숫자 $0, 1, 6, 8, 9$로만 이루어져 있는 문자열 $S$ 가 주어진다.

문자열 $S$를 $180$ 도 돌린 결과 값을 출력한다. 다시말해서 다음 연산을 $S$에 적용하고, 결과 문자열을 출력하면 된다.

• $S$를 반전한다.
• $0$ 을 $0$으로, $1$을 $1$로, $6$을 $9$으로, $8$을 $8$으로, $9$를 $6$으로 모두 바꾼다.

제약

• $1 \le |S| \le 10^5$
• $S$는 $0, 1, 6, 8, 9$로만 이루어져 있다.

문제 해설
이 문제 또한 위에서 어떻게 풀어야 하는지 설명을 해준다. 문자열을 입력받고, std::reverse함수를 사용한다. 그리고 $6$과 $9$인 경우만 반대로 출력하고 나머지는 그냥 출력하면 된다.

정답 코드

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    string s; cin >> s;
    reverse(s.begin(), s.end());
    for(auto a : s){
        if(a == '6') cout << '9';
        else if(a == '9') cout << '6';
        else cout << a;
    }
    return 0;
}

C - Made Up (*204)

접기/펼치기

문제 설명
길이가 $N$인 세 수열 $A$, $B$, $C$가 주어진다. $A = (A_1, A_2, ..., A_N)$, $B = (B_1, B_2, ..., B_N)$, $C = (C_1, C_2, ..., C_N)$ 이고 이 수열들은 모두 $1$ 부터 $N$사이의 정수로 이루어져 있다.(중복 가능)

식 $A_i = B_{C_j}$를 만족하는 $1$ 부터 $N$사이의 정수로 이루어진 순서쌍 $(i, j)$의 개수를 구하시오.

제약

• $1 \le N \le 10^5$
• $1 \le A_i, B_i, C_i \le N$
• 모든 입력 값은 정수로 주어진다.

문제 해설
처음 문제를 접할때는 std::map을 사용해서 풀면 되겠다고 생각을 했는데, $10^5$개의 값이 $10^5$개 있는 최대의 경우를 생각 못하고 값을 int로 선언해서 한번 미끄러졌던 문제였다. 문제를 풀고 나서도 조금 지저분하게 푼것 같아서 Editorial을 봤는데 역시 깔끔하게 푼거 같다. 한번 보자.

위의 식을 만족하는 순서쌍을 구하면 되는데 당연히 완전탐색으로 풀면 시간초과가 난다. 그래도 처음에는 완전탐색으로 풀 수 없을까? 라는 생각은 정말 좋은 것 같다. 그렇다면 어떻게 시간을 줄일 수 있을까? 미리 $1$ 부터 $N$ 까지 경우의 수를 미리 셀 수는 없는 것일까? $B_{C_j}$를 만족하는 각각의 수를 미리 세어두면 순서쌍을 셀때 $A_i$와 같은 정수를 가진 수를 미리 구해놨기 때문에 그 값을 다 더하면 될 것 같다.

경우의 수를 미리 세는 방법이 well-known으로 존재한다. 횟수를 구하는 배열 cnt를 선언하고 특정 값이 등장하면 그 값을 index로 하고 있는 배열의 원소의 값을 $1$ 올리는 방식으로 구할 수 있다. 이 테크닉은 매우 자주 사용하기 때문에 알아두는 것이 좋다. 그리고 해당하는 $i$값의 개수를 찾고 싶으면 cnt[i]로 개수를 쉽게 구할 수 있다.

먼저 $B$와 $C$ 배열에 있는 숫자를 순회하면서 개수를 전부 세고, $A$ 배열에 있는 원소를 처음부터 끝까지 순회하면서 $A$ 배열에 있는 원소가 $B$와 $C$ 배열에 얼마나 등장하는지 cnt배열을 이용해서 전부 더하면 된다.

정답 코드

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n; cin >> n;
    int a[n + 1], b[n + 1], c[n + 1];
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) cin >> b[i];
    for(int i = 1; i <= n; i++) cin >> c[i];

    int cnt[n + 1] = {};
    for(int i = 1; i <= n; i++) cnt[b[c[i]]]++;
    long long ans = 0;
    for(int i = 1; i <= n; i++) ans += cnt[a[i]];
    cout << ans;
    return 0;
}

D - aab aba baa (*966)

접기/펼치기

문제 설명
문자 'a'가 $A$번 등장하고, 문자 'b'가 $B$번 등장하는 길이가 $A + B$ 인 문자열 중에서 사전순으로 $K$번째로 오는 문자열을 찾아라.

제약

• $1 \le A, B \le 30$
• $1 \le K \le S$ $S$는 문자 'a'가 $A$번 등장하고, 문자 'b'가 $B$번 등장하는 길이가 $A + B$ 인 문자열의 총 개수이다.

문제 해설
엄청 많은 것을 업솔빙을 하면서 배운 문제. 문제에서 기본적으로 제공하는 editorial을 봤을 때는 전혀 이해가 안돼서 구글링을 하다가 한 일본 유저가 쓴 블로그 글을 보고 이해를 했다. 일본어로 되어있긴 한데 파파고를 돌려서 읽어보면 진짜 쉽게 설명을 잘 한것 같다. 그리고 링크 를 이 글에 공유하겠다. 나 처럼 고통받은 사람이 없기를. 그리고 이 글을 보면서 내 나름대로 이해한 내용을 블로그에 글로 남겨본다.

먼저 이 문제는 조합을 사용해서 푸는 문제라는 것을 알아야 한다. 왜냐하면 문자 'a'가 등장하는 횟수를 $a$라고 하고 'b'가 등장하는 횟수를 $b$라고 할 때, 총 $a + b$자리에서 문자 'a'가 들어갈 $a$자리를 찾는 문제이기 때문이다. 그리고 이 경우의 수는 ${a + b}\mathrm{C}{a}$ 로 나타낼 수 있다. 이 경우의 수를 $dp(a, b)$ 라고 정의하자. 이 경우의 수를 쉽게 찾기 위해서 바로 파스칼의 삼각형 공식을 이용한다. 궁금한 사람은 구글에 찾아보고 여기서는 결과 값만 보여주겠다.

• ${n}\mathrm{C}{r} = {n - 1}\mathrm{C}{r} + {n - 1}\mathrm{C}{r - 1}$ 이다.

이 식을 위에서 구한 경우의 수로 구하면

• ${a + b}\mathrm{C}{a} = {a + b - 1}\mathrm{C}{a} + {a + b - 1}\mathrm{C}{a - 1}$ 이다.

${a + b}\mathrm{C}{a}$ 이 $dp(a, b)$로 나타내기로 정의했기 때문에 ${a + b - 1}\mathrm{C}{a}$ 는 $dp(a, b - 1)$로, ${a + b - 1}\mathrm{C}{a - 1}$ 는 $dp(a - 1, b)$로 나타낼 수 있다. 즉

• $dp(a, b) = dp(a, b - 1) + dp(a - 1, b)$

로 나타낼 수 있고 이것이 점화식이다. 이렇게 dp를 구성하는 문제자체가 well-known문제라는 것을 해설을 찾아보면서 알게됐고, 나는 이런 비슷한 문제를 만날 때 푸는 방식을 알게 됐기 때문에 개인적으로 매우 뿌듯했던 문제였다.

이제 모든 경우의 수를 구했다. 이제 $K$번째 수만 구하면 된다. 이 경우는 맨 앞에 문자가 $a$가 오는지, $b$가 오는지에 따라서 경우가 달라진다. 우리가 구할 문자열이 'a'가 $a$개 있고, 'b'가 $b$개 있다고 하자. 맨 앞에 문자 $a$가 온다면 'a'가 $a - 1$개 있고, 'b'가 $b$개 있는 경우에서 경우의 수를 구하면 되기 때문에 $dp(a - 1, b)$를 찾는다. 이때

• $K$가 $dp(a - 1, b)$ 보다 작거나 같으면 문자열 'a'가 맨 앞에 오는 경우가 맞다는 뜻이다. 왜냐하면 b가 사전순으로 뒤에 있기 때문에 a가 앞에 오는 경우를 다 끝나야 그 다음 b가 앞에 오는 경우가 나온다. 따라서 $K$가 $dp(a - 1, b)$ 보다 작거나 같은 경우에는 반드시 $b$가 나올 수 없다.
• 즉 $K$가 $dp(a - 1, b)$보다 크면 문자열 'b'가 맨 앞에 오는 경우인데, 이때 맨 앞에 $a$가 등장하는 경우의 수가 끝났기 때문에 $K$에서 $dp(a - 1, b)$ 값을 뺀 다음 b를 출력한다.

그리고 남은 문자열은 그냥 뒤에 계속 반복해서 붙이면 된다.

정답 코드

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

typedef long long ll;
ll dp[31][31];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    dp[0][0] = 1;
    for(int i = 0; i <= 30; i++){
        for(int j = 0; j <= 30; j++){
            if(i > 0) dp[i][j] += dp[i - 1][j];
            if(j > 0) dp[i][j] += dp[i][j - 1];
        }
    }

    int a, b; 
    ll k;
    cin >> a >> b >> k;
    while(a > 0 && b > 0){
        if(k <= dp[a - 1][b]){
            cout << 'a';
            a--;
        }else{
            k -= dp[a - 1][b];
            cout << 'b';
            b--;
        }
    }
    cout << string(a, 'a') << string(b, 'b');
    return 0;
}