[Codeforces] Round #773 Div. 2
study/problemsolving

[Codeforces] Round #773 Div. 2

요즘 코드포스를 돌리고 있는데, 어렵다,, Div2 4개 푸는 걸 목표로 달리고 있다만, 계속해서 ABC를 풀거나 ABE를 풀거나(???)...

 

코포 결과

A. Hard Way

삼각형이 주어졌을 때, $(0, x)$ 점에서 삼각형에 닿지 않는 변의 길이를 구하는 문제이다.

그림을 몇 번 그려 보면, 삼각형의 한 변이 x축에 평행하고, 나머지 한 점이 그 변보다 아래에 있는 경우, x축에 평행한 변은 닿을 수 없다. 다행히 닿지 않는 변의 길이를 구하면 되니, 저 경우면 변의 길이를, 그렇지 않으면 0을 출력하면 된다.

이 그림의 경우 답은 3이 된다

 

B. Power Walking

$N$ 개의 파워업을 적당히 나눠서, 나눈 그룹마다 unique한 원소의 개수의 합을 최소화하는 문제이다.

이 때, $1$ 부터 $N$ 까지의 정수 $K$ 에 대해서, 그룹을 $K$개로 나눴을 때의 최솟값을 모두 구해야 한다.

예를 들어, $[1, 2, 2]$ 와 같이 3개의 파워업이 있다면,

$K=1$ 일 때 $\{1, 2, 2\}$ (2)

$K=2$ 일 때 $\{1\}, \{2, 2\}$ (1 + 1)

$K=3$ 일 때 $\{1\}, \{2\}, \{2\}$ (1 + 1 + 1) 로 정답은 2, 2, 3이 된다.

문제를 그리디하게 풀어보자. 처음에는 모든 것을 포함하므로, 중복되지 않는 원소의 개수가 된다.

만약 2 2 2 2와 같은 하나의 수로만 이루어진 배열의 경우, 나눌 때마다 1씩 증가하게 된다.

반면, 2 2 3 4와 같은 경우, $K=1$ 일 때는 3이지만, $K=2$일 때도 3이다. 2 2 | 3 4로 나눈 뒤, K가 증가할수록 1이 늘어난다.

그룹은 반드시 같은 것끼리 묶는 것이 최선이다.

따라서 (처음 상태에서 중복되지 않는 원소의 개수) 를 $A$ 라고 한다면, 답의 형태는 항상 $A$ 가 $A$ 번 나타난 뒤,  $N$ 까지 1씩 증가하는 형태를 띄게 된다.

( 문제를 풀 때 우선순위 큐로 생각해서 풀었다가 데였다.)

 

 

C. Great Sequence

배열이 주어지면, 배열에서 두 개의 원소를 서로 짝지어줘야 하고, 짝이 없다면 배열에 원소를 추가하며, 원소를 추가하는 최소 횟수를 구하는 문제이다.

문제에서 $x$ 가 주어지는데, 배열 안의 원소 $k$ 에 대해서 $(k, kx)$ 꼴로 짝을 지어주면 된다.

배열상의 순서는 중요하지 않으므로 정렬해준 뒤, 작은 수부터 탐색하며 $i$ 에 대해서 $xi$ 가 존재하는지의 여부를 따져가며 풀었다. 순회하면서 이전의 원소에 대해서 지워질 수 있으므로, 그 부분도 잘 생각하며 풀어야 한다.

 

D, E를 보고 문제이해는 했지만 손을 못 댔다.. 어제는 그래도 에듀포스 풀면서 E는 건드려서 풀었는데..D는 배열에 적절히 한 원소를 두 번 대입해서 tandem repeat으로 이뤄진 배열을 만드는 문제였고,E는 'l, r과 range를 적절히 조절하며 이분탐색을 섞어야 하나보다'까지만 생각했다. 조금 더 고민해봐야지