Codeforces Round #752 (Div. 2) A부터 D까지 업솔빙

Codeforces Round #752 (Div. 2) A부터 D까지 업솔빙

이번 대회에는 B번 1100 난이도까지 풀었지만 C번부터는 못풀었는데, 이 문제는 푸는 방법까지 알았는데 단 한가지 문장때문에 1시간을 뇌절하다가 못풀었다. 내가 푼 방식을 C번문제에서 설명할텐데, 내가 처음에 푼 코드와 정답 코드를 보면 이게 왜? 틀리지? 라는 생각을 이 글을 읽고 있는 사람 또한 알게 될 것이다. 마지막 D번 문제는 단순한 코드포스식 정수론이라서 업솔빙 할 것이다. 이번 대회에서 배운 것은

1. XOR연산과 홀수 짝수 반복 학습
2. 최소공배수와 최대공약수, 그리고 배수 약수 찾기 알고리즘
3. break문의 위험성
4. 수직선에서 나머지 연산의 기하학적 의미

A. Era (*800)

접기/펼치기

문제 설명
소호는 정수 $a_1, a_2, ..., a_n$로 이루어진 수열을 가지고 있다. 그는 다음 연산을 몇번이고도 수행할 수 있다.(0번 수행할 수도 있다.)

• 아무 양수 $k$를 선택한다. (매 연산마다 다른 숫자를 선택하라 수 있다.)
• 수열에서 아무 위치를 선택하고 숫자 $k$를 이 위치에 삽입한다.
• 이 단계에서 수열 $a$가 변화했고, 다음 연산은 이 바뀐 수열에서 수행한다.

예를 들면 $a = [3, 3, 4]$ 가 있고, $k = 2$를 선택한다. 이후 그가 얻을 수 있는 수열은 다음과 같다. $[2, 3, 3, 4], [3, 2, 3, 4], [3, 3, 2, 4], [3, 3, 4, 2]$

이 수열은 다음 조건을 만족해야 한다.

• 각 $1 \le i \le |a|, a_i \le i$ 즉 $i$번째 있는 원소가 반드시 $i$보다 작거나 같은 수여야 한다.

이 문제의 목표는 이 조건을 만족하는 수열을 만들기 위해서 필요한 연산의 최소 횟수를 구하는 것이다.

문제 해설
직관적으로 풀 수 있는 문제, 만약 3번째 위치에 숫자 8이 있다면 조건을 만족하기 위해서 앞에 숫자 $3, 4, 5, 6, 7$ 을 추가해야 한다. 즉 원소 $a_i$랑 같은 index로 이동하게 앞에 숫자를 추가해야 한다는 것이다. 원소 $a_i$가 index $i$번째 원소라면 앞에 숫자를 추가해야 하는 횟수는 $a_i - i$로 구할 수 있다. 즉 모든 원소를 순회하면서 $a_i - i$값을 구하고 이 값중 최대값을 구하면 답이 된다.

최대값을 구하는 이유는 최솟값을 구하면 뒤에 넣어야 하는데 못넣는 경우가 생기기 때문에 최대값을 구한다. 만약에 최대값이 7이고 앞에 3번 추가해야하는 원소가 또 있다면 앞에 3번 원소를 추가하는 동안 최대값을 가지고 있는 원소 또한 연산 횟수가 3번 줄어서 어짜피 전체 필요한 최소 연산은 똑같다.

정답 코드

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        int n; cin >> n;
        int ans = -1;
        for(int i = 1; i <= n; i++){
            int num; cin >> num;
            ans = max(ans, num - i);
        }
        cout << ans << "\n";
    }
    return 0;
}

B. XOR Specia-LIS-t (*1100)

접기/펼치기

문제 설명
소호는 정수 $a_1, a_2, ..., a_n$로 이루어진 수열을 가지고 있다. 이 수열 $a$를 $a$의 원소가 한개 혹은 그보다 더 많이 포함되어 있는 연속적인 subarray로 만들어야 한다. $k$를 최종적으로 만들어진 subarray의 개수라고 하고, $h_1, h_2, ..., h_k$를 각각 대응되는 subarray의 LIS의 길이이다.

예를 들어 $[2, 5, 3, 1, 4, 3, 2, 2, 5, 1]$ 을 $[2, 5, 3, 1, 4], [3, 2, 2, 5], [1]$ 로 나눌 수 있고, $h = [3, 2, 1]$ 이다.

이 문제의 목표는 주어진 배열 $a$을 쪼개서 $h_1, h_2, ..., h_k$의 XOR값을 $0$으로 만들 수 있는지 판별하는 것이다.

문제 해설
XOR의 성질을 알고 있다면 배열의 길이가 짝수라면 무조건 XOR값이 0이 될수 있다는 것을 알 수 있다. XOR은 같은 수가 짝수개 있다면 값이 0이 되는데, 주어진 배열을 길이가 1인 subarray로 나눈다면 모든 값이 $h_i$ 값이 1인 수가 짝수개 나오기 때문에 XOR값이 0이 된다.

주어진 배열의 길이가 홀수라면 길이를 1로 나눠도 1의 개수가 홀수개이기 때문에 XOR값이 1이된다. 하지만 LIS의 성질을 이용하면 쉽게 구할 수 있다. LIS는 오름차순으로 이루어진 원소의 개수를 새는 것인데, 연속하는 두 수를 선택해서 이 수가 내림차순으로 되어 있다면 이 값은 1이 된다. 즉 주어진 수열에서 연속하는 두 원소가 내림차순으로 되어 있으면 이 두수를 제외하고 나머지 원소를 1개로 나누고 이 두 수를 하나로 묶어서 LIS값이 1로 만들면 총 1의 개수가 짝수개가 되기 때문에 XOR값을 0으로 만들 수 있다.

즉 우리가 찾아야 하는 것은 연속하는 두 수가 내림차순으로 되어있거나 전체 배열의 길이가 짝수인지 아닌지 판별하면 된다.

정답 코드

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        int n; cin >> n;
        int arr[n];
        for(auto& x: arr) cin >> x;
        bool flag = false;
        for(int i = 0; i < n - 1; i++){
            if(arr[i] >= arr[i + 1]) flag = true;
        }
        cout << (n % 2 == 0 || flag ? "YES" : "NO") << "\n";
    }
    return 0;
}

C. Moamen and XOR (*1300)

접기/펼치기

문제 설명
소호는 정수 $a_1, a_2, ..., a_n$로 이루어진 수열을 가지고 있다. 그는 다음 연산을 주어진 수열에 원소가 없을 때 까지 반복할 것이다. $1 \le i \le |a|$ 인 index $i$를 선택하고 $a_i$가 $(i + 1)$ 로 나누어 떨어지지 않으면 그 원소를 수열에서 삭제한다. 연산을 반복하면서 수열 $a$는 계속 바뀌고 다음 연산은 이 바뀐 수열에 대해 수행한다.

위에서 주어진 연산을 계속 반복해서 수열에 있는 모든 원소를 제거할 수 있는지 결정해야 한다.

문제 해설
이게 대망의 그 문제이다. 마지막 break 때문에 계속 틀리게된 문제, 접근방법은 완벽히 맞았고 구현까지 끝내서 정답만을 기다리고 있었지만 test case의 작동방식을 파악하지 못해서 계속 틀렸다.

수열을 보면 맨 처음에 알 수 있는 것은 맨 앞에 있는 원소가 2의 배수이면 절대 사라지지 않는다는 점이다. 이 관찰로 $a_1$은 3의 배수이면 절대 사라지지 않고, $a_2$는 4의 배수이면 사라지지 않는다고 추측할 수 있다.

여기서 더 나아갈 수 있는데, 앞에 있는 원소가 사라진다면 뒤에 있는 원소가 앞으로 이동하면서 사라질 가능성이 생긴다는 것이다. 하지만 이렇게 해도 절대 사라지지 않는 경우가 있는데, 그 경우를 찾으면 끝난다. 만약 $a_2$가 끝까지 남아있으려면 어떤 수여야 할까? $a_2$ 앞에 있는 수는 $2, 3, 4$ 으로 나누어 떨어지면 안된다. 즉 $2, 3, 4$ 모든 수로 나누어 떨어진다면 이 수는 절대 사라지지 않을 것이다. 즉 $a_2$가 $2, 3, 4$의 최소공배수의 배수면 이 수는 절대 사라지지 않는다.

맨 앞에서 차례대로 $2$, $3$, $4$, $...$ 계속 최소공배수를 구하면서 이 수로 나누어 떨어지는 항이 있다면 바로 false를 한다음에 빠져나오면 된다.

내가 실수한 부분은 숫자 입력을 받는 도중에 break를 한 것이다. cin 구문을 최소공배수를 구하는 for문에 넣고 조건을 만족하면 break를 하는 방식으로 했는데, 이렇게 하면 아직 뒤에 입력을 기다리는 테스트케이스를 기다리지 않고 그 테스트 케이스를 종료해서 남아있는 테스트 케이스가 다음 테스트케이스에 영향을 미쳐서 계속 답이 맞지 않았던 것이다.

이 실수를 하지 않으려면

1. 그냥 모든 원소를 배열에 담고 배열의 원소에 대해 반복문을 한다.
2. false인 조건을 찾으면 그냥 저장을 하고 일단 모든 원소가 입력될때 까지 반복문을 돌린다.

가 필요하다.

정답 코드

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        int n; cin >> n;
        int arr[n];
        for(auto& x: arr) cin >> x;
        bool flag = true;
        int lm = 2;
        for(int i = 0; i < n; i++){
            lm = lcm(lm, i + 2);
            if(arr[i] % lm == 0){
                flag = false;
                break;
            }
        }
        cout << (flag ? "YES" : "NO") << "\n";
    }
    return 0;
}

D. Moderate Modular Mode (*1600)

접기/펼치기

문제 설명
두 짝수 $x, y$ 가 주어진다. 다음 조건을 모두 만족하는 수 $n$을 찾아라.

• $1 \le n \le 2 \cdot 10^{!8}$ 그리고 $n\;mod\;x= y\;mod\;n$

문제 해설
번뜩이는 아이디어를 요구하는 코드포스식 ad=hoc 느그 정수론 문제이다. 일단 $x, y$가 제한이 없으므로 누가 큰지 조건을 나눠서 문제를 풀어야 할 것 같다.

1. $x > y$ 인 경우
   $n = x + y$라고 하면
   왼쪽 항은 $(x + y)\;mod\;x = x\;mod\;x + y\;mod\;x = y (x > y)$ 이다.
   오른쪽 항은 $y\;mod\;(x + y) = y$ 이다.
   즉 $n = x + y$이면 성립한다.

2. $x \le y$ 인 경우
   문제에서 직관을 운운하는데, 한번 보자. 일단 $a \; mod \; b$를 하면 $a > b$ 일때 수직선 상에서 $b - qa$ 의 최소거리를 의미한다. 이때 $q$는 임의의 양수이다. 그러면 $(x \le y)$ 일때 $y \; mod \; x$를 하면 $x$를 최대한 $y$가 안넘는 선에서 배수를 통해서 땡기고 남은 두 수 사이의 거리가 나올 것이다. 그리고 $x$를 최대한 땡긴 수를 $x'$라고 하면 답은 $x'$와 $y$의 중간지점이다. 왜냐하면 $x, y$가 짝수라는 조건에서 $2$를 나눌때 정학히 절반이 되기 때문이다.
   즉 $n = y - (y\;mod\;x)/2$ 가 답이다.

다음 수직선을 보면 더 이해가 쉬울 것이다.

정답 코드

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        int x, y; cin >> x >> y;
        cout << (x > y ? x + y : y - (y%x)/2) << "\n";
    }
    return 0;
}