2023 부산대학교 CodeRace Open Contest

2023 부산대학교 CodeRace Open Contest

A - 첨탑 밀어서 부수기

단순 구현

00:01 AC

 

B - 영역 색칠

색이 k번 뒤바뀌는 영역은 최소 ((k + 1) / 2 + 1)번의 붓칠이 필요하다.

00:05 AC

 

D - 게임을 클리어하자

dp로 풀이할 수 있는데 26093번과 매우 유사하다.

최솟값 2개만 구하면 되므로 O(NM)이 가능하다.

00:13 AC

 

E - 시간이 겹칠까?

누적 합

00:15 AC

imos법이라고 많이 불리던데 간단한 테크닉에 별도의 이름을 붙일 필요가 있나 싶다.

 

F - 산지니의 여행계획

지문이 너무 억지스럽다.

여러 풍경을 차 안에서 느긋이 즐기고 싶다면서 마지막에는 운전 거리를 최대한 줄여보자고 한다.

아무튼 mst + dfs 풀이가 가능하다.

00:27 AC

 

여담으로 간선의 가중치가 모두 다른 그래프의 mst는 유일하다고 한다.

나는 잘 모르겠어서 proof by ac로 증명하였다.

 

G - Attention

주어진 두 배열을 A와 B라고 하자.

그리고 배열 C를 다음과 같이 정의하자.

C[i] = B[j] == i를 만족하는 j;

 

이제 중앙값을 A[0] .. A[N - 1]로 변화시키면서 답을 계산하면 된다.

구체적으로는 다음을 계산해야 한다.

ans += (p1 < i && p2 < C[A[i]] && A[p1] == B[p2]를 만족하는 쌍의 개수)

          * (p1 > i && p2 > C[A[i]] && A[p1] == B[p2]를 만족하는 쌍의 개수)

이는 Fenwick Tree 또는 pbds로 구할 수 있다.

항 하나만 구하면 나머지 항은 수식 정리를 통하여 구할 수 있다.

 

pbds 구현은 다음과 같다.

for i = 0; i < N; ++i

    ll x = tree.order_of_key(C[A[i]]);

    ans += x * (N + x - i - C[A[i]] - 1);

    tree.insert(C[A[i]]);

 

pbds는 상수가 크기 때문에 혹시 모를 TLE를 방지하기 위하여 대회 중에는 Fenwick Tree로 구현하였다.

실제로는 pbds 풀이도 매우 빠르게 돌아간다.

00:43 AC

 

C - 경품 추첨

지문이 무슨 소리인지 알아 먹을 수가 없어서 마지막으로 풀었다.

dp로 해결할 수 있는데 실수 자료형을 사용하면 오차가 발생한다.

다행히 우리에게는 __int128 타입이 있다.

00:52 AC

index 오류가 발생하는 코드였는데 다행히도 AC를 받았다.

 

끝

끝