제 2회 피갤컵 후기

제 2회 피갤컵에 참가했다.

1회 후기: https://flappybird.tistory.com/74

제 1회 피갤컵 후기

 

8솔, 패널티 499

5등했다.

 

전체적인 퀄리티에 대해서 말하자면, 1회 피갤컵과 비슷하게 매우 좋다고 생각한다. 특히 F와 G번 문제가 정말 재미있었다. 쉬운 포지션의 문제도 퀄리티가 좋은 편이다.

 

아쉬웠던 점들:

• D 퍼솔을 정말 간발의 차이로 놓쳤다. AC를 받은 직후 스코어보드에는 퍼솔로 표기되었으나, 한 1분쯤 지나니 나보다 먼저 제출한 다른 사람의 소스코드가 채점되었고, 퍼솔을 뺐겼다.
• 끝나기 2분 전 I 풀이를 다 짰는데, 예제가 안 나왔다. 그대로 디버깅하다 사망

풀이

1회 후기와 마찬가지로, 내가 못 푼 문제는 안 썼다. A-H의 풀이만 있다.

A. 피갤컵

여러 가지 방법이 있다.

• $N \le 5$이므로 각각의 $N$에 대해 답을 다 구하고, 조건문으로 답을 출력한다.
• 2024년 8월 이후 $7(N-1)$달 이후를 출력하면 되므로, 1회 피갤컵 이후 몇 년과 몇 달이 지났는지를 계산하여 출력한다.

나의 경우 후자를 선택했다.

B. 나이트의 이동

$N =3$일때와 $N>3$일때로 나눠 생각한다.

• $N=3$인 경우, 시작 위치가 $(2, 2)$인 경우 답은 $1$, 그렇지 않은 경우 답은 $4$이다.
• $N>3$인 경우, 시작 위치와 같은 색깔의 칸을 전부 방문할 수 있다. 따라서, $R+C$의 기우성에 따라 검은 색 칸의 개수, 흰색 칸의 개수 중 하나를 출력하면 된다.

C. 2^3

C와 E가 xor 연산을 쓰는 문제인데, 이 글에서는 다음 xor 연산들의 성질을 안다고 가정하고 설명하겠다.

• 결합법칙, 교환법칙이 성립한다.
• $0$이 항등원이다. ($a \oplus 0=a$)
• 모든 정수는 자기자신을 역원으로 갖는다. ($a \oplus a=0$)

 

구해야 하는 것은 $a \oplus b \oplus c=a^{(b^c)}$인 $(a, b, c)$의 개수이다. 경우를 나눠 생각하자.

• $a=1$인 경우, $1=1\oplus b \oplus c$, $b \oplus c=0$, $b=c$가 성립한다.
• $a>1$이고 $b=1$인 경우, $a\oplus 1 \oplus c = a$, $c=1$이 성립한다.
• $a>1$이고 $b>1$인 경우, $a \oplus b \oplus c \le 2 \cdot 10^{7}$이므로 $b^c \ge 30$이다. 이러한 조건을 만족하는 순서쌍 $(b, c)$를 모두 구하자. 이후 $a$를 $1$부터 $P$까지 보면서 식을 만족하는 순서쌍 $(b, c)$를 다 구해주면 된다.

세 번째 경우에서 나는 $a^{(b^c)}$가 너무 커져버리게 되면 이후의 $a$들에 대해 이 순서쌍을 더 이상 확인하지 않는 최적화를 사용했다. 이게 꼭 필요한지는 모르겠는데, 내 코드가 0.3s정도에 도니까 아마 없으면 tle를 받을 수도 있을거같다.

 

D. 1과 5

우선 끝자리나 끝에서 두 번째 자리가 $5$인 경우, 뒤쪽에서 숫자를 하나 이하로 지워 $5$의 배수로 만들 수 있다. 이 경우를 제외하자.

 

$s$를 자리수의 합이라 하자. 잘 알려진 정리에 의해, 주어진 자연수가 $3$의 배수임은 $s$가 3의 배수임과 동치이다. $s$가 $3$의 배수인 경우, 그냥 이 수가 $3$의 배수임을 선언하고 끝내면 된다. 만약 $s$를 3으로 나눈 나머지가 $1$일 경우, 맨 끝자리인 $1$ (위의 $5$의 배수 판정에서 제외되지 않은 수는 끝자리가 $1$이다)을 제거함으로 자리수 합을 $3$의 배수로 만들 수 있다.

 

따라서, 자리수 합을 $3$으로 나눴을 때 나머지가 $2$인 경우만 생각하면 된다. 만약 주어진 수가 $5$를 포함할 경우, 이를 제거하면 자리수 합이 $3$의 배수가 된다. 그렇지 않은 경우, 주어진 수는 $1$로만 이루어진 수일 것이다.

 

이때, 짝수개의 $1$로 이루어진 자연수는 $11$의 배수이다. 따라서 주어진 수의 길이가 짝수라면 $11$의 배수임을 선언하고 끝내면 되고, 그렇지 않다면 아무 $1$을 하나 지워 $11$의 배수로 만들면 된다.

 

E. 판드랄추

주어진 두 수를 $a, b$라 하고, 일반성을 잃지 않고 $a<b$라 하자. 다음과 같은 두 관찰을 할 수 있다. 

 

관찰 1. 두 수의 기우성이 홀수면 답은 -1이다.

두 수의 $2$진법 표현의 마지막 자리 수에 대해서 관찰하면, 어떻게 연산을 하더라도 한 수의 기우성이 바뀌면 다른 수의 기우성도 바뀌고, 역도 성립한다.

 

관찰 2. $a$와 $b$의 기우성이 같다면, 두 번의 연산으로 두 수를 같게 만들 수 있다.

$d=(b-a)/2$라 하면, 이는 정수이다. 이때, $a$에 $d$를 더하고 $b$에 $d$를 xor하는 연산을 두 번 시행하면 $a$는 $a+2d=b$가 되고, $b$는 $b \oplus d \oplus d=b$가 되어 같아진다.

 

따라서, 우리가 해야 할 일은 한 번의 연산으로 두 수를 같게 만들 수 있는지 판별하는 것이다.

두 수에 $x$라는 수를 연산하여 두 수가 같아졌다고 하자. 그러면 $a$에 $x$를 더하고 $b$에 xor연산을 했음을 알 수 있는데, xor 연산을 할 경우 수는 최대 $x$만큼 증가하므로 반대로 할 경우 여전히 $a<b$가 유지되기 때문이다.

 

따라서, 우리는 $(a +x)\oplus x=b$인 $x$를 찾으면 된다.

 

$x$의 가장 아래 비트부터 답을 결정할 수 있다. 다음과 같이 하면 된다.

• $a$의 $i$번째 비트와 $b$의 $i$번째 비트가 다르다면, 그냥 넘어간다.
• 다르다면, $a$와 $x$의 $i-1$번째 비트는 1이어야 한다. $x$에 $2^{i-1}$을 더하고 $a$도 $(a+2^{i-1})\oplus 2^{i-1}$로 바꾼다.

F. 치터 잡기

아이디어 하나를 내면 답이 된다. 따라서 풀이는 다음 사진으로 대체한다.

이렇게 하면, 이동하는 선 왼쪽에는 치터가 절대로 있을 수 없고, 따라서 $N$ (짝수일 때는 $N+1$)번의 이동마다 치터가 있을 수 있는 칸의 수가 $N$칸 감소하게 된다.

G. 내 맘대로 정렬

$A_i$가 $A_1, A_2, \cdots, A_i$ 중 최댓값일 경우, 이러한 $i$들을 prefix maximum이라 하자.

 

배열 $A$에 연산이 적용되면, 다음과 같은 변화가 일어난다.

• $i$가 prefix maximum이었다 하자. 또한, 이런 조건을 만족하는 다음 $i$를 $j$라 하자. (없다면 $j=N+1$이라 하자) 그러면 $A_i$는 $j-1$번째 원소가 된다.
• 그렇지 않은 모든 원소는 앞으로 한 칸씩 당겨진다.

따라서, 주어진 $(p_i, q_i)$를 다음과 같이 분류한다.

• $p_i \le q_i$: $p_i$와 $q_i+1$이 prefix maximum이며, $(p_i, q_i]$ 위치에 있는 원소는 모두 $p_i$번째 원소보다 작다.
• $p_i>q_i$: $p_i-1>q_i$인 경우는 없으므로, 만약 그렇다면 0을 출력하고 종료한다. 그렇지 않은 경우, $p_i$는 prefix maximum이 아님을 알 수 있다.

따라서, 알 수 있는 정보는 특정한 인덱스가 "반드시 prefix maximum이다", "반드시 prefix maximum이 아니다"가 있다. 반우선 주어진 정보와 알아낸 정보들간에 모순이 있는지 찾고, 그렇다면 0을 출력하고 종료하자. 다음 두 경우만 보면 된다.

• $i$가 prefix maximum이면서, 동시에 prefix maximum이 아니다.
• prefix maximum인 $i$에 대해, 어떤 $p_j$와 $q_j$가 존재하여 $i \in (p_j, q_j]$.

주의해야 할 점은, $1$번 인덱스는 반드시 prefix maximum이라는 것이다.

위 두 가지가 아닐 경우 답은 0 초과이다. 이제 답을 구하자.

 

정보를 바탕으로 알 수 있는 확실한 prefix maximum을 순서대로 $P_1, \cdots, P_M$이라 하자. 또한, 서술의 편의성을 위해 $P_{M+1}=N+1$로 놓자. 우선 prefix maximum들을 분류한다.

• 어떤 $p_j, q_j$가 있어 $p_j=P_i, q_j+1=P_{i+1}$이다: 이 경우, $P_i$번째 원소는 $1, 2, \cdots,P_{i+1}$번째 원소 중 최댓값이다. 즉, $(P_i, P_{i+1})$에는 추가적인 prefix maximum들이 반드시 없다.
• 그러한 $j$가 없다: 이 경우, $(P_i, P_{i+1})$에는 추가적인 prefix maximum들이 있을수도 있다.

이제 $i$를 $1$부터 $M$까지 증가시키며 $[1, P_{i+1})$ 위치에 $1, 2, \cdots, P_{i+1}-1$의 수들을 배치하는 방법의 수를 구하자. $i-1$일때의 답이 $X$였고, 이제 $i$일때의 답을 구해야 한다 하자.

 

전체적인 방법은 다음과 같다.

• $j$를 $P_i$부터 $P_{i+1}-1$까지 증가시키며, $A_j$가 들어갈 위치 $k$를 정한다. 이후, $A_j$를 $k-1$와 $k$ 사이에 끼워넣는다: $A_j$를 $k$로 정하고, 원래 $A$에서 값이 $k$ 이상이었던 것들을 $1$ 증가시킨다. 아무 제약 조건이 없으면 $k$의 후보는 $j$개이다.

첫 번째 케이스의 경우(위의 두 가지 경우 나누기에서), $P_i$번째 인덱스는 $[1, P_{i+1})$에서 최댓값을 가진다. $P_i$를 끼워넣는 방법의 수는 유일하다. 이후의 인덱스 $j$에 대해서는, 이 값이 prefix maximum이 될 수 없으므로 총 $j-1$개의 후보가 있다. 따라서, 총 경우의 수는 $\frac{(P_{i+1}-2)!}{(P_i-1)!}X$ 가지이다.

 

두 번째 케이스의 경우, 끼워넣을 수 있는 후보의 수는 다음 세 가지 중 하나이다.

• $P_i$의 경우, 최댓값이 되어야 하므로 유일하다.
• 인덱스 $i$가 반드시 prefix maximum이 아닐 경우($p_j>q_j, p_j=i$인 $j$가 존재) 총 $i-1$가지이다.
• 위의 경우가 둘 다 아닐 경우, 아무 제약 조건이 없으므로 $i$가지이다.

이를 어떻게 빨리 정리할까? 만약 모든 인덱스가 prefix maximum이 될 가능성이 있을 경우, 단순히 $(P_{i+1}-1)!/(P_i)!$가지이다. 그런데, 한 인덱스 $i$가 prefix maximum이 아니라는 조건이 있었을 경우 이 식에 $i$가 곱해지는 대신 $i-1$이 곱해진다. 따라서, 이러한 $i$를 전부 찾아서 $(i-1)/i$의 곱을 구하고, 이걸 위 식에 곱해주면 총 경우의 수가 된다.

 

위 모든 과정에서 factorial을 구하는 것은 모든 테스트 케이스를 실행하기 전 한번만 전처리해주면 된다.

prefix maximum이 아닌게 확정된 인덱스 $i$에 대해서, 이 인덱스는 최대 한 번만 확인된다. 따라서 총 시간복잡도는 $O(Q)$이다. (구현의 편의성을 위해 정렬이나 lower_bound 등을 썼으면 로그가 붙는다)

H. 햄북이

사진을 누르면 링크에 접속할 수 있다.

결국 문제에서 요구하는건 일렬로 놓인 $N$개의 수가 있을 때, 인접한 두 개의 수를 지우고 그 자리에 차를 쓰는 것과 같다. 그렇다면 결국 답이 되는 수들은 $N$개의 수들 중 몇 개의 합에서 나머지들의 합을 뺀 것과 같다.

 

$A_i$의 전체 합을 $S$라 하자. $A_i$들 중 일부를 골라서 만들 수 있는 합들 중 $S/2$ 이하인 최댓값을 $sum$이라 하자. 그렇다면 정답은 $S-(S-sum)$보다 작을 수 없음은 자명하다. 그렇다면 이 값이 실제로 답이 될까?

 

신기하게도, 다음과 같이 답을 construct할 수 있다.

$A_i$ 중에서 더해져야 할 값에 $+$, 빼져야 할 값들에 $-$로 표시하자. 이후, 인접한 $+$와 $-$를 고르고, 두 수를 지운 후 차이를 적는다. 또한, 이 수에는 원래 두 값들 중 $+$가 컸다면 $+$를, 아니면 $-$를 표시한다.

 

이 과정을 하나 이하의 수가 남을 때까지 반복한다. 매 시행 과정에서, 다음이 성립한다.

• $+$가 표시된 수는 초기 배열에서 $+$가 표시된 수들 일부의 합에서 $-$가 표시된 수들 일부의 합을 뺀 것이다.
• $-$가 표시된 수는 초기 배열에서 $-$가 표시된 수들 일부의 합에서 $+$가 표시된 수들 일부의 합을 뺀 것이다.

또한, 수가 두 개 이상 남아 있다면 인접한 $+$와 $-$는 항상 존재한다.

모두 $+$인 경우, 이들을 아무렇게나 연산을 해서 하나의 숫자로 만들면 결과값은 $S-(S-sum)$보다 작다. 즉, $sum$이 $S/2$ 이하인 최댓값이라는 것에 모순이 된다.

모두 $-$인 경우, $sum$이 $S/2$ 이하라는것에 모순이다.

 

따라서, 냅색 등의 dp를 돌려 $sum$을 구하고, $A_i$에서 어떤 값이 더해지고 빼져야하는지 구하면 답을 구할 수 있다.