AtCoder Beginner Contest 242 후기

A. T-shirt

 특정 등수 이상이면 무조건 티셔츠를 받으므로 1이고, 특정 등수 구간에 속할 때 x명에게 티셔츠를 추첨으로 준다. 구간에도 속하지 못하면 티셔츠를 절대 받지 못하므로 0이다. 단순히 구간별 확률을 출력하면 된다

import sys, bisect

a, b, c, x = map(int, sys.stdin.readline().split())
if x <= a:
    print(1)
else:
    if a + 1 <= x <= b:
        print(c / (b - (a + 1) + 1))
    else:
        print(0)

B. Minimize Ordering

 문자열이 주어졌을 때 이를 재조합했을 때 사전순으로 가장 앞서는 문자열을 출력하면 된다

import sys, bisect

x = list(sys.stdin.readline().rstrip())
x = sorted(x)
print(''.join(x))​

C. 1111gal password

 이번 대회에서 가장 아쉬웠던 문제. N자리 수의 숫자 중 각 자릿수의 숫자의 절댓값 차이가 1이하인 숫자들의 갯수를 세면 된다. 처음에는 백트래킹으로 시도했는데 순간적으로 절대 시간안에 들어올 수 없다는 판단 하에 다이나믹 프로그래밍으로 바꿨으나, 파이썬의 고질적인 시간초과문제로 c++로 바꿔서 풀게 되었다. 정해라고 판단했는데 WA가 떠서 당황한 나머지 백트래킹으로 시도했고 다시한번 TLE를 마주하게 되었다. 허망하게도 modulo 연산을 잘못해줘서 WA를 받았다는 사실을 깨닫고 수정 후 AC를 맞게 되었다. 페널티가 없었다면 1400~1600등을 했을텐데 뻘짓을 하는 바람에 3800등으로 추락하게 되었다..

 다이나믹 프로그래밍 상태 공간은 현재 길이가 idx이고, 마지막 숫자가 num일 때 가능한 전체 경우인 dp[idx][num]인 2차원 배열이다. 점화식은 아래와 같다. $$dp[idx][num] \ += dp[idx + 1][num - 1] + dp[idx + 1][num + 1] + dp[idx + 1][num]$$

단, num이 1이거나 9라면 각각 0인 경우를 제외해야 한다

#include <bits/stdc++.h>

using namespace std;

int n;
int dp[1000001][10];
int mod = 998244353;

// go : 현재 idx번째 자리 수이고 마지막 수가 num일 때 가능한 경우의 수를 리턴하는 함수
int go(int idx, int num) {
	// Base Case : 자릿수가 n일 때
    if (idx == n) {
        return 1;
    }
    // Memoization
    if (dp[idx][num] != -1) {
        return dp[idx][num] % mod;
    }
    dp[idx][num] = 0;
    // 만약 num이 1이라면 num + 1밖에 안된다
    if (num == 1) {
        dp[idx][num] += go(idx + 1, 2);
        dp[idx][num] %= mod;
    }
    // 만약 num이 9라면 num - 1밖에 안된다
    else if (num == 9) {
        dp[idx][num] += go(idx + 1, 8);
        dp[idx][num] %= mod;
    }
    // 점화식
    else {
        dp[idx][num] += go(idx + 1, num + 1) + go(idx + 1, num - 1);
        dp[idx][num] %= mod;
    }
    dp[idx][num] += go(idx + 1, num);
    dp[idx][num] %= mod;
    return dp[idx][num];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

	// 입력부
    cin >> n;
    memset(dp, -1, sizeof(dp));
    int ans = 0;
    // 끝자리별로 가능한 경우를 다 더함
    for (int i = 1; i < 10; i++) {
        ans += go(1, i);
        ans %= mod;
    }
    // 정답 출력
    cout << ans % mod;
}

총평 : 이번에도 D를 풀지 못했다. 원래도 못하는데 더 못해지니까 좀 그렇긴 하다. 하지만 어쩔 것인가! 내가 못해서 못푼 것이니 변명의 여지는 없고 그저 업솔빙밖에 할 게 없다. 레이팅은 오르고 있으니 성장하고 있다는 의미이긴 하나, 냉정하게 아직은 낮은 레이팅이라 등수가 좋지 못해도 오르는 것이라고 생각한다. 분발하자.