Harbour.Space Scholarship Contest 2023-2024 (Div. 1 + Div. 2)

 

Div. 1이 있어 오랜만에 코포를 쳤다.

A. Increasing and Decreasing (0:02, +)

공차를 뒤에서부터 1, 2, .. 로 설정해준 후 마지막에 수를 몰아서 쓰면 된다.

 

B. Swap and Reverse (0:05, +)

\(k\)가 짝수이면 문자열을 자유롭게 변형할 수 있고, 홀수이면 인덱스의 홀짝성을 유지한 채 자유롭게 바꿀 수 있다. 따라서 경우를 나눈 후 문자열을 정렬해주면 된다.

 

C. Divisor Chain (0:44, +2)

쉽게 생각할 수 있는 방법이 다 반례가 있는 것 같아 뇌정지가 왔다. 이상한 풀이로 페널티를 적립하던 중 괜찮은 접근이 떠올라 증명 없이 내서 맞았다. 2의 거듭제곱에 한 번 도달하면 쉽게 끝을 낼 수 있는데, 여기 도달하기 위해 현재의 수를 2로 최대한 나눈 후 홀수 약수를 아무거나 찾았다. 끝나고 생각해보니, 2의 거듭제곱이 아니라면 가장 작은 비트를 지우는 방법으로 접근하면 깔끔하고 멋진 풀이가 되는 것 같다.

 

D. Matrix Cascade (0:56, +)

윗 줄부터 보며 켜야 하면 키면 된다. 이를 관리하기 위해선 대각선 모양의 누적합이 필요한데, 많이 본 유형이라 그냥 바로 짜서 맞았다.

 

E. Guess Game (1:35, +)

A, B가 고정되어 있다고 생각한 후 종료 턴 수를 구해보자. 한 명이 턴을 넘길 때마다 비트가 하나 결정되므로 대략 (두 수의 비트가 처음으로 달라지는 위치 이전에 모두가 1인 비트의 수) 정도가 종료 턴 수가 됨을 알 수 있다. 이는 각 노드에 등장 횟수를 저장하는 이진 트라이를 이용하면 처리할 수 있다. 예외 처리가 살짝씩 필요한데 그닥 어렵지는 않다.

 

F. Exotic Queries (2:18, +)

쿼리가 인덱스인 줄 알았지만, 아니라는 것을 알아채는 데에 10분 정도가 걸렸다. 문제 세팅이 며칠 전 본 SCPC 2차 4번과 비슷해서 우선 오프라인을 박고 생각해보기로 했다. 쿼리를 끝점 기준으로 정렬하자. \(i\)번째 step에서는 \(D_j  = [j,i]\)일 때의 답을 관리할 것이다. 이제 \(i\)가 변함에 따른 \(D_j\)를 관리해야 한다. 우선 \(i\)인 원소가 존재한다면 모든 \(D_i\)에 1을 더하자. 이후, 값이 \(i\)인 두 인덱스를 \(a, b\), \([a+1,b-1]\) 구간에서 \(i\) 미만인 수 중 최댓값을 \(x\)라 하자. 이럴 시, \(i \leq x\)에 대해 \(D_i\)는 1 증가한다. \(i-1\) 이하인 수를 다 처리했을 때 구간이 나누어지기 때문이다. 이를 모든 인접한 \(a, b\)에 대해 처리해주면 된다. Range Maximum Query를 지원하는 세그먼트 트리 하나, Range Update Point Query를 지원하는 펜윅 트리 하나를 사용하면 된다.

 

요즘 코포를 소홀히 했더니 C에서 많이 절었지만, D~F가 K-웰노운이라 나름 선방을 해낼 수 있었다. SCPC 대비를 위해서라도 슬슬 PS를 열심히 해야 할 것 같다.