2023 신촌지역 대학생 프로그래밍 대회 동아리 연합 여름 대회 (SUAPC 2023 Summer) Open

2023 신촌지역 대학생 프로그래밍 대회 동아리 연합 여름 대회(SUAPC 2023 Summer) Open · Arena #5

L - 나의 FIFA 팀 가치는?

pq

00:07 AC

 

G - 개발자 지망생 구름이의 취업 뽀개기

동일한 난이도의 문제들을 푸는 데 걸리는 최소 시간은 sum(시간) + max(시간) - min(시간)이다.

따라서 푸는 데 걸리는 시간이 짧은 문제부터 풀면 된다.

00:16 AC

 

K - 케이크 두 개

두 케이크의 중점을 지나는 직선을 그리면 된다.

직사각형의 중점은 ((x1 + x2 + x3 + x4) / 4, (y1 + y2 + y3 + y4) / 4)이다.

좌표에 4를 곱한 후 처리하면 편리하다.

00:26 WA

예제 입력 1만 보고 두 직사각형 모두 축에 평행한 줄 알았다.

00:29 AC

 

I - 폭탄 피하기

포함 배제 + 조합론

00:47 AC

 

J - 큰 수 만들기 게임

16496번의 강화 버전인데 대회 일자 며칠 전에 랭작하다가 풀이하였다.

안 풀어봤으면 30분은 더 걸렸을 것 같다.

 

성현이의 답은 소인수분해한 후 16496번과 동일하게 풀이하면 된다.

지훈이의 답은 2를 최대한 사용한 후 3을 사용할 수 있다면 앞자리를 3으로 바꾸어주면 된다.

두 수의 합이 128 비트 정수 자료형의 최댓값을 아슬아슬하게 넘어가기 때문에 큰 수 연산이 필요하다.

01:10 AC

 

H - 탭 UI

다음과 같은 누적 합 배열 A를 정의하자.

A[i] = sum(l[1 .. i])

그리고 사용자가 클릭한 탭의 번호를 x라고 하자.

답은 min(max(A[x - 1] + A[x] - L, 0), 2 * max(A[N] - L, 0)) / 2이다.

01:26 AC

 

F - 작곡가 A의 시창 평가

z 배열로 빨간색으로 색칠된 구간을 구할 수 있다.

각 구간에 대하여 그런디 수를 구해보면 (구간의 그런디 수) = (구간의 크기)임을 알 수 있다.

님 게임의 풀이와 동일하게 xor을 하면 된다.

01:46 AC

 

D - 디지털 트윈

다음과 같은 점화식을 세울 수 있다.

dp[i][0] = i번 행에서 왼쪽으로 갈 때 컨테이너 벨트의 최소 길이

dp[i][1] = i번 행에서 오른쪽으로 갈 때 컨테이너 벨트의 최소 길이

구체적인 계산 과정은 생략한다.

행이 비어 있는 경우 별도의 처리가 필요함에 유의해야 한다.

02:18 WA

일부 케이스를 간과하였다.

에디토리얼을 보면 알겠지만 점화식이 복잡하지는 않은데 고려해야 할 케이스가 조금 많은 편이다.

02:29 AC

 

A - A→B

아무리 봐도 풀이가 생각나지 않아서 naive 코드를 짜고 규칙을 찾아서 풀었다.

03:31 AC

 

E - 성게 밭

암수 조건이 뜬금 없다고 생각할 수 있는데 이는 문제를 풀기 위한 핵심 조건이다.

암수 조건에 의하여 서로 다른 세 성게는 동일한 가시를 공유할 수 없다.

따라서 차수가 3 이상인 정점은 성게의 중심이며 나머지 정점은 성게의 가시이다.

 

각 성게의 암수를 적절히 결정하면 주어진 그래프는 이분 그래프가 된다.

이제 이분 그래프에서 최대 독립 집합의 크기를 구하면 된다.

일반적인 그래프에서 이는 NP-hard이지만 이분 그래프에서는 이분 매칭으로 답을 구할 수 있다.

 

이러한 유형을 너무 오랜만에 봐서 30분 동안 멍만 때리고 있었다.

'이분 그래프 최대 독립 집합'으로 구글링하니 풀이가 바로 나와서 다행히 풀 수 있었다.

04:18 AC

 

C - 2048 (not solved)

조금 많이 귀찮은 행렬 곱셈 dp

 

B - 기초적인 문제 (not solved)

전혀 기초적이지 않다.

 

M - 트리와 케이 (not solved)

Pass

 

N - 북극여우는 괄호를 뒤집어 (not solved)

Pass

 

끝

끝