2022 경인지역 6개 대학 연합 프로그래밍 경시대회 shake! Open Contest

2022 경인지역 6개 대학 연합 프로그래밍 경시대회 shake! Open Contest

B - 지수를 더하자

수학

00:04 AC

 

D - 버튼 정렬

최초 한 번만 정렬되면 이후에는 주기성이 생긴다.

00:16 WA

예제만 통과하는 잘못된 코드였다.

00:20 WA

 

다음과 같은 반례에 주의해야 한다.

5

1 2 3 5 4

10

잘못 생각하면 한 번의 연산으로 마지막 4를 5로 만들 수 있다고 생각할 수 있다.

하지만 이전의 모든 원소 x에 대하여 x > 4를 만족하여야 한다.

따라서 수열 A가 최초로 정렬되는 시점은 1이 아닌 10이 된다.

00:25 AC

 

A - 팝핀 소다

시은이보다 약한 선수의 수를 K라고 하자.

매 대결마다 K는 (K - 1) / 2로 감소하며 K가 0이 되면 이변을 일으켜야 한다.

A번 치고 까다로운 문제였다.

00:30 AC

 

C - 굉장한 모비스터디

세 개의 그래프를 구성할 수 있다.

각 그래프에서 정점 i가 속한 컴포넌트 번호를 tuple iii로 관리해주자.

이후 map<iii, vector<int>>로 빈도를 세주면 된다.

00:42 AC

 

G - 견우와 직녀

구현이 약간 까다로운 tree dp

01:03 AC

 

E - 개구리와 쿼리

다음과 같은 배열 B와 C를 정의하자.

• B[i][j] = sum(A[i][j .. N]);
• C[i][j] = min(C[i - 1][j], B[i][j]);

이제 각 query를 O(N)에 처리할 수 있다.

01:13 AC

 

F - 문자 연금술

편의를 위하여 N > M이라고 가정한다.

항상 ab...ba...a를 출력하도록 하였다.

01:46 WA

N = M = 1인 경우를 예외 처리하였다.

01:50 WA

두 가지 경우로 나누어서 처리하였는데 후술한다.

02:01 WA

N = M = 1인 경우의 예외 처리가 불필요하고 잘못된 예외 처리였다.

02:02 AC

 

대회 중 제출하였던 풀이와 비슷하지만 조금 더 간단한 풀이를 발견하였다.

if N > 3 && M > 1 then

    ans = str(1, 'a') + str(1, 'b') + str(N - 3, 'a') + str(M - 1, 'b') + str(2, 'a');

           = "aba...ab...baa";

else

    ans = str(1, 'a') + str(M, 'b') + str(N - 1, 'a');

           = "ab...ba...a";

 

H - 경우의 수

backtracking + 조합론

x1이 1인 경우와 그렇지 않은 경우를 나누어서 처리해야 한다.

02:48 WA

모듈러 곱셈 역원을 잘못 구하였다.

03:05 AC

 

I - 숲 속의 과학자

지문이 상당히 복잡하지만 다음과 같이 요약할 수 있다.

• bst를 구성하되 높이를 최소화하시오.
• 노드가 최대한 오른쪽으로 치우치게 구성하시오.

재귀 함수로 풀이하면 되는데 다음과 같은 solve 함수를 정의할 수 있다.

ll solve(ll s, ll e, ll x, int d);

// s 이상 e 미만의 원소를 포함하는 높이 d의 트리에서 x번째 원소를 return

03:52 AC

 

J - 송유관 I (not solved)

이벤트를 다음과 같이 바꾸어 생각할 수 있다.

• 1 L T: 새로운 발전소가 들어왔고 L번 주유소에 송유관을 설치한다.
• 2 I C: [I, N]번 주유소에 송유관이 설치된 모든 발전소에 기름을 공급한다.

다음과 같은 배열 A와 B를 정의하자.

• A[i] = i번 주유소에 공급된 기름의 양
• B[i] = i번 주유소에 송유관을 설치한 가동 전인 발전소에 대하여 (발전소가 들어온 시점의 A[i] + T)의 최솟값

1번 이벤트가 들어오면 B[L]의 최솟값을 구해야 한다.

이는 각 주유소마다 pq를 설치하여 해결할 수 있다.

2번 이벤트가 들어오면 A[I .. N]에 C를 더하고 A[i] >= B[i]를 만족하는 주유소를 구해야 한다.

이는 상당히 복잡한 작업인데 LzSeg로 해결할 수 있다.

 

LzSeg는 다음과 같이 4개의 배열로 구현할 수 있다.

• st1: i번 주유소에 공급된 기름의 양
• st2: 리프 노드인 경우 st1[p] - pq[i].top().first, 그렇지 않다면 구간의 최댓값
• lz: lazy update 용도
• pq: (발전소가 들어온 시점의 st1[p] + T, 발전소 번호)의 최솟값을 관리하는 pq

st2[1]이 0 이상이라면 가동된 발전소가 존재하는 것이다.

 

K - 끝말잇기 (not solved)

Pass

 

L - 송유관 II (not solved)

Pass

 

끝

끝