제2회 피갤컵

https://www.acmicpc.net/contest/view/1455

 

 

A

2024년 7월 기준 $7(n-1)$개월이 지났을 때 몇년 몇월인지 구하는 사칙연산 문제였다.

 

B

나이트가 2번 이동했을 때 같은 색 칸으로 이동한다는 것으로 우선 $n\geq 4$인 경우에 대해 밝은 색, 어두운 색 칸의 개수를 세는 것으로 답을 구했다. $n$이 3이하일 때 답이 달라지는데 이를 예외처리 해주었다.

 

C

$p^{q^r}$의 경우 $p>1$, $q>1$인 경우에 대해 매우 큰 값을 가지기 때문에 $p=1$인 경우와 $q=1$인 경우에 대해 더하는 것이 답이 될 것이라고 생각했고 맞았다.

 

D

1, 5의순서와 무관하게 답을 구할 수 있어야 하므로 3의 배수가 가장 적합할 것이라고 생각했다. 각 자리의 합을 구해놓고 3의 배수가 되도록 1 또는 5를 빼주는데 1을 빼야하는데 1이 없는 경우는 5의 배수이고 5를 빼야하는데 5가 없는 경우에는 1을 하나 이하로 빼서 11의 배수를 만들어주는 것으로 풀었다.

 

E

$|a-b|$의 기우성이 변하지 않기 때문에 $|a-b|=1(m=\mathrm{mod}\;2)$인 경우에는 불가능한 것으로 예외처리를 해주고 시작했다. 두 번째 관찰은 둘을 같게 만드는 것이 2번에는 무조건 가능하다는 것이다. 작은 쪽에 $|a-b|/2$를 더해주는 연산을 2번 하면 같아지기 때문이다. 이제 1번의 연산으로 둘을 같게 만드는 것이 가능한지를 살폈다. 둘 중 큰 수를 $x$라고 했을 때 $(x>>i)\&1$이 0이라면 $2^i$에 대해 더하기 연산과 bitwise xor 연산이 같아진다. 그러므로 $(x>>i)\&1=1$인 $i$에 대해서 $2^i$을 연산에 활용하면 $2^{i+1}$만큼 차이를 줄일 수 있다. $(x>>i)\&1=1$인 각 비트에 대해서 $2^{i+1}$으로 차이를 0으로 만드는 것이 가능한지 판단했다.

 

F

한 번의 이동마다 한 칸에 치터가 없음을 확정시킬 수 있다는 것을 그림을 그려가면서 알게 되었다. 이를 구현했다.

 

G

$p_i$, $q_i$가 의미하는 바를 생각해보았다. $a_1$~$a_{p_i}$ 중 $a_{p_i}$가 가장 크고 $a_{p_i}<a_{q_i+1}$이라는 것인데, 이를 활용해 어떻게 경우의 수를 구할지 고민을 했다. 처음에는 $a_{p_i}<a_{q_i+1}$라는 사실을 활용하면 순서가 강제되는 것을 활용해 이를 나눠줄 생각을 했지만 $a_{p_i}\geq q_i$라는 점과 $a_1$~$a_{p_i}$ 중 $a_{p_i}$가 가장 크다는 점을 반영하기가 힘들었다. 생각을 하던 중 $a_{p_i}<a_{q_i+1}$라는 것은 $a_1$~$a_{q_i+1}$ 중 $a_{q_i+1}$이 가장 크다는 것이므로 이를 활용하면 문제를 풀 수 있을 것 같았다. 입력된 $p_i$와 $q_i$중 서로 모순되는 것이 없는지 우선 확인해주고 없다면 map에 $i$마다 $a_i$가 $a_1$~$a_j$ 중 최대라고 할 수 있는 $j$의 최댓값을 저장해두고 $n!$에서 각각의 $j$를 나누어주는 방식으로 답을 구했다.

 

H

bitset을 활용한 dp로 풀 생각을 했는데 복잡도를 줄일 방법을 못찾았다.