2023 신촌지역 대학생 프로그래밍 대회 동아리 연합 여름 대회 (SUAPC 2023 Summer) Open
2023 신촌지역 대학생 프로그래밍 대회 동아리 연합 여름 대회(SUAPC 2023 Summer) Open · Arena #5
사용 가능한 언어 C++17 Java 8 Python 3 C11 PyPy3 C99 C++98 C++11 C++14 Java 8 (OpenJDK) Java 11 C++20 Java 15
www.acmicpc.net
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
끝
끝