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

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

D번 문제까지 풀어서 1000점 가량 퍼포먼스가 나와서 가상 레이팅 점수가 올랐다. 정말 뿌듯했다. DP문제를 시간내에 해결했다는 점이 정말 고무적인 성과라고 생각한다. 이제 ATcoder 1400점 갈수 있을까?

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

A - Four Digits (*5)

접기/펼치기

문제 설명
$0$부터 $9999$사이 숫자 $N$이 주어진다.

4자리 정수이면 그냥 $N$을 출력하고 4자리 정수가 아닐 경우 앞에 $0$을 붙인 후에 그 숫자를 출력하라.

문제 해설
string 생성자를 사용해서 문제를 푼다. 문자열 크기가 4보다 작으면 작은 수 만큼 앞에 $0$을 만들어서 출력한다.

정답 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    string s; cin >> s;
    cout << string(4 - s.size(), '0') + s;
    return 0;
}

B - Failing Grade (*9)

접기/펼치기

문제 설명
학생 $N$ 명이 시험을 본다. $i$번째 학생은 $a_i$점을 얻었다.

$P$점 보다 낮은 점수를 얻은 학생은 시험에 떨어지고 장학금을 받지 못한다. 시험에 떨어진 학생의 수를 구하라.

문제 해설
모든 학생을 다 확인하면서 조건문 사용해 개수를 세면 된다.

정답 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, p; cin >> n >> p;
    int cnt = 0;
    while(n--){
        int num; cin >> num;
        if(num < p) cnt++;
    }
    cout << cnt;
    return 0;
}

C - Swiss-System Tournament (*367)

접기/펼치기

문제 설명
$1$부터 $2N$까지 번호를 부여받은 $2N$명의 학생이 가위바위보 대회에 참여한다.

대회는 $M$개 라운드로 이루어져 있고 각 라운드에는 $N$번의 1대1 경기를 치룬다. 그리고 이 경기에는 각 학생들이 치룬다.

$i=0,1,...,M$에 대해서 $i$번째 라운드가 끝나고 학생의 순위는 다음과 같이 결정한다.

• $i$번째 라운드가 끝나고 누적 승리수가 많은 학생이 높은 순위이다.
• 만약 승리수가 같다면 ID숫자가 작은 학생이 높은 순위이다.

추가적으로 $i=1,...,M$에 대해서 $i$번째 경기는 다음과 같이 수행한다.

• $k=1,2,...,M$에 대해서 경기는 $i-1$번째 경기가 끝난 후 $(2k-1)$번째와 $2k$번째 순위를 가진 학생이 수행한다.

각 경기에서 두 학생은 가위바위보를 한번만 수행하고 한 사람의 결과는 승, 패, 무승부이다.

지현이는 미래를 볼 수가 있어서 $i$번째 학생이 $j$번째 라운드에서 $A_{i,j}$를 낼 것을 알고있다.

$M$번째 라운드가 끝나고 나서 학생의 순위를 출력하라.

문제 해설
C번문제인데 생각보다 코드가 길어서 풀면서 의아했던 문제이다. 문제 풀이 방법은 쉽다. 매 경기가 끝나고 나서 순위를 주어진 규칙에 따라서 정렬하고 다음 경기를 수행하면 된다.

먼저 승수에 따라서 순위가 결정되기 때문에 pair 앞을 승수로, 뒤를 ID로 설정했다. 이때 승수가 많은 순으로 정렬해야 하기 때문에 내림차순으로 정렬하고 ID값은 작은 순으로 정렬해야 하기 때문에 음수를 붙여서 사용했다.

그 다음에는 각 라운드를 수행하면 된다. 이때 무승부인 경우 두 선수 모두 승수를 세지 않는것이 중요하다.

정답 코드

#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, m; cin >> n >> m;
    char game[2 * n][m];
    vector<pii> v;
    for(int i = 0; i < 2 * n; i++){
        cin >> game[i];
        v.push_back({0, -i});
    }


    for(int i = 0; i < m; i++){
        for(int j = 0; j < 2 * n; j+=2){
            int x = -(v[j].second), y = -(v[j + 1].second);
            if(game[x][i] == game[y][i]) continue;
            if((game[x][i] == 'G' and game[y][i] == 'C') or 
            (game[x][i] == 'C' and game[y][i] == 'P') or
            (game[x][i] == 'P' and game[y][i] == 'G')) (v[j].first)++;
            else (v[j + 1].first)++;
        }
        sort(v.begin(), v.end(), greater<>());
    }
    for(auto [x, y] : v){
        cout << (-y) + 1 << "\n";
    }

    return 0;
}

D - Between Two Arrays (*865)

접기/펼치기

문제 설명
$n$개 숫자로 이루어진 수열 $S=(s_1,s_2,...,s_n)$ 은 모든 $i(1\le i\le n-1)$ 에 대해서 $s_i\le s_{i+1}$를 만족하면 내림차순이 아니라고 한다.

$N$개 정수로 이루어진 두 내림차순이 아닌 수열 $A=(a_1,a_2,...,a_N)$ 과 $B=(b_1,b_2,...,b_N)$이 주어진다.
다음 조건을 만족하는 $N$개 정수로 이루어진 내림차순이 아닌 수열 $C=(c_1,c_2,...,c_N)$을 생각해보자.

• 모든 $i(1\le i\le N)$ 에 대해서 $a_i\le c_i\le b_i$를 만족한다.
  이 조건을 만족하는 내림차순이 아닌 수열 $C$의 개수를 구하라. 그리고 그 개수를 $998244353$으로 나눈 나머지 값을 출력하라.

문제 해설
$N$의 개수가 $3000$ 이하이고 나머지 연산을 하는 것으로 보아서 DP문제라는 감이 왔다. 일단 2차원 DP를 선언한다.

• $dp(i,j)=$ $i$번째 숫자까지 봤을때, 숫자 $j$로 끝나는 위 조건을 만족하는 수열 $C$의 개수

이렇게 선언하면 $dp(0,j)$는 $a[0]\le j\le b[0]$인 모든 $j$에 대해서 1을 대입하면 된다.
그리고 규칙을 찾으면 되는데, $dp(i,j)$에서 $a[i]$보다 작은 $j$는 고려할 필요가 없다. 왜냐하면 존재하지 않는 경우이기 때문이다. 즉 각 $i$번째마다 $j$는 반드시 $a[i]$부터 $b[i]$까지만 고려하면 된다. 그러면 $dp(i,a[i])$는 어떤 방식으로 구할까?
$i-1$번째 수열에서 $0$ 부터 $a[i]$숫자가 마지막인 수열의 경우의 수를 모두 더해서 구한다. 그러면 이 다음 숫자인 $dp(i,a[i]+1)$는 어떻게 구할까? 이미 이전에 $dp(i,a[i])$에서 $dp(i-1,a[i])$까지 경우를 모두 구했기 때문에 이 값에 추가로 $dp(i-1,a[i]+1)$인 경우만 더하면 된다.

즉 각 경우마다 맨 처음을 따로 계산해 주고 남은 뒷 부분은 단순히 점화식을 사용하면 풀리는 문제이다.

정답 코드

#include <bits/stdc++.h>
using namespace std;

const int mod = 998244353;
using ll = long long;
ll dp[3010][3010];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n; cin >> n;
    int a[n], b[n];
    for(auto& x : a) cin >> x;
    for(auto& x : b) cin >> x;

    for(int i = a[0]; i <= b[0]; i++) dp[0][i]++;
    for(int i = 1; i < n; i++){
        for(int j = 0; j <= a[i]; j++){
            dp[i][a[i]] += dp[i - 1][j];
            dp[i][a[i]] %= mod;
        }
        for(int j = a[i] + 1; j <= b[i]; j++){
            dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % mod;
        }
    }

    ll ans = 0;
    for(int i = a[n - 1]; i <= b[n - 1]; i++){
        ans += dp[n - 1][i];
        ans %= mod;
    }
    cout << ans;
    return 0;
}