2019 SCCC 벚꽃맞이 컨테스트
대회 요약 및 풀이
출제자
번호 | 제목 | 출제자 |
A | 벚꽃이 정보섬에 피어난 이유 | 권욱제 (컴퓨터18) |
B | 소가 정보섬에 올라온 이유 | |
C | 윌리암슨수액빨이딱따구리가 정보섬에 올라온 이유 | |
D | 토끼가 정보섬에 올라온 이유 | 김도현 (컴퓨터17) |
E | 여우가 정보섬에 올라온 이유 | |
F | 두더지가 정보섬에 올라온 이유 | 주영준 (소프트15) |
G | 라쿤이 정보섬에 올라온 이유 | 조민석 (컴퓨터16) |
대회 요약
n/m명(참가자/신청자)
번호 | 제목 | 정답자 | 정답률 |
A | 벚꽃이 정보섬에 피어난 이유 | | |
B | 소가 정보섬에 올라온 이유 | | |
C | 윌리암슨수액빨이딱따구리가 정보섬에 올라온 이유 | | |
D | 토끼가 정보섬에 올라온 이유 | | |
E | 여우가 정보섬에 올라온 이유 | | |
F | 두더지가 정보섬에 올라온 이유 | | |
G | 라쿤이 정보섬에 올라온 이유 | | |
A. 벚꽃이 정보섬에 피어난 이유
solved: x out of y
writer: 권욱제
O(N^4)
N이 10밖에 되지 않으므로 모든 경우를 다 돌려 보면 됩니다.
반복문이나 재귀나 등등 뭐든 다 좋아요.
첫 문제 파이팅스럽게 그림도 예쁘게 그려 넣었답니다.
아래의 그림과 같은 느낌으로 4중 for문을 사용하면 된답니다.
1 ~ i
i+1 ~ j
j+1 ~ k
k+1 ~ l
이런 느낌으로 짜시면 됩니다
for (i, 1, n-3) {� for (j, i+1, n-2) {� for (k, j+1, n-1) {� for (l, k+1, n) {� }� if (dap < p1 + p2 + p3 + p4) {� dap = p1 + p2 + p3 + p4;� }� }� }� }
B. 소가 정보섬에 올라온 이유
solved: x out of y
writer: 권욱제
O(N + Q)
어떤 수에 -1이 곱해질 때마다 S를 naive하게 계산하면 O(NQ)로 시간초과가 납니다.
식을 잘 관찰해 보면,
a[i]가 -a[i]가 될때, a[i-3 ~ i], a[i-2 ~ i+1], a[i-1 ~ i+2], a[i ~ i+3]의 값만 바뀝니다.
이를 이용해서, 쿼리가 주어질 때마다 값을 O(1)에 갱신할 수 있습니다.
O(N + Q)
60
60
2 | 2 | 3 | 5 | 1 | 7 | 2 | 3 | 2 | | |
30
105
70
42
2 | 2 | 3 | 5 | -1 | 7 | 2 | 3 | 2 | | |
-30
-105
-70
-42
84
84
C. 윌리암슨수액빨이딱따구리가 정보섬에 올라온 이유
solved: x out of y
writer: 권욱제
O(NM)
전형적인 4방향 탐색문제입니다.
같은 시작점에서 총 3개의 도착지로 가는 최단경로의 길이를 찾아야 합니다.
하지만, 맵의 크기가 3000*3000이어서 BFS 한 번에 약 0.5초 정도의 시간이 걸립니다.
탐색을 한 번에 0.5초가 걸리므로, 3번 탐색하면 시간제한 1초를 넘어버리게 됩니다.
O(NM)
그렇다면 시간초과를 어떻게 해결하는가?
BFS의 정의를 정확히 알고 있다면, 문제를 쉽게 해결할 수 있습니다.
N*M 격자는 모든 칸이 상하좌우 4칸과 가중치 1인 간선으로 그래프로 볼 수 있습니다.
D. 토끼가 정보섬에 올라온 이유
solved: x out of y
writer: 김도현
O(NM)
dp[i][j]=“토끼의 위치가 (i,j)일때 탈출하면서 획득할 수 있는 최대 당근개수”라고 정의해봅시다. 어떠한 경로를 선택하든지 매 시간 토끼의 x좌표는 1씩 증가하기 때문에 상태간 의존성이 사이클 없는 방향그래프(DAG)이므로 DP가 가능합니다. 점화식은 dp[i][j]=max(dp[i-1][j+1], dp[i][j+1], dp[i+1][j+1])+(arr[i][j]==’C’) 입니다. 출구를 지나칠 수 있다는 조건을 처리하는게 어려울 수도 있는데, 잘 생각해보면 현재출구를 지나쳐서 탈출할 수 있다면 지금 탈출하는것보다 손해볼 이유가 없습니다. 당근을 더 먹으면 먹지 잃지는 않기 때문입니다. 따라서 출구도 빈칸처럼 재귀적으로 답을 구한 다음, 부분문제들이 모두 탈출 불가한 경우에 현재출구로 탈출하면 됩니다.
E. 여우가 정보섬에 올라온 이유
solved: x out of y
writer: 김도현
O(N^2)
먼저 “전체V의 개수=N개의 별 각각에 대해 그 별을 중심으로 하는 V의 개수들의 합”으로 문제를 분해할 수 있습니다. 각각의 부분문제들에 대해 가정한 중심별을 b라고 합시다. 그러면 그 b를 중심으로 하는 별자리의 개수는 (b보다 왼쪽위에 있는 별의 개수)*(b보다 오른쪽 위에 있는 별의 개수)임을 알 수 있습니다. 각각의 개수는 O(N)만에 구할 수 있으므로 부분문제의 시간복잡도는 O(N)이고, 부분문제가 N개이므로 총 O(N^2)에 해결 할 수 있습니다.
O(N log N)
N^2 알고리즘을 다음과 같은 과정을 통해 O(NlogN)으로 최적화할 수 있습니다. 우선 별들을 x좌표 순으로 정렬한 배열을 star[]라 하고, 별 b에 대해 왼쪽에 있는 별들의 집합을 left, 오른쪽에 있는 별들의 집합을 right라고 정의합시다. 그러면 부분문제의 답은 (left 중 b보다 높은 별의 개수)*(right중 b보다 높은 별의 개수)가 됩니다. b=star[0]일때 left는 공집합이고, right는 b보다 오른쪽에 있는 별들의 집합입니다. b=star[i]일때 left에는 star[i-1]의 left에 새로운 원소들이 추가되고 right에는 star[i-1]의 right에서 몇몇 원소가 빠집니다. 이런식으로 left에는 원소를 추가하고 right에는 원소를 삭제해가며 각 부분문제별로 (left 중 b.y보다 높은 별의 개수)*(right중 b.y보다 높은 별의 개수)를 구해줄 수 있습니다.
O(N log N)인 이유
집합 left, right를 펜윅트리나 Binary Search Tree등의 자료구조로 표현하면 (원소의 추가/삭제) 및 (~보다 큰 원소의 개수) 등의 연산들이 O(logN)에 가능하고, 추가/삭제할 원소들은 인치웜?으로 알수있으므로, 부분문제는 amortized O(logN)에 해결됩니다. N개의 부분문제가 있으므로 전체 시간복잡도는 O(NlogN)입니다.
여담
곱셈할 때 Integer Overflow가 날 수 있으니 주의하세요! 답이 long long은 안넘어가는데 넘어가는줄알고 모듈러 조건을 넣어버렸네요...그래도 데이터 다시만들기는 귀찮아서 냅뒀습니다.
N^2 솔루션도 부분점수를 드리고 싶었으나, 대회가 ACM-ICPC룰이라 그럴 수 없었네요. N^2은 생각했는데 펜윅(혹은 세그)트리를 몰라서 풀지 못하신 분들께 심심한 위로를 전합니다.
F. 두더지가 정보섬에 올라온 이유
solved: x out of y
writer: 주영준
O(N^2)
트리의 노드의 갯수가 N개 일때, 모든 경로를 뽑으면 N^2이며, 이것을 계산하는데는 N^2이면 충분히 할 수 있다.
어떻게 하냐면 모든 노드를 하나씩 루트로 잡아 자식노드까지의 경로의 최솟값을 계속 더해가면 답이 나올 것이다.
3
5
2
1
4
3
2
1
5
4
O(N*W)
다이나믹 프로그래밍(DP)를 이용하면 O(N*W)로 줄일수 있다. 문제에서 N이 10^5, W가 10^2이기에 충분히 풀 만한 시간이 된다.
DP[node][weight] = DP[childNode][k]의 합(weight == k, 단 childNode의 edge의 가중치가 weight랑 같을 경우, k >= weight)
이렇게 잡으면 DP[node][weight]에는 node에 도착하는 경로중 최솟값이 weight인 경로의 갯수가 잡히게 된다.
그러면 이 node를 통과해서 경로를 만드는 경우를 dp[node][weight] 값을 이용해 구할 수 있다. 그러면 시간 복잡도가 dp의 모든 값을 다 도는 경우이니 O(N*W)만에 할 수 있다.
O(NlogN)
이문제는 disjointSet을 이용하면 NlogN으로도 풀 수 있다.
간선 중 가장 큰 간선을 골라가며 disjointSet을 만들면 간선을 고를때 마다 그 간선을 가중치가 최소로 되는 경로의 갯수를 구할 수 있다.
그렇게 가장 큰 간선부터 가장 작은 간선까지 모든 간선을 disjointSet에 추가하면서 값을 구하면 된다.
** 참고로 이문제는 Integer값을 넘어 가게 되니 64bit-Integer를 사용하기 바란다.
G. 라쿤이 정보섬에 올라온 이유
solved: x out of y
writer: 조민석
전형적인 최대 유량 문제
문제를 해결하기 위해서, 최대 유량(Maximum Flow) 알고리즘을 사용 할 수 있습니다.
먼저 솜사탕 무게를 노드로 생각해 봅시다. 다음과 같은 그래프를 얻을 수 있습니다.
0
1
2
K-1
....
....
A
흐르는 유량 1을 라쿤 한마리의 행동이라고 생각을 하면, 솜사탕을 받는 행위를 다음과 같은 간선들로 나타낼 수 있습니다.
현재 무게로부터, (현재 무게 + 배급받을 무게) mod K 인 노드에 연결해줍니다.
서류 제한을 나타내기 위해서, 간선의 용량은 '배급받을 무게의 솜사탕 종류 수'로 설정합니다.
0
1
2
K-1
....
....
A
배급 받을 수 있는 솜사탕 한봉지 무게가 1, A, K 인 경우, 그래프는 위와 같고, 1로 향하는 용량은 2, A로 향하는 용량은 1이 됩니다.
(간략하게 0 노드에 대해서만 나타내었음)
스티커를 사고, 붙이는 것도 다음과 같이 생각 할 수 있습니다.
새로운 솜사탕 노드들을 한겹 더 만듭니다.�이 노드들은 스티커를 있는상태를 의미하며, 바로 서류에 붙여서 스티커가 없는 상태로 돌아갈 수 있습니다.�(파란 간선 : 스티커 구매, 빨간 간선 : 서류에 붙이기, 점선 : 스티커를 사용하지 않음)
0
1
2
K-1
....
....
A
0
1
2
K-1
....
....
A
문제 설명대로, 이 간선들에도 적절한 용량을 부여 할 수 있습니다. (해보세요!)
이제 Source 와 Sink 노드를 연결할 차례인데, 지금까지의 설명을 잘 따라왔다면, 충분히 해결 가능하다고 생각합니다. (해보세요!)
0
1
2
K-1
....
....
A
0
1
2
K-1
....
....
A
최종 그래프는 다음과 같습니다. (간략화 되었음)
0
1
2
K-1
....
....
A
0
1
2
K-1
....
....
A
SRC
SNK