Good Bye, BOJ 2019! Editorial
- 운영진: leejseo, ryute, jhnah917, Lawali, ahgus89, ckw1140, cheetose, ho94949, rdd6584, gs11008, junseo, wookje, junie
- 모든 출제자 및 검수자, 대회 플랫폼을 지원해주신 스타트링크, 그리고 대회에 참가하고 지금 에디토리얼을 읽고 있는 당신께 감사의 말씀을 전합니다.
A. 겨울왕국 티켓 예매
- 출제자: jhnah917
- First solve: easrui (1분)
$N < 12$이거나 $M < 4$인 경우에는 L4가 존재하지 않고, 그렇지 않은 경우에는 $11M+4$를 출력하면 됩니다. 그리고 출제자는 아직 겨울왕국2를 보지 않았습니다.
참고로, 다음의 내용에 유의해주세요.
- L은 12번째 알파벳입니다.
B. 제야의 종
- 출제자: leejseo
- First solve: cki86201 (5분)
들은 횟수가 많은 순으로 사람들을 정렬해서 $P_1, P_2, \cdots, P_N$이라 번호 붙일 때, 각 타종을 들은 사람의 번호는 (어떤 $a_i$에 대해 $1, 2, \cdots, a_i$와 같이) 연속적으로 나타나야 합니다.
이 사실이 실제로 가능한 상황임과 필요충분조건임은 쉽게 확인할 수 있고, 이를 이용하여 단순 구현으로 문제를 해결하면 됩니다.
C. 욱제가 풀어야 하는 문제
- 출제자: ahgus89
- First solve: jihoon (2분)
정점이 $2N$개, 골라야 하는 간선 개수가 $N$개이므로 모든 정점이 간선의 양 끝점에 포함됩니다. 구해야 하는 답을 $A_N$이라 합시다.
빨간색 1번 정점은 파란색 1번 정점 또는 파란색 2번 정점과 연결됩니다.
- 앞의 경우는 나머지 $2N-2$개의 정점을 연결해주면 되므로 $A_{N-1}$가지 경우가 존재합니다
- 뒤의 경우는 파란색 1번 정점이 빨간색 2번 정점과 연결되어야 하고, 나머지 $2N-4$개의 정점을 연결해주면 되므로 $A_{N-2}$가지 경우가 존재합니다.
따라서 $A_N=A_{N-1}+A_{N-2}$라는 점화식이 성립하고, 예제를 통해 ${A_1=1, A_2=2}$임을 알 수 있으므로 DP를 통해 $A_{191229}$까지 구해 각 $N$마다 $A_N$을 출력하면 문제를 풀 수 있습니다.
D. 철도 여행
- 출제자: leejseo
- First solve: cki86201 (11분)
전체 답이 각 컴포넌트에 대한 답을 합친 것이 됨은 명백합니다. 각 컴포넌트에 대한 답은
- 컴포넌트에 홀수 차수 정점이 있다면 (홀수 차수 정점의 수)/2,
- 없다면
- 컴포넌트에 간선이 있다면 1
- 컴포넌트에 간선이 없다면 0
이 됩니다. 실제로 이 횟수만의 철도 여행으로 모든 간선을 방문하는 방법은 다음과 같습니다.
각 컴포넌트에 대해 차수가 홀수인 정점이 존재하는 동안 다음과 같은 과정을 반복합니다:
- 차수가 홀수인 정점을 하나 잡고, 해당 정점에서 시작하여 아직 사용하지 않은 간선만 사용하여 더 이상 갈 수 없을 때까지 DFS를 진행합니다.
- 그러면, 현재 있는 정점 또한 차수가 홀수인 정점입니다.
- DFS를 하며 방문한 간선을 전부 지웁니다.
- 그러면 차수가 홀수인 정점의 수가 2개 감소합니다.
홀수 차수인 정점이 없어졌는데도 간선이 남아있는 경우, 남은 간선들은 회로 몇 개의 합집합으로 표현 가능합니다. 이 회로들을 기존의 보행 중 적당한데 끼워넣어 주면 됩니다. (다른 관점으로 보자면, 오일러 회로를 이룰 때 까지 그래프에 적절하게 간선을 추가한다고 생각해도 무방합니다.)
만약, 처음부터 차수가 홀수인 정점이 없는 (간선이 있는) 컴포넌트라면 컴포넌트 자체가 하나의 회로를 이루므로 자명합니다.
E. 내 생각에 A번인 단순 dfs 문제가 이 대회에서 E번이 되어버린 건에 관하여 (Easy)
- 출제자: wookje
- First solve: arnold518 (19분)
핵심 아이디어는 문제의 그림과 같이 트리를 평면에 그리는 것입니다. 문제에서 제시한 조건에 맞게 트리의 각 노드를 좌표평면에 배치합니다. $(x, y)$ = (중위순회 번호, 트리에서의 노드 깊이)로 두면 조건에 맞게 좌표를 부여할 수 있습니다.
이제 트리가 아니라, 2차원 평면에서 직사각형 내 수들의 합을 최대화 하는 문제가 되었습니다.
일반적인 2차원 평면에서의 문제와 달리, 이 문제는 $y$좌표의 최대 범위가 약 $\log N$이라는 특수성이 있습니다. 높이의 상하한을 고정하고 maximum subarray와 비슷하게 풀거나, 루트 노드부터 스위핑하며 내려오면 $O(N \log N)$에 해결할 수 있습니다. $O(N \log^2 N)$으로 보일 수 있지만, 잘 생각해 보면 $O(N \log N)$임을 알 수 있습니다.
F. 별이 빛나는 밤에
- 출제자: ryute
- First solve: cki86201 (43분)
문제를 요약하면, 맨 위와 맨 아래에 있는 두 개의 점과 두 점 사이에 있는 선분들에 대해 점을 하나씩 잘 골라서 최대 넓이 삼각형의 넓이를 최소화 하는 문제입니다. 간단한 관찰을 통해 다음과 같은 직관적인 사실을 알 수 있습니다.
Lemma. 선분의 오른쪽 끝 점들 위에서 구한 left hull과 선분의 왼쪽 끝 점들 위에서 구한 right hull로 둘러싸인 영역을 $S$라고 하자. 최대 넓이 삼각형의 넓이가 최소가 되게 할 때의 최대 넓이 삼각형의 세 꼭짓점은 $S$와 한 점만을 공유하는 선분들의 공유점이다.
- 엄밀한 증명은 "Keikha, Vahideh & Löffler, Maarten & Mohades, Ali. (2017). Largest and Smallest Area Triangles on a Given Set of Imprecise Points."을 참고해주시기 바랍니다.
위 Lemma를 이용하면, 다음과 같은 사실을 알 수 있습니다. 이 문제에서는 맨 윗 점과 맨 아랫 점이 고정되어 있으므로 두 점이 left hull과 right hull에 모두 포함됩니다. (left hull과 right hull이 직선이 아니라고 가정합시다. 직선이라면 자명한 해법이 존재합니다.)
따라서 만약 선분이 두 점을 이은 직선과 교차한다면 $S$와 한 점을 초과하는 공유점이 생기게 되고, 이 선분을 무시할 수 있습니다. 따라서 모든 선분은 직선 왼쪽에 존재하거나, 오른쪽에 존재한다고 가정해도 무방합니다. left hull과 right hull은 맨 윗점과 아랫점이 고정되어 있으므로, 왼쪽 선분들에 대해 오른쪽 점을 정하고 오른쪽 선분들에 대해 왼쪽 점을 정합니다. 이 정해둔 점들에 대한 convex hull을 구함으로서 $S$를 빠르게 구할 수 있고, 이 위에서 최대 넓이 삼각형의 넓이를 구하면 됩니다.
최대 넓이 삼각형은 두 점을 고정하고, 한 점을 회전시켜 가면서 구할 수 있습니다. 이때 마지막 점을 삼분탐색으로도 구할 수 있지만 문제의 제한이 크므로, 투 포인터와 유사한 기법을 통해서 $O(N^2)$으로 구해야 합니다. 참고로 사용하는 모든 점들의 좌표가 정수이므로, 정답은 반드시 정수이거나 정수에 0.5를 더한 꼴이어서 실수 연산을 사용할 필요가 없습니다.
G. 최단 경로와 쿼리
- 출제자: ckw1140
- First solve: cki86201 (76분)
분할-정복 기법을 이용하여 문제를 해결할 수 있습니다.
가운데 열의 $N$개의 격자에서 시작하는 다익스트라 알고리즘을 돌리면 됩니다. 그러면 가운데 열을 기준으로 시작점/출발점이 양 옆으로 나눠지는 쿼리는 가운데 $N$개를 각각 지난다고 가정하고 풀면 정답을 구할 수 있습니다. 왜냐하면,
- 가운데를 안지나는 것도 지난다고 가정하고 풀면 갱신이 가능하고,
- 만약 최단경로가 구해지지 않았다면 실제 최단경로는 나머지 한 쪽에만 있을 것입니다.
따라서, 가운데를 지나지 않았던 쿼리들은 분할할 때 한 쪽으로 몰아주면 됩니다. 이 방법을 이용하면 $O(N^2 M \log (NM) \log M) $ 시간에 해결할 수 있습니다.
H. 쿼리와 쿼리
- 출제자: Lawali
- First solve: imeimi2000 (93분)
1번 쿼리는 다시 말하면 $L \le i \le R$인 모든 $i$에 대해 $l_i$ $r_i$ $v$의 업데이트 연산을 추가적으로 해주는 것과 동일합니다. 이 문제를 해결하려면 다음 두 가지 접근을 혼합해서 사용해야 합니다.
- 방법 a Bitwise xor연산은 자기 자신이 역원인 연산입니다. 즉 2번 쿼리를 처리할 때 이전에 나온 1번 쿼리에서 $[s,e]$에 속하는 원소의 갯수의 홀짝성에 따라 1번 쿼리의 영향을 받는지의 여부가 결정됩니다. 다시 말해, 1 $L$ $R$ $v$라는 쿼리가 2 $s$ $e$에 영향을 미친다는 것은 $[l_L,r_L]$, $[l_{(L+1)},r_{(L+1)}]$, … $[l_R,r_R]$의 모든 구간과 $[s,e]$가 겹치는 원소의 갯수가 홀수라는 것입니다. 이는 segment tree with lazy propagation을 이용하여 sweeping기법을 통해 구간합으로 오프라인 쿼리의 형식으로 구할 수 있습니다. 이것을 사용하면 시간 복잡도는 $O(Q^2\log N)$이 됩니다.
- 방법 b 1번쿼리가 들어올 때마다 저장해뒀다가 2번쿼리가 들어오면 쿼리를 전부 적용해 배열 A에 적용합니다. prefix bitwise xor를 이용하면 1번 쿼리를 $O(1)$의 시간복잡도로 저장해줄수 있고 배열 A의 구간 xor을 구하기 위해 prefix bitwise xor를 사용하면 쿼리를 한번 적용시킬 때마다 $O(N+M)$의 시간 복잡도가 됩니다. 이것을 사용하면 전체 시간 복잡도는 $O(Q(N+M))$이 됩니다.
이제 이 문제를 해결해봅시다. 우선 쿼리를 어떤 크기 $B$로 나누고 그 각 나뉜 부분을 쿼리의 구간이라고 합시다. 쿼리의 구간의 크기는 $B$가 되고, 그 갯수는 $Q/B$개가 됩니다. 같은 구간에 속하는 1번 쿼리와 2번 쿼리는 a의 방식을 이용해서 처리하고 쿼리의 구간이 끝날때마다 b를 적용시켜줍시다.
그렇게 하면 시간복잡도는 $O(Q/B*B^2\log N+Q/B(N+M))=O(QB\log N+Q/B(N+M))$이 됩니다. $QBlogN \approx Q/B(N+M)$이 되는 적절한 크기 $B$를 찾으면 대략 $B=100$이라는 것을 알 수 있고, B를 50~150정도로 잡아주면 무난하게 AC를 받을 수 있습니다.
- 참고: 만약 segment tree with lazy propagation이 아니라 fenwick tree를 이용하면 시간을 1초대로 줄일 수 있습니다.
댓글 (2개) 댓글 쓰기
jh05013 4년 전
갓
ks9509 4년 전
수고하셨습니다!!