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

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

이번 대회 문제 set은 전체적으로 평이하다. 마지막 문제에 조금 헤맸는데, 분명 대회때는 TLE가 나와서 이 문제를 못풀었다고 생각했는데 대회 결과를 보니까 4솔로 되어있어서 이상했다. 결과를 보니 대회에서 제공하는 testcase는 모두 통과했는데, virtual에서 제공하는 test case는 통과못해서 그런 결과가 나온것 같다. 하지만 TLE가 나온것은 TLE이기 때문에 틀렸다고 생각하고 업솔빙을 했다.
이번 대회를 참여하면서 배운 것은

1. std::lower_bound()의 활용

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

A - kcal (*6)

접기/펼치기

문제 설명
우리는 100ml 당 $A$ 칼로리를 가진 에너지 드링크를 먹는다. 이 에너지 드링크 $B$ml를 먹으면 몇 칼로리를 얻을까?

제약

• $0 \le A, B \le 1000$
• 모든 입력은 정수이다.

문제 해설
단순 수학, 비례식을 써도 풀 수 있고 곱셈과 나눗셈을 쓰면 풀 수 있다. 100ml당 칼로리 값이 $A$이기 때문에 $B$를 100으로 나눈 값에 $A$를 곱하면 답이다.

정답 코드

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    double a, b; cin >> a >> b;
    cout << a * b / 100;
    return 0;
}

B - Permutation Check (*16)

접기/펼치기

문제 설명
$1$ 부터 $N$ 까지의 수 $N$개가 주어진다 (중복 가능). 즉 $A = (A_1, A_2, ..., A_N)$

$A$가 $N$의 순열인지 결정하시오.

제약

• $1 \le N \le 10^3$
• $0 \le A_i \le N$
• 모든 입력은 정수로 이루어져 있다.

문제 해설
순열은 $1$부터 $N$까지 수가 반드시 한번씩 나타나야 하는 수열을 말한다. 따라서 각 원소의 개수를 구하는 배열을 선언하고 이 값이 1이 아닌 경우 No를 출력하면 된다.

정답 코드

#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 arr[n + 1] = {0};
    for(int i = 0; i < n; i++){
        int num; cin >> num;
        arr[num]++;
    }
    bool flag = true;
    for(int i = 1; i <= n; i++){
        if(arr[i] != 1) flag = false;
    }
    cout << (flag ? "Yes" : "No");
    return 0;
}

C - POW (*63)

접기/펼치기

문제 설명
밑수 $X$에 대해 $Y$번 제곱한 수를 $X$의 $Y$승이라고 하고 $pow(X, Y)$라고 쓴다. 예를 들어 $pow(2, 3) = 2 \times 2 \times 2 = 8$

세 정수 $A, B, C$가 주어진다. $pow(A, C)$와 $pow(B, C)$ 둘중 누가 더 큰지 결정하자.

제약

• $-10^9 \le A, B \le 10^9$
• $1 \le C \le 10^9$
• 모든 값은 정수로 주어진다.

문제 해설
문제 조건을 보면 $A, B, C$ 모두 최대값이 $10^9$이기 때문에 단순한 제곱으로는 이 문제를 풀 수 없다는 것을 눈으로 보면 알 수 있다.
조금만 테스트케이스를 생각해보면 밑수가 크면 제곱한 값도 크고, 밑수가 작으면 제곱한 값도 작다는 것을 알 수 있다. 여기서 제곱의 횟수인 $C$에 따라서 답이 달라진다.
$C$가 짝수이면 $A, B$가 음수인지, 양수인지 상관없이 모두 양수로 바뀌기 때문에 $A, B$에 절댓값을 취하고 비교하면 된다.
$C$가 홀수이면 밑 수가 음수이면 마이너스가 살아있기 때문에 이 점을 주의해야한다. 이것을 고려하더라도 단순히 $A, B$의 대소만 비교하면 간단히 답을 구할 수 있다.

정답 코드

#include <iostream>
#include <string>
#include <algorithm>
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;
    if(c % 2 == 0){
        a = abs(a);
        b = abs(b);
    }
    cout << (a > b ? ">" : (a < b ? "<" : "="));
    return 0;
}

D - Kth Excluded (*713)

접기/펼치기

문제 설명
$N$개 양수로 이루어져 있는 수열 $A = (A_1, A_2, ... A_N)$ 과 $Q$개 질의가 주어진다.

$i$번째 질의 $(1 \le i \le Q)$ 속에 양수 $K_i$가 주어진다. $A_1, A_2, ..., A_N$ 에 속하지 않은 가장 작은 $K_i$번째 양수를 찾아라.

제약

• $1 \le N, Q \le 10^5$
• $1 \le A_1 < A_2 < ... < A_N \le 10^{18}$
• $1 \le K_i \le 10^{18}$

문제 해설
일단 이 문제의 제목인 $Kth Exclued$를 이해해야 하는데, MEX개념과 똑같기 때문에 구글에서 검색해 보자. 만약 배열이 $3, 6, 7$ 로 주어진다면 배열에 속하지 않은 가장 작은 첫번째 양수는 1이고, 2번째는 2, 3번째는 4이다.

우리는 cnt라는 배열의 값을 구할 것이고 정의는 다음과 같다.

• $cnt[i] = $ $i$번째 배열의 원소보다 작은 양수의 개수

그렇다면 이 값은 어떻게 구할까? 첫번째 배열에 원래 있어야 하는 수는 뭘까? $1$이다. 그런데 이 값 대신에 다른 수 $x$가 등장했다면 그 앞에 있는 양수의 개수는 $x - i$ 이다. 만약 첫번째 배열의 원소에 $3$이 있다면 원래는 $1$이 있어야 하지만 그 자리에 $3$이 차지해있기 때문에 앞에 $2$개의 양수가 있다는 뜻이다. 만약 $10$번째 배열에 숫자 $10$이 있다면 원래 있는 자리에 알맞는 수가 있기 때문에 cnt[10] = 0$ 이다.

우리가 구할 질의의 수는 $10^5$ 개 이다. 이것을 매번 완전탐색으로 찾으면 무조건 시간초가가 나기 때문에 시간을 줄여야 하고 문제 제약에 항상 오름차순으로 데이터가 주어진다고 했기 때문에 cnt배열은 오름차순으로 정렬되어 있고 즉 $O(logn)$ 인 이분 탐색을 쓸 수 있다.

그렇다면 $k$번째 수를 어떻게 찾을까? cnt배열에서 lower_bound를 이용해서 위치를 찾는다. 찾은 위치를 idx라고 하자. 그렇다면 수 arr[idx]보다 작은 양수가 $cnt[idx]$개 있다는 뜻이다. lower_bound 함수의 특성상 cnt[idx - 1]은 무조건 cnt[idx]보다 작다. 그리고 k - cnt[idx - 1]은 k와 arr[idx - 1]사이에 있는 양수의 개수를 의미한다. arr[idx - 1]에서 (k - arr[idx - 1])만큼 더한다면 우리가 찾는 수를 구할 수 있다.

정답 코드

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

typedef long long ll;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, q; cin >> n >> q;
    ll arr[n + 1] = {0, }, cnt[n + 1] = {0, };
    for(int i = 1; i <= n; i++){
        cin >> arr[i];
        cnt[i] = arr[i] - i;
    }
    while(q--){
        ll k; cin >> k;
        int idx = lower_bound(cnt + 1, cnt + n + 1, k) - cnt;
        cout << arr[idx - 1] + k - cnt[idx - 1] << "\n";
    }
    return 0;
}