Good Bye, BOJ 2019! 에디토리얼

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

이 됩니다. 실제로 이 횟수만의 철도 여행으로 모든 간선을 방문하는 방법은 다음과 같습니다.

각 컴포넌트에 대해 차수가 홀수인 정점이 존재하는 동안 다음과 같은 과정을 반복합니다:

  1. 차수가 홀수인 정점을 하나 잡고, 해당 정점에서 시작하여 아직 사용하지 않은 간선만 사용하여 더 이상 갈 수 없을 때까지 DFS를 진행합니다.
  2. 그러면, 현재 있는 정점 또한 차수가 홀수인 정점입니다.
  3. DFS를 하며 방문한 간선을 전부 지웁니다.
  4. 그러면 차수가 홀수인 정점의 수가 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개) 댓글 쓰기



ks9509 4년 전

수고하셨습니다!!