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

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

이전에 했던 결심 바로 취소하게 만든 E번 문제... 비트필드 + DP는 나한테 아직 버검다. 외판원순회 문제부터 풀고 와야하는데 내 머리에 아직 한계같다. 그리고 D번 문제는 구현까지 완료했는데, 자꾸 Runtime Error가 나와서 뭐가 문제인가 확인했을때, stack memory 초과였을때 드는 허탈함은 이루 말할 수 없다. 배열 선언을 heap 공간인 전역 변수에 선언하니까 바로 ACㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 이 문제플 풀면서 여러가지 많이 배운것 같다. 나머지 A, B, C는 그냥 간단한 문제.
이번 대회에서 배운 것은

1. c++의 stack 메모리 한계값
2. $O(nlogn)$의 약수 구하기 알고리즘
3. 에라스토테네스의 채 응용

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

A - Your First Judge (*7)

접기/펼치기

문제 설명
문자열 $S$가 주어진다. 이 문자열이 "Hello,World!"랑 일치하면 AC를, 아니면 WA를 출력하라.

문제 해설
설명이 필요한지?

정답 코드

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    string s; cin >> s;
    cout << (s == "Hello,World!" ? "AC" : "WA");
    return 0;
}

B - log2(N) (*68)

접기/펼치기

문제 설명
양의 정수 $N$이 주어진다. $2^k \le N$을 만족하는 최대 정수 $k$를 출력하라.

문제 해설
사실 문제 제목처럼 c++의 <cmath>헤더에 있는 log2()함수를 쓰면 쉽게 풀 수 있다. $k$는 log의 지수부분을 출력하면 된다. 여기서 주의해야할 점은 부동 소수점 오차이기 때문에 double보다 더 정확한 long double자료형을 써야 한다.

그런데 이 방법말고 이진수의 성질을 이용해서 쉽게 푸는 방법도 있다. 주어진 $N$을 7이라고 해보자. 이 수의 답은 $2$이다. 왜냐하면 $k = 3$인 경우 8이므로 $8 > 7$이고, 등식을 만족하지 않기 때문이다.
이때 이 7을 이진수로 나타내면 $111$이다. 그리고 $2^2$는 4이고, 4를 이진수로 나타내면 $100$이다. 어떤가? 감이 조금 잡히지 않는가? 이래도 잡히지 않는다면 다음 예시를 들어보자.

주어진 $N$이 이진수로 $100010$이라고 가정해보자. 그러면 이진수의 성질에 의해서 $100000 \le 100010$이다. 그리고 $100000$은 $2^5 = 32$이다. 즉 $N$이 $100010$이면 답은 $k = 5$이다.

즉 그냥 주어진 수의 MSB부터 세서, 1이 처음으로 나온 위치를 그냥 출력하면 된다. 이때 주의해야할 점은 LSB의 위치는 $0$이라는 점과 $N$의 범위가 $10^{18}$까지 이므로 $2^{60}$이 $10^{18}$보다 작은 값중에서 가장 크므로 60번째 자리부터 확인해야한다는 점이다. 1이 처음으로 나온 위치는 비트마스킹을 이용하면 쉽게 찾을 수 있다.

정답 코드

#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    long long n; cin >> n;
    for(int i = 60; i >= 0; i--){
        if(n & (1LL << i)){cout << i; break;}
    }
    return 0;
}

C - One More aab aba baa (*178)

접기/펼치기

문제 설명
문자열 $S$의 순열로 이루어진 문자열 중에서 $K$번째 사전순으로 작은 문자열을 출력하라.

문제 해설
이전에 풀었던 DP문제라고 생각 할 수 있지만 $1 \le |S| \le 8$ 이므로 그냥 next_permutation함수 사용하면 된다. $|S|$가 10개가 넘어가면 이 방법은 사용할 수 없고 DP를 사용해야 한다.
$S$를 정렬하고, 저 함수를 $K$번 수행해서 나온 문자열을 출력하면 된다.

정답 코드

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    string s; cin >> s;
    int k; cin >> k;
    sort(s.begin(), s.end());
    k--;
    while(k--){
        next_permutation(s.begin(), s.end());
    }
    cout << s;
    return 0;
}

D - Coprime 2 (*736)

접기/펼치기

문제 설명
$N$개의 양의 정수로 이루어져있는 수열 $A = (A_1, A_2, ..., A_N)$ 이 주어진다. 다음 조건을 만족하는 $1$부터 $M$까지 모든 정수 $k$를 찾아라.

• $1 \le i \le N$을 만족하는 모든 $i$에 대해서 $gcd(A_i, k) = 1$를 만족한다.

문제 해설
진짜 앞으로 10만이 넘는 배열은 그냥 전역 변수로 선언하려고 한다. 이 문제에서 너무 크게 데였다. 일단 이 문제의 조건을 보면 숫자 $1$은 무조건 가능하다는 것을 알 수 있다. 그리고 쉽게 알 수 있는 것은 모든 $A_i$에 대해서 각 숫자의 약수, 그 약수의 모든 배수들은 전부 조건을 만족하지 못한다는 것을 알 수 있다. $k$가 여러 $A_i$중 한 숫자의 약수면 $gcd()$는 그 약수값이 되기 때문이다. 그래서 각 $A_i$의 약수를 찾고, 그 약수와 그 약수의 모든 배수를 제외한 나머지 값을 출력하면 되는 문제이다.

이걸 어떻게 빠르게 풀 수 있을까? 위에서 풀이 방식을 보니까 에라스토테네스의 채 방법과 엄청나게 유사하다는 생각이 든다면 당신은 이 문제를 풀 수가 있다. 그렇지 않으면 에라스토테네스의 채를 공부하고 오면 다음번에 소수 찾는문제를 만났을 때 핵심 열쇠가 될 것이다.

약수를 찾는 알고리즘은 보통 그냥 $O(n)$방식으로 코딩하지만 수 $N$의 루트 값만큼만 찾으면 된다는 것을 안다면 시간복잡도를 $O(logn)$으로 줄일 수 있다. 주어진 $A_i$에 대해서 약수를 vector에 저장하고, 에라스토테네스의 채 방식으로 그 약수와 그 약수의 모든 배수를 제외해 나간다면 답을 구할 수 있다. 시간을 더 단축하기 위해서 약수를 찾았는데, 그 약수가 이미 제외되어 있다면 그 약수와 그 배수들은 이미 제외했기 때문에 제외하는 과정을 넘기면서 시간을 단축할 수 있다.

정답 코드

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

int f[100002];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, m; cin >> n >> m;
    for(int i = 0; i < n; i++){
        int num; cin >> num;
        vector<int> v;
        for(int j = 2; j * j <= num; j++){
            while(num % j == 0){
                v.push_back(j);
                num /= j;
            }
        }
        if(num > 1) v.push_back(num);
        for(auto x : v){
            if(f[x]) continue;
            for(int j = x; j <= m; j+=x) f[j] = 1;
        }
    }

    vector<int> ans;
    for(int i = 1; i <= m; i++){
        if(!f[i]) ans.push_back(i);
    }
    cout << ans.size() << "\n";
    for(auto x : ans) cout << x << "\n";

    return 0;
}