Atcoder Beginner Contest 253 후기

A. Median?

 세 수 a,b,c가 주어질 때 b가 세 수의 중앙값인지 확인하는 문제

import sys

arr = list(map(int, sys.stdin.readline().split()))
val = arr[1]
res = sorted(arr)
print('Yes' if res[1] == val else 'No')

 

B. Distance Between Tokens

 2차원 평면에서 두 점 사이의 거리를 묻는 문제. 단, 유클리드 거리가 아닌 택시 거리를 출력해야 한다

import sys

n, m = map(int, sys.stdin.readline().split())
arr = [list(sys.stdin.readline().rstrip()) for _ in range(n)]

# a, b = 첫 동그라미의 좌표
# c, d = 두번째 동그라미의 좌표
a, b, c, d = -1, -1, -1, -1
for i in range(n):
    for j in range(m):
        if arr[i][j] == 'o':
            if a == -1:
                a, b = i, j
            else:
                c,d  = i, j
print(abs(a - c) + abs(b - d))

 

C. Max - Min Query

 c++의 map을 통해 쉽게 풀 수 있는 문제. c++의 map은 파이썬의 dict와 같지만, key값이 정렬되는 특징을 지닌다. 이 때 map은 입력으로 주어지는 숫자를 key, 주어지는 숫자가 총 몇번 등장했는지를 value로 저장하는 map으로 정의한다.

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;

int n;
map<int, int> arr;

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

    cin >> n;
    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;
        // 삽입인 경우
        if (num == 1) {
            int x;
            cin >> x;
            // 없으면 1로 초기화, 있으면 1 증가
            if (arr.find(x) != arr.end()) {
                arr[x] += 1;
            }
            else {
                arr[x] = 1;
            }
        }
        // 삭제인 경우
        else if (num == 2) {
            int x;
            int c;
            cin >> x >> c;
            // 없앨 수 있는 갯수만큼 삭제
            arr[x] -= min(arr[x], c);
            // 모두 없애면 map에서 해당 key 삭제
            if (arr[x] == 0) {
                arr.erase(x);
            }
        }
        // 출력인 경우
        else {
            cout << (--arr.end())->first - (arr.begin())->first  <<  "\n";
        }
    }
}

 

D. FizzBuzz Sum Hard

 1 이상 N이하의 숫자들 중 a와 b의 배수들을 제외한 수들의 합을 구하는 문제. 일반적인 포함-배제 문제이다. 1부터 N이하의 자연수의 합은 잘 알려진 공식인 $\frac{n(n +1)}{2}$로 구할 수 있다.

 이 때 a의 배수들의 합을 생각하면, $a + 2a + 3a + ... $이다. 식을 a에 대해 묶으면, $a(1+2...)$이 되므로 역시 위의 공식을 이용하고 a만 곱해주면 된다. b의 경우 같은 방식으로 처리할 수 있다.

 주의해야 할 점은 a와 b의 공약수는 한 번 더해줘야 된다는 점이다. 왜냐하면 위에서 a의 배수이면서 b의 배수이니까 두 번 빼주었기 때문이다

import sys, math

n, a, b = map(int, sys.stdin.readline().split())

# total : 1부터 n까지의 전체 합
total = n * (n + 1) // 2

# temp1 : a의 배수의 갯수
temp1 = n // a

# res1 : a의 배수들의 합
res1 = a * (temp1 * (temp1 + 1)) // 2

# temp2 : b의 배수의 갯수
temp2 = n // b

# res2 : b의 배수들의 합
res2 = b * (temp2 * (temp2 + 1)) // 2

# gcd : a와 b의 최대공약수
gcd = math.gcd(a, b)

# c : a와 b의 최소공배수
c = gcd * (a // gcd) * (b // gcd)

# temp3 : c의 배수의 갯수
temp3 = n // c

# res3 : c의 배수들의 합
res3 = c * (temp3 * (temp3 + 1)) // 2

# 정답 출력
print(total - res1 - res2 + res3)

 

E. Distance Sequence

 업솔빙 문제. 초반에 dp라는 감이 빠르게 왔지만 최적화를 잘 하지 못했다. top down보다는 bottom-up 방식이 풀기 편했다.

 N개의 원소로 이루어지고 특정 조건을 만족하는 수열의 갯수를 구하면 된다. 조건은 $\left| A_i - A_{i + 1}\right| \geq K$를 만족하는지 여부이다. 이 때 상태 공간을 현재 idx번째 위치이고 그 때 원소가 num일 때 조건을 만족하는 수열의 수라고 정의하자. 그런데 현재 수가 num이라면, $num - K < some \ num < num + K$인 구간에 속한 some_num을 고르면 조건을 절대로 만족할 수 없다. 따라서, 점화식은 아래와 같다. $$ dp[idx][num] = \sum_{i = 1}^{num - k} dp[idx - 1][i] + \sum_{i = num + k}^{m} dp[idx - 1][i]$$

 그런데 현재 상태 공간의 값을 계산하기 위해서는 필연적으로 이전 상태 공간을 순회해야 되기 때문에 촉 $O(N^3)의 시간복잡도를 가지게 된다. 따라서, 어떤 부분에서 최적화가 필요하다.

 무엇이 되었든 복잡도를 한 차원 낮춰야 하는데, 크게 보면 두 가지 부분에서 줄일 여지가 있다. 애초에 상태 공간을 1차원으로 모델하든지 점화식의 시그마 부분을 $O(N)$에서 줄이던지. 그런데 문제를 풀기 위해서는 필수적으로 2가지 정보가 필요하므로 첫번째 방법보다는 두번째 방법으로 접근해야한다. 

 두번째 방법으로 최적화하는 방법은 prefix sum, 즉 누적합을 이용하는 방법이다.

<그림 1. 누적합을 이용하여 최적화>

 위 그림 1에서 dp[i][1], 즉 첫번째 물음표의 값을 구한다고 하자. 이 때 k는 임의로 3이라고 하자. 따라서, 우리는 dp[i-1][4], dp[i-1][5], dp[i-1][6]까지의 합이 필요하다. 그런데, 이것은 $pf[i-1][6] - pf[i-1][3]$과 일치한다. 만일 dp[i][5]를 구하는 경우는 dp[i-1][1], dp[i-1][2]의 합만 필요하는 데 이것은 $pf[i-1][2]$와 일치한다. 따라서, 이전에서 필요했던 dp값들을 $O(N)$이 아닌 상수 시간만에 가져올 수 있으므로 전체적인 복잡도는 $O(N^2)$이 된다.

 주의해야 할 점은 현재 수를 기준으로 양 쪽 구간이 1보다 큰지, M보다 작거나 같은지에 따라 더해야 할 누적합의 원소가 달라진다는 점과, 현재 i번째 dp 테이블(dp[i])를 모두 채우면 다시 누적합을 새로 만들어줘야 한다는 점이다

import sys

n, m, k = map(int, sys.stdin.readline().split())
mod = 998244353
# k가 0인 경우는 단순히 모든 경우를 출력하면 된다
if k == 0:
    print(pow(m, n, mod))
else:
    # dp : 현재 idx번째이고 그 때 고른 원소가 num일 때 조건을 만족하는 수열의 경우의 수를 저장하는 2차원 상태 공간 배열
    dp = [[0] * (m + 1) for _ in range(n)]
    # pf : dp 테이블의 각 행(row)에 대한 누적합을 저장하는 2차원 배열
    pf = [[0] * (m + 1) for _ in range(n)]
    
    # idx가 1인 경우 초기화
    for i in range(1, m + 1):
        dp[0][i] = 1
    pf[0][1] = dp[0][1]
    for i in range(2, m + 1):
        pf[0][i] = pf[0][i - 1] + dp[0][i]
        pf[0][i] %= mod
        
    # 점화식
    for i in range(1, n):
        for j in range(1, m + 1):
            # 왼쪽 구간이 1이상인 경우
            if j - k >= 1:
                dp[i][j] += pf[i - 1][j - k]
            # 오른쪽 구간이 M이하인 경우
            if j + k <= m:
                dp[i][j] += pf[i - 1][m] - pf[i - 1][j + k - 1]
            dp[i][j] %= mod
            
        # 누적합 갱신
        pf[i][1] = dp[i][1]
        for j in range(2, m + 1):
            pf[i][j] = pf[i][j - 1] + dp[i][j]
            pf[i][j] %= mod
            
    # 정답 계산 및 출력
    ans = 0
    for i in range(1, m + 1):
        ans += dp[n - 1][i]
        ans %= mod
    print(ans % mod)

 

후기 : 기업 주최로 열린 ABC + 상위권에게는 상금 지급이라서 평소보다 빡세게 느껴졌다. 다만, D가 굉장히 쉬워서 E까지 푸는 것을 목표로 했지만 못풀어서 아쉬웠다. 생각해보면 손도 못댈 문제는 아니고 정해인 DP까지 잘 접근했지만 최적화를 잘 시키지 못했다. 뭔가 D,E는 종합적으로 사고해야 되는데 원툴로만 쇼부를 보려니까 일어나는 현상같다. 어쨌든 꾸준히 하자