AtCoder Beginner Contest 249 후기

A. Jogging​

 두 사람 A와 B가 있을 때, A는 a분동안 걷고, c분을 쉰다. B는 d분동안 걷고, f분을 쉰다. 둘다 같은 x시간에 동시에 출발했을 때, 누가 더 멀리 가있는지 확인하는 간단한 수학문제이다. A는 1초에 b만큼 가고, B는 1초에 e만큼 간다. 접근법은 간단하다. 걷고 쉬는 것을 하나의 사이클이라고 할 때, 전체 사이클을 구한다. 이후 남은 시간과 걸을 수 있는 시간을 비교하여 더 작은 쪽만큼 걸으면 전체 거리가 된다

import sys

# 입력부
a,b,c,d,e,f,x = map(int, sys.stdin.readline().split())
taka = (a * (x // (a + c)) + min((x % (a + c)), a)) * b
aoki = (d * (x // (d + f)) + min((x % (d + f)), d)) * e
if taka > aoki:
    print("Takahashi")
elif taka < aoki:
    print('Aoki')
else:
    print("Draw")

B. Perfect String

 간단한 문제이다. 알파벳 대문자부터 소문자까지 한번만 등장하면 Yes, 그렇지 않으면 No인데 알파벳 대문자와 소문자가 적어도 하나 이상 나오는 조건만 주의하면 된다

import sys, string

# 입력부
arr = list(sys.stdin.readline().rstrip())
# cache : 특정 알파벳이 몇번 나왔는지 저장하는 dictionary
cache = dict()

# flag1 : 소문자가 한번이라도 나오는지 확인하는 변수
# flag2 : 대문자가 한번이라도 나오는지 확인하는 변수
flag1, flag2 = False, False

for i in arr:
	# 중복이면 절대로 조건을 만족할 수 없다
    if i in cache:
        print('No')
        sys.exit(0)
    # 소문자 등장 시 flag1 변수 변경
    if i in string.ascii_lowercase:
        flag1 = True
    # 대문자 등장 시 flag2 변수 변경
    if i in string.ascii_uppercase:
        flag2 = True
    cache[i] = 1
    
# 조건에 따라 정답 출력
print('Yes' if flag1 and flag2 else 'No')

C. Just K

 브루트 포스문제이다. N이 15로 매우 작기 때문에 복잡도를 $O(Max\ Len\ of(S_i) \ * \ N \ 2^N)$으로 해도 문제가 없다. 심지어 $S_i$는 알파벳 소문자로만 이루어지며, 중복된 알파벳이 없기 때문에 최대 26자가 됨을 알 수 있다. 따라서 전체 문자열을 비트마스킹으로 순회한 다음, 비트마스킹에 속한 문자열의 알파벳들의 출현 횟수를 체크하여 조건에 맞게 최대값을 변경시키면 정답을 구할 수 있다.

import sys

# 입력부
n, k = map(int, sys.stdin.readline().split())
arr = []
for _ in range(n):
    arr.append(sys.stdin.readline().rstrip())
ans = 0

# 비트마스킹으로 가능한 부분집합을 전부 뽑는다
for i in range(1 << n):
	# cache : 현재 부분집합에 속한 문자열의 알파벳 출현 횟수를 저장하는 dictionary
    cache = dict()
    cnt = 0
    for j in range(n):
        # 현재 부분 집합에 속하는 문자열인 경우
        if (1 << j) & i != 0:
            # 알파벳의 출현 횟수 저장
            for q in arr[j]:
                if q not in cache:
                    cache[q] = 1
                else:
                    cache[q] += 1
    # 정확히 k번 등장한 알파벳 수 계산
    for j in cache:
        if cache[j] == k:
            cnt += 1
    # 정답 갱신
    ans = max(ans, cnt)
    
# 정답 출력
print(ans)

D. Index Trio

 대회중에 풀긴 했으나, 정해는 아니었다. 우선 필자의 풀이는 다음과 같다. $A_i$로 들어오는 숫자들의 갯수를 저장한다. 전체 수를 순회하면서 분해되는 수 (문제 기준 $A_i$)를 약수의 대칭성을 이용하여 순회한 후에 가능한 두 약수가 캐싱된 갯수에 있는지 확인하고 둘 다 있다면 더해준다. 이 때 2 x 2 = 4처럼 두 약수가 같은 경우는 중복을 제거하기 위해 빼준다. 

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;

int n;
// temp : 입력으로 들어오는 수의 집합
unordered_set<int> temp;
// cnt : 현재 수가 i일 때 몇 개의 숫자가 i인지 저장하는 배열
ll cnt[200001];

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

    // 입력부
    cin >> n;
    ll ans = 0;
    memset(cnt, 0, sizeof(cnt));
    for (int i = 1; i <= n; i++) {
        int a;
        cin >> a;
        temp.insert(a);
        cnt[a] += 1;
    }
    // set을 순회한다
    for (int num : temp) {
    	// 약수의 대칭성을 이용하여 sqrt(N)까지 순회한다
        for (int j = 1; j <= int(sqrt(num)); j++) {
            // 만일 두 약수가 있다면 포함
            if (num % j == 0 && cnt[j] != 0 && cnt[num / j] != 0) {
            	// 2를 곱해주는 이유는, j와 num / j가 자리를 서로 바꿀 수 있기 때문이다
                ans += 2 * (cnt[num] * cnt[j] * cnt[num / j]);
                // 만일 두 약수가 같다면 배제
                if (j == num / j) {
                    ans -= cnt[num] * cnt[j] * cnt[num / j];
                }
            }
        }
    }
    // 정답 출력
    cout << ans;
}

 물론 시간복잡도 상의로 $O(N \sqrt(N))$으로 무리가 없으나, 자칫 N이 더 커진다면 TLE를 피할 수 없을 것이다. 현재는 N이 20만이나, N이 50만 정도만 되어도 3억번의 연산을 해야한다. 대회가 끝나고 공식 풀이를 읽어보았고 공식 풀이를 소개하겠다.

 인덱스 i,j,k가 있다고 하자, 이 때 각각의 $A_i, A_j, A_k$ 중 세 수가 모두 입력의 최대값(이후 M이라고 하겠다)보다 클 수 없다. 기껏해봐야 1이 있는 경우 두 수가 최대값이 될 수 있을 뿐이다. 따라서, $ 1 \leq i,j,k \leq M$이 되며, $A_i = A_j * A_k$ 이고 $A_i, A_j, A_k$는 모두 양의 정수이다. 

 따라서, $A_j$를 기준으로 생각해보자. 어차피 $A_i$는 $A_k$에 의해 결정되므로 $A_i$는 신경쓰지 않아도 된다. 어차피 $A_j$가 가능한 범위는 M, 즉 입력의 최대값이다. 그렇다면 $A_k$가 가능한 범위는 어디까지 일까? M을 $A_j$로 나눈 수의 몫, 즉  $\left \lfloor \frac{M}{A_j}\right \rfloor $이다. 

 이제 복잡도를 구해보자. 최악의 경우 1부터 N까지 단 한번만 들어올 수도 있기 때문에, 이 경우를 가정하고 계산을 하겠다. 이 때 $A_j$의 범위는 1이상 M이하이다. 따라서, $A_j$를 범위에 따라 순회하게 되면 $A_k$의 복잡도는 $\sum_{A_j=1}^{M}\left \lfloor \frac{M}{A_j}\right \rfloor$가 된다. 그런데, 이것은 자명하게도 $\sum_{A_j=1}^{M}\left \lfloor \frac{M}{A_j}\right \rfloor \leq \sum_{A_j=1}^{M} \frac{M}{A_j}$ 가 성립한다. 왜냐하면 단순히 정수값인 몫만 더한 것과 몫과 소숫점까지 같이 포함해서 더한 것은 당연히 후자가 더 크거나 같기 때문이다. 또한 이것은 $\sum_{A_j=1}^{M} \frac{M}{A_j} \leq \frac{M}{1} + \left ( \frac{M}{2} + \frac{M}{2}\right ) + \left (\frac{M}{4} + \frac{M}{4} + \frac{M}{4} + \frac{M}{4} \right)+ ... + \left(\frac{M}{2^d} + ... + \frac{M}{2^d} \right)$로 확장할 수 있다. 이유는 아래의 그림과 같기 때문이다

<그림 1. 증명>

 원래 위의 식을 아래와 같이 바꾸게 되면 분모가 더 작은 수, 즉 더 큰 수로 바꾸기 때문에 전체적인 합 역시 아래가 크거나 같을 수 밖에 없다. 같은 경우는 1까지만 있는 경우거나, $\frac{1} {2}$까지만 있는 경우이다. 따라서, 전체적인 식을 정리하면 $\sum_{A_j=1}^{M}\left \lfloor \frac{M}{A_j}\right \rfloor \leq M(d + 1)$이 된다. 이 때, $2^d = M \rightarrow d = log_2 M$가 되므로 전체적인 복잡도는 $O(M log M)$이 된다. 

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;

int n;
// cache : 현재 수가 i일 때 i가 몇번 나왔는지 저장하는 배열
int cache[200001];
// temp : 입력 수들의 set
unordered_set<int> temp;

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

    // 입력부
    cin >> n;
    memset(cache, 0, sizeof(cache));
    ll ans = 0;
    int m = 0;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        cache[x] += 1;
        temp.insert(x);
        m = max(m, x);
    }
    // 입력 set을 돌면서
    for (int num : temp) {
    	// A_j와 A_k의 곱이 최대값 이하일 때 까지 순회하면서
        // 가능한 쌍을 더해준다
        for (int k = 1; k * num <= m; k++) {
            // 오버플로우가 발생할 수 있으니 long long으로 캐스팅
            ans += (ll) cache[num] * cache[k] * cache[num * k];
        }
    }
    // 정답 출력
    cout << ans;
}

 

대회 후기 : 우테코 방학시기에 방도 구하고 레벨 1 조원들이랑 1박 2일 회식도 해서 상당히 바쁜 나날들이었다. 거기다 선릉으로 출근도 하면서 적응기도 거치고 자취방에 필요한 것들고 구입하고 청소도 하면서 최초로 여유로울 시기에 본 대회라 당연히 제때 참여하지는 못하고 버추얼로 참여했다. 그럼에도 D 풀이를(정해는 아니지만) 떠올려서 운 좋게 맞아서 나름 괜찮다고 생각했으나 공식 풀이를 보고 아직 부족하다고 느꼈다. 그럼에도 불구하고 여전히 페널티를 많이 먹어서 짜증난다. 특히 간단한 A에서 상당히 고전하여 스스로에게 많이 실망했다.. 열심히 하자가 아니라 꾸준히 하자!

 

==== E번 업솔빙 중