SNUPC 2022 G번 수 만들기

문제 링크: https://www.acmicpc.net/problem/25613

25613번: 수 만들기

 

0. 숫자들을 $a_1, a_2, \cdots, a_k$ 순으로 나열했다고 하자. 괄호를 적당히 넣어서 분수를 만들었다고 할 때, 다음을 관찰할 수 있다.

• $a_1$은 분자에 간다.
• $a_2$는 분모에 간다.
• $a_3, a_4, \cdots, a_k$는 분모/분자 어디에나 갈 수 있다.

3번째 관찰을 $a_i$부터 $a_k$까지 괄호를 씌우면 $a_{i+1}, \cdots, a_k$까지 분자에 있었으면 분모로, 분모에 있었으면 분모로 위치를 변경할 수 있기 때문이다. 나눗셈으로 구해진 식은 (분자에 있는 값)$^2$ / 전체 수의 곱 이 된다. 따라서 우리가 구하고자 하는 것은 $1$개 이상 $k$개 미만의 숫자를 골라 곱해서 만들 수 있는 수의 개수와 같다.

 

한 가지 간단하게 알고 넘어갈 수 있는 것은, 만약 숫자들 중 $1$이 있다면 $0$개 이상 $k$개 이하의 숫자를 골라 곱해서 만들 수 있는 수의 개수와 $1$개 이상 $k$개 미만의 숫자를 골라 곱해서 만들 수 있는 수의 개수가 같다는 것이다. $1$이 없다면 두 경우의 수 차이가 $2$ 난다. 이제 $0$개 이상 $k$개 이하의 숫자를 골라 곱해서 만들 수 있는 수의 개수를 구하는 것으로 하자.

 

1. 만들 수 있는 수를 소인수분해 해서 생각해보자. $1$은 만들 수 있는 수에 영향을 안 준다. $5$의 지수는 곱하는 수에 들어가 있는 $5$의 개수와 관련있다. $7$도 마찬가지이다. 나머지 숫자를 ($2$의 지수, $3$의 지수)로 생각해보면, 2, 4, 8, 3, 9, 6이 각각 (1, 0), (2, 0), (3, 0), (0, 1), (0, 2), (1, 1)이 된다. 이제 우리의 문제는 각 2차원 벡터가 $A_i$개 주어질 때 적당히 더해서 만들 수 있는 벡터의 개수와 동일하다.

 

2. (1, 0), (2, 0), (3, 0)으로 만들 수 있는 (x, 0) 꼴의 수, (0, 1), (0, 2)로 만들 수 있는 (0, y) 꼴의 수를 구한 뒤에 (x, 0) 꼴의 수, (0, y) 꼴의 수, (1, 1)을 더해서 만들 수 있는 (x, y) 꼴의 수를 구하자.

 

$1$, $2$, $3$이 각각 $p$, $q$, $r$개 있다고 하자. 이 숫자들을 더해서 만들 수 있는 수의 꼴들은 다음과 같다.

 

• $p \geq 2$이거나 $p=1, q \geq 1$이라면 $[0, p+2q+3r]$으로 나타난다.
• $p=1$, $q=0$이라면 $0 \geq i \geq r$인 $i$에 대해 $3i, 3i+1$의 꼴로 나타난다.
• $p=0, q=0$이라면 $0 \geq i \geq r$인 $i$에 대해 $3i$의 꼴로 나타난다.
• $p=0, r=0$이라면 $0 \geq i \geq q$인 $i$에 대해 $2i$의 꼴로 나타난다.
• $p=0, q=1$이라면 $0 \geq i \geq r$인 $i$에 대해 $3i, 3i+2$의 꼴로 나타난다.
• $p=0, q \geq 2, r \geq 1$이라면 $[0, 2q+3r] \setminus \{1, 2q+3r-1\}$이다.

여기에서 중요한 점은 $0 \geq i \geq 5$인 $i$에 대해서 $6k+i$ 꼴의 수들만 보았을 때 $k$가 구간을 이룬다는 것이다.

$1$, $2$로 만들 수 있는 수들의 범위는 $r=0$인 케이스이므로 위의 경우들에 포함된다.

 

이제 $(x, 0), (0, y), (z, z)$ 3개의 벡터를 더한다고 하자. $x=6x'+k_1$, $y=6y'+k_2$, $z=6z'+k_3$와 같이 6으로 나눈 나머지를 고정하게 된다면 $(x'+z', y'+z')$가 존재하는 범위는 육각형 내부의 모든 점 형태로 나온다. 이때 각 변들은 x, y축과 평행하거나 기울기가 1 또는 -1이다. 그렇다면 3개의 벡터를 모두 더한 값의 $x$값과 $y$값의 6으로 나눈 나머지가 고정되어있을 때 가능한 $(x, y)$ 값의 영역은 6개의 육각형의 합집합으로 나타난다. 이는 스위핑을 적당히 해주면 될 것이라고 믿는다. 따라서 각 테스트케이스당 $6^3$번의 연산으로 해결할 수 있다. 이게 돌지는 잘 모르겠다.