AtCoder Beginner Contest 234 A부터 E까지 업솔빙

AtCoder Beginner Contest 234 A부터 E까지 업솔빙

시간이 맞아서 최초로 실제 대회에 참여한 문제셋이다. 그래서 그런지 더욱더 업솔빙에 최선을 다했고, 풀지 못했던 E와 기를 쓰고 겨우 풀었던 D번 문제가 생각보다 쉬운 문제였다는 난이도 선정에 아쉬워하기도 했다. 하지만 처음 Atcoder 대회에서 퍼포먼스가 *825정도 나왔다는 점에서 나는 매우 만족한다. 이제 atcoder를 계속 연습하면서 brown 등급의 문제는 거뜬하게, green등급은 기를 쓰고 풀어서 겨우 풀 수 있는 수준까지가 1차 목표이다. 이번 대회에서 배운 것은

1. 재귀함수로 이진수 빠르게 구하기
2. 다양한 자료구조 생각하기
3. 때로는 모든 경우의 수를 다 구하는 것이 가장 좋은 해법이다.

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

A - Weird Function (*7)

접기/펼치기

문제 설명
함수 $f$를 다음과 같이 정의하자. $f(x) = x^2 + 2x + 3$
정수 $t$에 대해서 $f(f(f(t) + t) + f(f(t)))$ 값을 구하라.
답은 항상 $2 \times 10^9$ 를 넘지 않는 정수이다.

문제 해설
$f(x)$ 함수를 구현한후 문제에서 주어진 대로 식을 작성해서 출력하면 된다.

정답 코드

#include <iostream>
using namespace std;

int f(int x){
    return x * x + 2 * x + 3;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    cout << f(f(f(t) + t) + f(f(t)));
    return 0;
}

B - Longest Segment (*46)

접기/펼치기

문제 설명
2차원 평면에 점 $N$개가 주어진다. $i$번째 점의 좌표는 $(x_i, y_i)$ 이다.
이 점들 중에서 두개의 점 사이의 최대 거리를 구하라.

문제 해설
이중 반복문 한다음에 두 점사이의 거리를 구하는 공식인 $\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$를 모든 두 점 사이에 적용한 다음에 최대값을 구하면 된다.

정답 코드

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


int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n; cin >> n;
    double a[n][2];
    for(int i = 0; i < n; i++) cin >> a[i][0] >> a[i][1];
    double ans = -1e9;
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            double dx = a[i][0] - a[j][0];
            double dy = a[i][1] - a[j][1];
            ans = max(ans, sqrt(dx * dx + dy * dy));
        }
    }
    cout.precision(8);
    cout << fixed << ans;
    return 0;
}

C - Happy New Year! (*155)

접기/펼치기

문제 설명
10진법으로 숫자 $0$과 $2$로만 이루어진 양수가 있을 때, $K$번째 작은 수를 찾아라.

문제 해설
일단 문제에 있는 $K = 923423423420220108$ 인 경우 답을 보고 나서 일단 평소의 수학처럼 답을 구하면 절대 안될것 같다는 생각을 했다. 그래서 $K = 10$까지 나올 수 있는 답을 모두 나열해 보니까 바로 규칙이 나왔다. 그냥 $K$를 이진수로 표현했을 때 $1$을 $2$로 바꾸면 되는 것이었다. 이런 센스는 결국 비슷한 문제를 계속 풀어봐야 생기는 것 같다. 따라서 못풀었다고 낙심하지말자. 나도 이와 비슷한 문제 codeforces에서 나왔을 때 못풀었다.

정답 코드

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

typedef long long ll;

void func(ll x){
    if(x > 1) func(x / 2);
    cout << (x % 2 ? 2 : 0);
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll k; cin >> k;
    func(k);
    return 0;
}

D - Prefix K-th Max (*503)

접기/펼치기

문제 설명
숫자 $(1, 2, ..., N)$으로 이루어진 순열 $P = (P_1, P_2, ..., P_N)$과 양의 정수 $K$가 주어진다.
각 $i = K, K + 1, ..., N$에 대해서 다음 조건에 만족하는 수를 찾아라.

• $P$의 첫번째부터 $i$번째 원소 중에서 $K$번째로 큰 수

문제 해설
문제를 보고 예제코드를 통해서 숫자를 넣고 뺐을 때 몇가지 알아낸 정보가 있다.

1. 맨 처음에 처음부터 $K$개 원소를 묶었을 때, 가장 작은 원소가 $K$번째 작은 원소이다.
2. $K$번째 작은 원소보다 더 작은 값이 들어왔을 경우, 답에 영향을 끼치지 않고 더 큰 값이 들어왔을 경우 답이 바뀐다.

내가 처음에 고민했던 것은 $N$의 제한이 $5 \times 10^5$ 인데, $K$개 원소가 들어간 배열을 어떻게 항상 정렬된 상태로 유지할까? 였다. 왜냐하면 1번 정보에 의하면 항상 정렬된 상태로 유지되어야 그 집합의 가장 작은 원소를 쉽게 찾을 수 있기 때문이다. 일반 vector자료구조에서는 삽입과 삭제가 $O(N)$ 이기때문에 시간제한에 맞출 수 없다. 따라서 나는 $set$과 우선순위 큐를 생각했다.

나는 처음 생각한 set을 사용해서 문제를 풀었지만 우선순위 큐로 푸는 것이 더 나은 풀이라고 생각해서 소개한다. $P$의 맨 처음부터 $K$개의 원소를 우선순위 큐에 넣으면 맨 위에 가장 작은 원소가 있을 것이라고 생각하지만 C++의 우선순위 큐는 기본적으로 MAX-heap이기 때문에 맨 위에 가장 큰 원소가 있다. 따라서 이 문제를 해결하기 위해서는

1. 우선순위 큐를 다음과 같이 선언한다. priority_queue<int, vector<int>, greater<int>>
2. 원소에 마이너스를 붙여서 담는다.
   나는 2번 방법을 사용했다.

일단 맨 위에 있는 숫자가 첫번째 답이므로 출력, 그 다음에는 현재 맨 위에 있는 숫자보다 값이 작은 원소가 다음 차례에 들어오면 답에 아무 영향을 미치지 않기 때문에 큐에 넣지 않는다. 반대로 현재 맨 위에 있는 숫자보다 값이 큰 원소가 다음 차례에 들어오면 현재 맨 위에 있는 원소는 필요 없고 다음 원소는 답에 영향을 미치기 때문에 다음과 같이 한다.

• 우선순위 큐의 맨 위에 있는 값을 빼고, 다음 차례 원소를 넣는다.

그러면 바뀐 큐의 맨 위 원소는 그 우선순위 큐의 현재 가장 작은 값이 있을 것이므로 답의 조건에 만족한다. 비교를 할때 큐에 있는 원소는 음수를 붙여서 비교하고 음수를 붙여서 넣어야 한다는 점을 잊지말자.

정답 코드

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, k; cin >> n >> k;
    int a[n];
    for(auto& x : a) cin >> x;
    priority_queue<int> pq;
    for(int i = 0; i < k; i++) pq.push(-a[i]);
    cout << -pq.top() << "\n";
    for(int i = k; i < n; i++){
        if(-pq.top() < a[i]){
            pq.pop();
            pq.push(-a[i]);
        }
        cout << -pq.top() << "\n";
    }
    return 0;
}

E - Arithmetic Number (*899)

접기/펼치기

문제 설명
다음 조건을 모두 만족하는 양의 정수 $n$을 산술 숫자 라고 하자.

• $n$은 10진법으로 써있고, 0으로 시작하지 않을 때 $d_i$를 $n$의 맨 앞자리 부터 $i$번째 숫자라고 하자. $k$는 숫자 $n$의 자릿수라고 할 때, $(d_2 - d_1) = (d_3 - d_2) = \cdots = (d_k - d_{k - 1})$ 을 만족한다.
  • 이 조건은 수열 $(d_1, d_2, ..., d_k)$ 가 산술 평균을 이룬다고 다시 쓸 수 있다.
  • 만약 $n$이 한자리 정수이면 이 또한 산술 숫자라고 한다.

예를 들어 $234, 369, 86420, 17, 95, 8, 11, 777$은 산술 숫자지만 $751, 919, 2022, 246810, 2356$은 아니다.
$X$보다 작지 않은 최소 산술 숫자를 구하라.

문제 해설
처음에 이 문제를 접했을 때 어떻게 하면 주어진 수를 요리하고 규칙을 세워서 이 문제를 풀지? 라는 생각을 했다. 이전까지 계속 규칙을 찾아서 구현을 하는 문제만 나왔기 때문이다. 이 문제는 이전에 내가 풀었던 문제처럼 규칙에 맞는 수를 $1$부터 $10^{17}$ 까지 모두 구한다음에 lower_bound()를 이용해서 조건에 맞는 수를 찾으면 된다. 엄청 많아보일것 같다고 생각하지만 생각을 조금만 해보면 그리 많지 않다는 것을 알게 된다.

1. 맨 처음자리 숫자는 무조건 $1$부터 $9$까지여야 한다.
2. 맨 처음자리 숫자부터 시작해서 공차, 즉 $d_i$가 $-9$부터 $8$까지여야 한다.
3. 전체 자릿수는 $1$부터 $18$자리 까지이다.

이 조건을 만족하는 수를 모두 구하면 $9 \times 18 \times 18 = 2916$ 개이다. 하지만 이 조건만으로는 반례가 있는데, $40-4$과 같은 경우도 있기 때문이다. 그렇기 때문에 다음 조건을 추가해야 한다.

• 모든 자릿수의 숫자는 $0$ 부터 $9$까지여야 한다.

전체 경우의 수를 모두 for문으로 찾되, 마지막 조건에 맞지 않는 숫자는 제외하는 방식으로 구하면 전체 산술 숫자를 구할 수 있다. $X = 10^{17}$ 이면 답은 $111111111111111111$ 이므로 long long type를 벗어나지 않는다.

정답 코드

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

typedef long long ll;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll x; cin >> x;
    set<ll> s;
    for(int i = 1; i < 10; i++){
        for(int j = -9; j < 9; j++){
            string str;
            int dig = i;
            for(int k = 1; k <= 18; k++){
                str += (dig + '0');
                s.insert(stoll(str));
                dig += j;
                if(dig < 0 || dig > 9) break;
            }
        }
    }
    cout << *(s.lower_bound(x));
    return 0;
}