Harbour.Space Scholarship Contest 2023-2024

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

A - Increasing and Decreasing

y - x < N * (N - 1) / 2라면 답이 존재하지 않는다.

그렇지 않다면 A = {x, ..., y - 10, y - 6, y - 3, y - 1, y}와 같이 만들면 된다.

00:03 WA

오타가 있어서 예제가 나오지 않았다.

00:04 AC

 

C - Divisor Chain

우선 x를 2^n 꼴로 만들어야 하는데 하위 비트부터 제거하면 된다.

2^n 꼴이 되었다면 1이 될 때까지 2로 나누면 된다.

00:12 AC

 

B - Swap and Reverse

K가 짝수라면 항상 정렬이 가능하다.

증명은 살짝 복잡한 것 같은데 믿음을 가지고 넘겼다.

K가 홀수라면 reverse 연산은 아무런 의미가 없어진다.

홀수 인덱스와 짝수 인덱스를 각각 정렬하면 된다.

00:18 AC

 

D - Matrix Cascade

대각선 누적 합으로 해결할 수 있을 것 같은데 조금 복잡해 보였다.

셀 (i, j)에 연산을 수행하였을 때 나머지 셀이 어떻게 변화하는지 살펴보자.

• x >= i를 만족하는 셀 (x, y)가 모두 반전된다.
• x >= i + 1를 만족하는 셀 (x, y - 1), (x, y + 1)이 모두 반전된다.
• x >= i + 2를 만족하는 셀 (x, y - 2), (x, y + 2)가 모두 반전된다.
• ...

이는 열 단위로 연산을 수행하고 왼쪽 또는 오른쪽 방향으로 전파가 되는 형태로 생각할 수 있다.

 

다음과 같은 배열 B, L, R을 정의하자.

B[i] = i번 열이 반전된 상태라면 1, 그렇지 않다면 0

L[i] = i번 열에서 왼쪽으로 전파가 이루어져야 한다면 1, 그렇지 않다면 0

R[i] = i번 열에서 오른쪽으로 전파가 이루어져야 한다면 1, 그렇지 않다면 0

 

L과 R은 매 행마다 shift가 필요한데 deque을 이용하면 쉽게 구현할 수 있다.

j번 열에 대하여 B[j] ^= L[j] ^ R[j]를 수행하고 (A[i][j] ^ B[j])가 1이라면 셀 (i, j)에 연산을 수행하면 된다.

셀 (i, j)에 연산을 수행하면 B[j], L[j], R[j]는 모두 반전된다.

00:36 AC

 

E - Guess Game

서로 다른 두 수 a, b에 대하여 (a ^ b)의 켜져 있는 비트 중 최상위 비트에 가까운 비트를 i번 비트라고 하자.

이때 a(또는 b)에서 i번 비트의 상위 비트 중 켜져 있는 비트의 개수를 cnt(a, b)라고 하자.

 

잘 관찰하면 다음과 같은 결론을 이끌어낼 수 있다.

• a가 b보다 작다면 턴 수는 (cnt(a, b) + 1) / 2 * 2 + 1이다.
• a가 b보다 크다면 턴 수는 cnt(a, b) / 2 * 2 + 2이다.
• a가 b와 동일하다면 턴 수는 (a = b의 켜져 있는 비트 수) + 1이다.

Trie를 구성하고 잘 세주면 된다.

입력 값을 정렬하고 a와 b가 서로 다른 경우와 동일한 경우로 나누어서 처리하면 보다 쉽게 구현할 수 있다.

01:32 AC

 

F - Exotic Queries

x = A[i] = A[j]이고 A[(i + 1) .. (j - 1)]에 x가 존재하지 않는다면 A[i]와 A[j]를 인접하다고 하자.

최댓값을 관리하는 Segment Tree를 이용하면 인접한 두 수가 동일한 구간에 속할 수 있게 되는 l의 최솟값을 구할 수 있다.

query를 l이 증가하는 순으로 정렬하고 Fenwick Tree로 합을 관리하면 ft.rsq(l, r)로 문제를 해결할 수 있다.

02:31 AC

 

G - Magic Square (not solved)

Pass

 

H - Asterism Stream (not solved)

Pass

 

I - Future Dominators (not solved)

어쩌구

 

끝

2221점에서 2230점으로 소박한 상승을 목표로 하였는데 2283점으로 max rating을 갱신하였다.

다음 라운드가 많이 부담되는데 떡상이 있으면 떡락도 있는 법이다.

스트레스 받지 말고 즐겜 모드로 칠 수 있도록 노력해야겠다.

끝