[CodeForces] #818 (Div.2) A~C 업솔빙

---

안녕하세요 Gliver 입니다.

이번 글은 코드포스 #818 (Div.2) 에 대해 업솔빙하는 글입니다.

 

이번 대회는 망했다.. C번을 풀다가 대회가 끝나 버렸다.

 

A번

  - GCD와 LCM을 잘 알고 있다면 빠르게 풀 수 있는 문제이다.

  - 처음에 접근을 잘 못해서 A번부터 말렸었다.  

B번

  - 테스트케이스가 친절해서 쉽게 풀 수 있었다.

  - 하지만, 증명은 꽤 어려운 문제인 것 같다.

C번

  - 처음에 잘못된 아이디어를 떠올려서 말린 문제이다.

  - 결국 끝나고 1분 후에 코드를 완성하였는데 그때는 이미 늦었다.

    사실, C번까지 풀었다 해도 잘한 라운드는 아닌듯 하다.

 

 

 

A. Madoka and Strange Thoughts

$\frac{lcm(a,b)}{gcd(a,b)} \leq 3$ 의미를 어떻게 해석하는지가 관건인 문제이다.  

 

처음에 $lcm(a,b)$은 $a, b$를 소인수 분해 했을 때 합집합, $gcd(a, b)$ 소인수 분해 했을 때 교집합이라는 의미로 접근해보고,
식 $a \times b = lcm \times gcd$ 를 이용해 $\frac{lcm^2(a,b)}{a \times b} \leq 3$ 으로 식 변형도 해서 접근해보았다.  
지금 생각해보니, $\frac{a \times b}{gcd^2(a,b)} \leq 3$ 으로 식 변형을 하면 쉽게 풀 수 있었을 것 같다.

 

다시 돌아와서 생각해보니, $a$와 $b$의 관계에 대해서 생각하면 쉽게 풀 수 있는 문제였다.

즉, $a$와 $b$가 1의 배수, 2의 배수, 3의 배수 관계일 때 문제의 조건을 만족한다. 

 

1의 배수일 때

  - $n$만큼의 쌍이 존재한다.

2의 배수일 때

  - $a < b$ 인 경우에 $\lfloor \frac{n}{2} \rfloor$ 만큼의 쌍이 존재한다.

  - 따라서 $a > b$ 인 경우까지 고려하면, $2 \times \lfloor \frac{n}{2} \rfloor$ 만큼의 쌍이 존재한다.

3의 배수일 때

  - 2의 배수일 때와 동일한 로직으로 구하면 $2 \times \lfloor \frac{n}{3} \rfloor$ 만큼의 쌍이 존재한다.

 

 

 

 

 

B. Madoka and Underground Competitions

모든 부분 공간 $1 \times k$ 또는 $k \times 1$ 에 적어도 1개의 'X'가 있도록 $n \times n$ 공간을 구성하는 문제이다.

단, 'X' 문자의 개수가 최소가 돼야 한다.

 

테스트케이스 3번째를 보면 $k \times k$ 공간을 만들고, $n \times n$ 공간에 똑같이 나열했다는 것을 알 수 있다.  

 

$k \times k$ 공간을 조건에 맞게 만들었다는 가정하에 이를 $n \times n$ 공간에 나열하면 문제의 조건을 만족하는지 알아보자.

$k \times k$ 공간이 조건을 만족한 상태에서 이를 오른쪽 공간에 붙여 넣어 보자.
기존에 'X'의 좌표가 $(y, x)$라면 $(y, x+k)$ 지점에 'X'가 새로 생기는 것이다.
(아래로 붙이는 경우도 비슷한 원리로 동작한다)

부분 공간 $k \times k$은 이미 조건을 만족하므로, 전체 공간 $n \times n$이 조건을 만족하는지 살펴보자.
즉, $0 \leq \alpha \leq k$ 인 $\alpha$에 대해, 부분 공간 $(y, \alpha+1 \sim \alpha+k)$이 조건을 만족하는지 살펴보자.
  - $(y, x)$에 'X'가 있다면 $(y, x+k)$에도 'X'가 있을 것이다.  
  - $(y, x)$에 있는 'X'로 인해서 $\alpha+1 \leq x$ 인 경우, 즉 $x$에 대해 $x \ge \alpha+1$인 경우의 조건을 만족한다.
  - $(y, x+k)$에 있는 'X'로 인해서 $x+k \leq \alpha+k$인 경우, 즉 $x$에 대해 $x \leq \alpha$인 경우의 조건을 만족한다.
  - 따라서, $k \times k$ 공간에서 어떤 $x$ 좌표에 'X'가 있더라도 $\alpha$가 $0 \leq \alpha \leq k$인 경우는 상관없다는 것이다.

이는 $k \times k$ 공간을 아래쪽 공간에 붙여 넣는 경우도 동일하게 증명하면 된다.

 

따라서, 우리는 $k \times k$ 공간만 조건에 맞게 만들면 문제를 해결할 수 있다.

$k \times k$ 공간에 문제의 조건을 만족하며 최소한의 'X'를 배치해보자. 
각 행에는 1개의 'X'를 놓으면서, 이미 놓았던 열을 피해서 'X'를 놓으면 된다. (B1.cpp)
이렇게 배치하면 $k$개의 'X'를 사용하면서 문제의 조건을 만족할 수 있다. 

이를 수행하는 가장 간단한 방법을 대각선 정보를 이용하는 것이다. (B2.cpp)

 

$(r, c)$에는 무조건 'X'를 넣고 위의 로직을 수행하면 답을 구할 수 있다.

 

 

 

$x, y$ 좌표의 합 (i+j)이 같으면 같은 대각선을 의미한다.

만약, 좌표의 범위를 넘어선 경우에도 같은 대각선으로 취급하고 싶다면 (i+j) % k이 같으면 같은 대각선으로 처리하면 된다.

참고로, 여기서 k는 2차원 공간의 $x$좌표의 크기를 의미한다.

 

 

 

C. Madoka and Formal Statement

크기가 $n$인 배열 $a, b$가 주어졌을 때, 배열 $a$를 $a_i := a_i + 1$ 연산을 통해서 배열 $b$로 만들 수 있는지 판단하는 문제이다. 

단, $a_i := a_i + 1$ 연산은 $a_i \leq a_{i+1}$인 경우에 가능하다.

 

풀이1

먼저, $a_i$ 가 $b_i$가 되려면 어떻게 해야 하는지 살펴보자.  

$a_i$는 연산을 통해서 $a_i$ 이상인 숫자가 될 수 있다. 즉, $a_i > b_i$라면 $a_i$가 $b_i$가 되는 것은 불가능하다.

 

그렇다면, 모든 $i$에 대해서 $a_i \leq b_i$인 경우에는 어떻게 되는지 살펴보자.

$a_i \leq b_i$인 경우에 연산을 통해서 될 수 있는 $a_i$의 후보 $a_{i*}$를 살펴보자.
연산을 통해서는 증가밖에 안 되니 당연히 $a_i$ 이상인 수가 될 수 있다.  ($a_i \leq a_{i*}$)
$a_{(i+1)*} \leq b_{i+1}$를 만족해야 하기 때문에 $a_{i*}$ 또한 $a_{(i+1)*}+1$을 초과할 수 없다.  ($a_{i*} \leq b_{i+1}+1$)

따라서, $a_{i*}$은 $a_i \leq a_{i*} \leq b_{i+1}+1$을 만족하고, $b_i \in a_{i*}$를 만족해야 한다.
사실, $b_{i+1}+1 \leq a_i$인 경우에는 $a_{i*} = a_i$이기 때문에 $a_i \leq a_{i*} \leq max(a_i, \ b_{i+1}+1)$이 정확한 표현이다.  

즉,  $a_i \leq b_i \leq max(a_i, \ b_{i+1}+1)$을 만족하지 않으면 $a_i$는 $b_i$가 될 수 없다.
이 식 자체가 $a_i > b_i$인 경우를 거르기 때문에 이 조건문 하나만 사용해도 된다.

 

 

 

 

풀이 2

이 풀이는 대회 도중에 생각해낸 풀이에 해당한다. 

 

$a_i$가 $b_i$가 되도록 다음과 같이 시뮬레이션을 돌리는 것이다.

각 $i$에 대해 $a_i < b_i$라면 $a_i$가 $b_i$가 되게끔 $a_i := a_i+1$ 연산을 할 수 있는 만큼 진행하며
이를 $i := (n+i-1) \ \% \ n$ 로 갱신하며 계속 반복하는 것이다.

 

먼저, 이러한 풀이를 사용하기 위해서는 다음과 같은 문제를 해결해야 했다.

"무수히 많이 시뮬레이션을 하다 보면 $a$가 $b$가 될 수 있는지 알 수 있는데 상한선을 어떻게 정할 것인가?"

시뮬레이션을 하다가 $a_i = b_i$가 되는 경우가 생기면 $a_i$가 고정됨에 따라 $k < i$인 $a_k$의 갱신의 상한선이 생기게 된다.
즉, $a_i = b_i$가 되는 경우를 기점으로 배열의 크기인 $n$번만 더 돌리면 배열 $a$가 배열 $b$가 될 수 있는지를 판단할 수 있다.

 

그렇다면, $a_i = b_i$인 지점이 매우 늦게 나오는 경우엔 어떻게 할까?

모든 $i$에 대해 $b_i - a_i > 10^8$ 을 만족하는 경우를 생각해보자.
이러한 경우, 시뮬레이션 횟수를 $10^8$번 이상 수행해야 $a_i = b_i$인 경우가 나오게 될 것이다.

따라서, 배열 $a$의 원소들과 배열 $b$의 원소들이 차이가 많이 나는 경우에 시뮬레이션을 단축시키는 작업을 해주자.

배열 $a$의 원소 중에서 최댓값을 $max(a)$라 하고, 배열 $b$의 원소 중에서 최솟값을 $min(b)$라 하자.
$max(a) \leq min(b)$인 경우에 배열 $a$의 모든 원소들을 $min(b)$가 되도록 만들 수 있으며 만들어도 된다.
이러한 처리를 해주면 배열 $a$와 배열 $b$의 원소들의 차이가 적게 나며 $a_i = b_i$인 경우 또한 빠르게 나오게 된다.

 

정리하자면, 시뮬레이션을 돌려 배열 $a$가 $b$가 될 수 있는지를 확인하면 된다.

이때, 배열 $a$와 배열 $b$의 원소의 차가 크면 차이를 줄여주는 전처리 작업을 해주고 시뮬레이션을 돌리면 된다.

 

 

 

 

 

느낀점

이번에는 그냥 망한 거 같다.

내 기준 문제들이 어려운 것 같았지만, 논리적으로 접근했다면 A~C 모두 빠르게 풀 수 있었을 것 같다.