Codeforces 첫 도전 후기 (Div. 4 Round #1090)

개요

 

알고리즘 문제해결 자체는 백준 온라인 저지 사이트를 통해 많이 해보았지만, 다른 사용자들과 경쟁하는 경험은 거의 없는 상태였다.

 

그런 경험을 쌓아보고 싶어 예전에 이름만 알고 사용해본 적은 없던 Codeforces 사이트를 가입한 후 둘러보던 중 가장 난이도가 낮다는 Div.4 라운드가 열릴 예정이라는 것을 발견하였고, 참가하게 되었다.

 

문제는 여기서 확인할 수 있다.

https://codeforces.com/contest/2218

Dashboard - Codeforces Round 1090 (Div. 4) - Codeforces

 

 

 

A번~C번은 python으로 풀었고, D번~F번은 java로 풀었다.

 

문제

 

A. The 67th Integer Problem

 

정수 x(-67 <= x <= 67) 가 주어지면, min(x, y)가 최댓값을 갖게 하는 y(-67 <= y <= 67) 를 출력하면 된다.

y가 x 이상일 때 min(x, y)가 최대가 될테니, 입력받은 x를 그대로 출력해도 되고, 67만 계속 출력해도 되고...

for _ in range(int(input())):
    print(input())

---

B. The 67th 6-7 Integer Problem

 

7개의 정수가 주어지면, 그 중 6개를 음수로 바꾸었을 때 가능한 최댓값을 출력하면 된다.

7개의 정수 중 최댓값을 제외한 나머지 6개를 음수로 바꾸면 최댓값을 만들 수 있다. 

for _ in range(int(input())):
    a = list(map(int, input().split()))
    print(2 * max(a) - sum(a))

---

C. The 67th Permutation Problem

 

정수 n이 주어지면, 3개의 원소를 갖는 블록들로 분할한 후 각각의 블록들의 중앙값을 모두 더했을 때 최댓값이 되도록 하는 길이 3n의 순열을 출력하면 된다.

 

가장 큰 값(3n)은 절대로 중위값이 될 수 없으므로, 중위값을 가능한 크게 만들기 위해서는 그것의 바로 다음으로 작은 값(3n - 1)을 중위값으로 만들어 주어야 한다. 그렇게 쭉 따라가다 보면, {1, 3n - 1, 3n}, {2, 3n - 3, 3n - 2}, ... 로 블록들을 구성할 수 있다.

... 증명은 못하겠는데, 이렇게 하면 되겠지 싶어서 내보았고 정답을 받았다.

import sys
input = sys.stdin.readline
 
for _ in range(int(input())):
    n = int(input())
    for i in range(n):
        print(i + 1, 3 * n - 2 * i - 1, 3 * n - 2 * i, end=" ")
    print()

---

D. The 67th OEIS Problem

 

정수 n이 주어지면, 연속한 두 수의 최대공약수가 모두 유일한 수열 a를 출력하면 된다.

소수(2, 3, 5, 7, ...)를 생각해 보자. 2x3과 3x5의 최대공약수는 3이고, 3x5와 5x7의 최대공약수는 5이다.

 

... 이렇게 연속한 두 소수의 곱으로 이루어진 수열을 구성하면, 최대공약수를 유일하게 만들 수 있다. 어차피 1만번째 소수가 10의 18승을 넘진 않을 테니...

import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        boolean[] notPrime = new boolean[200001];
        for(int i = 2; i * i < 200001; i++)
            if(!notPrime[i])
                for(int j = i; i * j < 200001; j++) {
                    notPrime[i * j] = true;
                }
 
        List<Long> prime = new ArrayList<>();
        prime.add(1L); prime.add(1L);
        for(int i = 2; i < 200001; i++)
            if(!notPrime[i]) prime.add((long)i);
 
        int t = Integer.parseInt(br.readLine());
        while(t-- > 0) {
            int n = Integer.parseInt(br.readLine());
            for(int i = 1; i <= n; i++) {
                bw.write(prime.get(i) * prime.get(i - 1) + " ");
            }
            bw.write("\n");
        }
 
        bw.close();
    }
}

---

E. The 67th XOR Problem

 

길이 n과 수열 a가 주어지면, 원소 하나를 골라 나머지 모든 원소에 xor한 후 고른 원소를 제거하는 연산을 원소가 하나 남을 때까지 반복했을 때 가능한 최댓값을 출력하면 된다.

 

마지막 연산 직전 원소가 2개 남았을 때를 생각해보자. 두 수 x와 y에는 n-2개의 원소가 xor되어 있는 상태일 것이다.

여기서 x와 y에 xor 연산을 취한다면, xor되어 있는 n-2개의 원소는 상쇄되어 없어질 것이다.

 

따라서, 그냥 수열 a의 두 수를 xor했을 때 가능한 최댓값을 출력하면 된다.

시간 제한이 넉넉하기 때문에 모든 경우를 찾는 O(n^2)도 충분히 가능하다.

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int t = Integer.parseInt(br.readLine());
        while(t-- > 0) {
            int n = Integer.parseInt(br.readLine());
            int[] a = new int[n];
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int i = 0; i < n; i++)
                a[i] = Integer.parseInt(st.nextToken());

            int ans = 0;
            for(int i = 0; i < n; i++)
                for(int j = i + 1; j < n; j++)
                    ans = Math.max(ans, a[i] ^ a[j]);

            System.out.println(ans);
        }
        bw.close();
    }
}

---

F. The 67th Tree Problem

 

정수 x와 y가 주어지면, 자신을 포함해 서브트리에 속한 노드의 개수가 짝수를 이루는 노드가 x개, 홀수를 이루는 노드가 y개가 되도록 하는 트리를 구성해 그 트리의 간선들의 시작점과 끝점을 출력하면 된다.

 

루트(1번) 노드는 항상 x + y개의 노드를 가지고 있고, 리프 노드는 항상 1개의 노드(자기 자신뿐)를 가지고 있다. 즉, 짝수 노드 하나가 있기 위해서는 반드시 하나 이상의 홀수 노드가 있어야 하기 때문에, 짝수 노드의 개수는 홀수 노드의 개수를 초과할 수 없다.

 

일단 루트 노드는 무조건 x + y이니, x + y가 짝수인데 x = 0이거나, x + y가 홀수인데 y = 0이거나, 루트 노드를 제외하고 x > y인 경우엔 "NO"를 출력하고, 그렇지 않다면 아래 사진처럼 트리를 구성해 주면 된다.

x = 4, y = 6인 경우

 

 

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int t = Integer.parseInt(br.readLine());
        while(t-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            // x: even, y = odd
            int x = Integer.parseInt(st.nextToken()), y = Integer.parseInt(st.nextToken());
            if((x + y) % 2 == 0) x--;
            else y--;

            if(x < 0 || y < 0 || x > y) {
                bw.write("NO\n");
                continue;
            } else {
                bw.write("YES\n");
                int k = 2;
                for(int i = 0; i < x; i++, k += 2) {
                    bw.write(1 + " " + k + "\n");
                    bw.write(k + " " + (k + 1) + "\n");
                }
                for(int i = 0; i < y - x; i++, k++)
                    bw.write(1 + " " + k + "\n");
            }
        }
        bw.close();
    }
}

 

 

 

라운드 종료 후

 

아쉽게도 마지막 G번은 아이디어까진 떠올랐으나 구현하던 도중 시간이 다 되었다. ㅠㅠ

 

그렇게 총 6문제를 풀었고, 왜 이렇게 점수를 많이 주나 했는데 찾아보니 처음 6개의 라운드는 배치고사 같은 느낌으로, 기본적으로 주는 추가 점수가 있다고 한다.

 

가장 쉬운 난이도라고 해서 사실 살짝 만만하게 봤는데, 이것조차 후반 문제들은 꽤나 어렵게 느껴졌다. 그럼 그 상위 디비전은....

... 앞으로도 더 열심히 해야겠다.

 

이게 블로그의 첫 글이라 뭔가 이상한데, 앞으로 백준에서 푼 문제나 학교에서 배운 것 등등을 여기에 올려보아야겠다.