본문 바로가기

Codeforces

Codeforces Round #594 (Div. 1)

https://codeforces.com/contest/1239

https://codeforces.com/blog/entry/70720 (Editorial)

원래는 문제를 풀 생각이 아니었지만, 스코더보드의 상태가 흥미로워서(tlwpdus 2등, ainta 4등, D가 B보다 많이 풀림) 문제를 보다가 다 풀어버렸다.

 

 

A. Ivan the Fool and the Probability Theory

$N\times M$크기의 격자가 있다. 이 격자를 검은색과 흰색으로 칠하려고 한다. 이때, 인접한 4칸 중 같은 색인 것이 2개 이상인 칸이 없도록 하려고 한다. 이렇게 칠하는 경우의 수는?

대체적으로 체스판처럼 칠하되, 인접한 두 칸이 같은 색인 경우가 조금씩 있는 형태이다. $(x, y)$와 $(x, y+1)$의 위치의 칸이 둘 다 검은 색이라 하자. 그러면 $(x, y-1), (x, y+2), (x-1, y), (x-1, y+1), (x+1, y), (x+1, y+1)$이 모두 흰색이어야 한다. 여기서 주목할 점은 $(x-1, y), (x-1, y+1)$이 흰색이고, $(x+1, y), (x+1, y+1)$이 흰색이라는 점이다. 이 논리를 반복하면, 모든 $i$에 대해 $(i, y), (i, y+1)$이 같은 색이 된다. $(x', y'), (x'+1, y')$이 같은 색일 경우, 모든 $j$에 대해 $(x', j), (x'+1, j)$가 같은 색이 된다. 만약 이러한 $y$과 $x'$가 모두 존재한다면, $(x', y), (x', y+1), (x' + 1, y), (x' + 1, y + 1)$이 모두 같은 색이 되어서 모순이다. 따라서 $(i, y), (i, y+1)$이 같은 색이 되게 할 $y$들을 적당히 고르거나, $(x', j), (x'+1, j)$이 같은 색이 되게 할 $x'$들을 적당히 고르는 문제가 된다. 그 경우의 수는 피보나치 수열과 같다. 따라서 답은 $F_N+F_M-1$이다.

 

 

B. The World Is Just a Programming Task (Hard Version)

문자 '(와 ')' $N$개로 이루어진 문자열이 있다. 이 문자열에 $k$-cyclic shift를 하면 뒤쪽 $k$개의 문자가 앞으로 이동한다($0\leq k \leq N-1$). 문자열의 beauty란, $k$-cyclic shift를 했을 때 올바른 괄호 문자열이 만들어지는 $k$의 개수이다. 이 문자열의 $i$번째 문자와 $j$번째 문자를 바꾸는 연산을 하려고 한다. 이 연산을 한 번만 beauty를 최대화하기 위해서는 어느 위치에 연산을 시행해야 하는가?

'('의 개수와 ')'의 개수가 다르면 어떠한 cyclic shift를 하더라도 beauty는 0이다. 따라서 '('와 ')'의 개수가 같은 경우만을 고려하자. '('는 +1, ')'는 -1로 생각한 후 prefix sum을 구하자. 그러면 이 문자열의 beauty는 prefix sum의 최솟값이 등장하는 횟수이다. 예를 들어, ')(()))()(('의 prefix sum은 [-1, 0, 1, 0, -1, -2, -1, -2, -1, 0]이고, 최솟값 -2는 2번 등장하므로 beauty는 2이다. '('와 '('를 바꾸거나, ')'와 ')'를 바꾸는 연산은 의미가 없다. 따라서 '('와 ')'를 바꾸는 연산만을 생각하자. 이 연산을 시행하면 +1 하나가 -1로 바뀌고, -1 하나가 +1로 바뀌므로, 특정 구간의 prefix sum이 2만큼 감소한다. 따라서 특정 구간에 연산을 시행한다고 생각하자. 연산을 시행하기 전 최솟값은 $mn$이라 하자. 연산을 시행한 구간 안에 $mn$이 하나라도 있었다면, 연산을 시행한 후의 최솟값은 $mn-2$가 되고, 그 개수는 원래 있던 $mn$의 개수보다 작거나 같다. 따라서 연산을 시행하는 구간은 $mn$을 포함하면 안 된다. 이제 케이스를 2가지로 나누자.

 

1. 연산을 시행한 구간 안에 $mn+1$이 존재하는 경우:  새로운 최솟값은 $mn-1$이 되고, 그 개수는 연산을 시행한 구간에 있던 $mn+1$의 개수이다. 

2. $mn+1$이 존재하지 않는 경우: 최솟값은 여전히 $mn$이고, 그 개수는 연산을 시행한 구간에 있던 $mn+2$의 개수만큼 증가한다.

 

따라서 첫번째 케이스와 두번째 케이스로 나누어 문제를 풀면 된다. 첫 번째 케이스는 $mn$을 포함하지 않는 maximal 구간들에 연산을 시행해보면 되고, 두 번째 케이스는 $mn, mn+1$을 포함하지 않는 maximal 구간들에 연산을 시행해보면 된다.

 

 

C. Queue in the Train

기차에 $N$개의 좌석이 일렬로 있고, 각 좌석에는 $1$에서 $N$의 번호가 붙어있다. $i$번 자리에는 $i$번 승객이 있다. $1$번 좌석 옆에는 정수기가 있다. 모든 $i$에 대해, $i$번 승객은 시각 $t_i$에 물을 받으러 간다. 그러나 정수기는 한 번에 한 명씩만 사용할 수 있으므로 줄이 생긴다. 물을 받는데 걸리는 시간은 $p$이고, 정수기와 좌석 사이를 이동하는 시간은 고려하지 않는다. 사람들을 줄을 서는 것을 싫어하므로, $1$번 승객, $2$번 승객, ..., $i-1$번 승객 중 한 명이라도 좌석에 없을 경우(줄을 서있거나 물을 받는 중)에는 $i$번 승객이 줄을 서러 가지 않고 기다린다. 만약 두 승객이 동시에 줄을 서러 가려고 할 경우, 둘 중 번호가 작은 사람만이 가고 번호가 큰 사람은 더 기다리게 된다. 각 승객이 언제 물을 받게 될지 구하여라. 

문제를 제대로 이해하기만 하면 푸는 것은 그다지 어렵지 않다. 사람들을 3가지로 나눌 수 있다: 좌석에 없는 사라들, 줄을 서기 위해 기다리고 있는 사람, 그리고 나머지 사람들. 좌석에 없는 사람들은 queue 등의 자료구조 관리하고, 줄을 서기 위해 기다리고 있는 사람들은 priority_queue 등의 자료구조로 관리한다(왜냐하면 번호가 작은 사람부터 줄을 서러 가기 때문에). 줄을 서려고 기다리고 있는 사람들이 언제 줄을 서게 될지 알기 위해서, 좌석에 없는 사람들을 fenwick tree 또는 set으로 관리를 하자. 이 기차에서 일어나는 사건은 3가지가 있다: 승객이 좌석에 돌아오는 사건, 승객이 줄을 서러 가는 사건, 승객이 줄을 서기 위해 기다리기 시작하는 사건. 각각을 1번, 2번, 3번 사건이라 하자. 이 중 2번 사건은 1번 또는 3번 사건이 일어났을 때만 일어난다. 따라서 우리는 1번 사건과 3번 사건들을 시간순으로 정렬한 후 하나씩 실행하면 된다. 그러면 $O(NlogN)$으로 문제를 해결할 수 있다.

 

 

D. Catowise City

$N$명의 사람과 $N$명의 고양이가 있다. $i$번 사람과 $i$번 고양이는 서로 아는 사이이다. 이 외에에도 아는 사이인 사람들과 고양이들이 존재한다. 일부 사람들을 심사위원으로 선정하고, 일부 고양이들을 선수로 선정하여 대회를 진행하려고 한다. 이 때, 심사위원과 선수 중 아는 사이가 있어서는 안 된다. 심사위원의 수와 선수의 수는 모두 1 이상이어야 하며 그 합은 $N$이어야 한다. 조건을 만족하도록 심사위원과 선수를 선정하는 것이 가능한지 판별하고, 가능하다면 어떻게 선정해야하는지 찾아라.

$i$번 사람과 $i$번 고양이가 둘 다 선택될 수는 없다. 그리고 선택된 총 수가 $N$이어야 하므로 $i$번 사람나 $i$번 고양이 중 하나는 선택되어야 한다. $x$번 사람과 $y$번 고양이가 아는 사이라면, $x$번 사람이 선택되면 $y$번 사람이 선택되어야 하고, $y$번 고양이가 선택되면 $x$번 고양이가 선택되어야 한다. 이러한 관계를 그래프로 나타내자. 고양이들의 관계를 나타내는 그래프는 사람들의 관계를 나타내는 그래프에서 간선의 방향을 모두 바꾸면 된다. 따라서 사람들 사이의 관계를 나타내는 그래프만 생각하자. 이 그래프에서 $1$개 이상 $N-1$ 이하의 정점을 골라서, 선택된 정점에서 도달할 수 있는 정점들은 모두 선택되었도록 해야한다. 이는 2-SAT 문제와 비슷하다. 따라서 그래프에서 SCC들을 구하자. SCC가 1개라면 조건을 만족하도록 선택하는 것이 불가능하다. SCC가 2개 이상이라면, 그 중에서 outdegree가 0인 SCC 하나만을 고르면 된다(선택 방법은 다양할 수 있다). 그러면 $O(N)$에 문제를 해결할 수 있다.

 

 

E. Turtle

$2\times N$ 격자가 있다. $(i, j)$ 격자에는 $a_{i, j}$개의 양배추가 있다. 거북이는 아래와 오른쪽 방향으로만 이동하며 $(1, 1)$에서 $(2, N)$까지 가고, 그 경로에 있는 양배추를 모두 먹는다. 거북이는 먹는 양배추의 양이 최대가 되는 경로를 선택한다. $2N$개의 수가 주어졌을 때 이 수들을 잘 배치해서, 각 칸에 그 수만큼의 양배추를 놓았을 때 거북이가 먹는 양배추의 양을 최소화하여라.

위쪽 칸에 놓을 수들과 아래쪽 칸에 놓을 수들을 정했다면, 위쪽 칸은 오름차순으로, 아래쪽 칸은 내림차순으로 놓는 것이 최적이다. 거북이가 가는 경로를 정하기 위해서는 수 $x$를 정하면 된다. 거북이는 $(1, 1), (1, 2), ..., (1, x), (2, x), (2, x+1), ..., (2, N)$으로 이동한다. 이 경로상에 있는 수들의 합을 $f(x)$라 하자. $f(x+1)-f(x)=a_{1, x+1} - a_{2, x}$이다. 따라서 $f(x+1)-f(x) < f(x+2)-f(x+1)$임을 알 수 있다. 이것은 $f(x)$의 그래프가 아래로 볼록하다는 것이다. 따라서 $f(x)$의 최댓값은 $x=1$ 또는 $x=N$일 때이다. $x=1$일 때와 $x=N$일 때를 비교하면, $(1, 1)$과 $(2, N)$은 항상 지나게 되고, 어느 경로를 선택하는지에 따라 $2N-2$개의 칸 중 $N-2$개의 칸을 지난다. 따라서 $(1, 1)$과 $(2, N)$에는 가장 작은 수 2개를 놓고, $2N-2$개의 수들은 합이 가능한 비슷한 $N-1$개의 두 집합으로 나누면 된다. 이것은 dp를 통해서$O(AN^2)$으로 풀 수 있다($A$는 $a_{i, j}$의 최댓값). 

 

 

F. Swiper, no swiping!

$N$개의 정점과 $M$개의 간선으로 구성된 무방향 연결 그래프가 주어진다. self-loop, multi-edge는 없다. 이 그래프에서 $1$개 이상 $N-1$개 이하의 정점들을 지우고, 그와 연결된 간선들도 지울 것이다. 그렇게 해서 남은 그래프에서 각 정점의 degree가 지우기 전의 degree와 3으로 나눈 나머지가 같게 하려고 한다. 이렇게 지우는 것이 가능한지 판별하고, 가능하다면 어떻게 지워야하는지 방법을 찾아라.

간단한 케이스 몇 가지를 생각하자. 그리고 그 외의 경우는 안된다는 것을 보이자. 원래 그래프에서, degree를 3으로 나눈 나머지가 $k$인 정점을 $k$번 정점이라 하자.

 

1. 0번 정점이 존재하는 경우: 이 정점만을 남기고 전부 지우면 된다.

 

2. 2번 정점들만으로 이루어진 사이클이 존재하는 경우: chordless 사이클 1개만을 남기고 전부 지우면 된다.

1, 2번에 해당하지 않는다면, 2번 정점들이 forest를 이루고 그 사이를 1번 정점들이 연결하고 있는 형태일 것이다.

 

3. 2번 정점들로 이루어진 하나의 트리에 대해, 두 종류의 1번 정점이 연결되어 있는 경우: 두 1번 정점 사이을 잇는 최단 경로 하나만을 남기고 지운다.

이제 남은 상황은, 2번 정점들로 이루어진 모든 트리들이 각각 하나의 1번 정점에만 연결된 형태이다. 트리의 리프는 모두 1번 정점으로 연결이 되어있을 것이다. 따라서 1번 정점을 포함하는 사이클이 생기게 된다.

 

4. 두 개 이상의 트리에 연결된 1번 정점이 존재하는 경우: 두 트리에 대해서 1번 정점을 포함하는 chordless 사이클을 찾는다. 이 사이클 두 개의 합집합만을 남기고 전부 지우면 된다. (8자 모양)

 

이제 그 외의 상황은 발생하지 않음을 보이자. 1~4번 경우가 모두 안 된다는 것은, 그래프의 각 component가 2번 정점들로 구성된 트리와 1번 정점 하나로 이루어진다는 것이다. 한 component에서 2번 정점의 개수가 $k$개라 하자. (이 component에서 간선의 개수) = (2번 정점 사이를 잇는 간선의 개수) + (1번 정점과 2번 정점을 잇는 간선의 개수)이다. (간선의 개수) * $2 \equiv 2k + 1 (\textrm{mod } 3)$, (2번 정점 사이를 잇는 간선의 개수) $=k-1$, (1번 정점과 2번 정점 사이를 잇는 간선의 개수) $\equiv 1(\textrm{mod } 3)$. $2k+1 \equiv 2(k-1) + 2$에서 모순. 따라서 이러한 상황은 발생하지 않는다. 

 

1~4의 상황에 해당했지만, 아무 정점도 지우지 않아야 하는 경우(ex. 그래프 전체가 chordless 사이클 1개이면 2번 상황에 해당한다)에는 답이 없는 것이다. 이를 고려하여 구현하면 된다. $O(N)$에 해결할 수 있다.

 

* chordless cycle: 사이클의 정점 사이를 잇는 간선 중 사이클에 속하지 않는 간선이 없는 사이클.

'Codeforces' 카테고리의 다른 글

Codeforces Global Round 5  (0) 2019.10.24
Codeforces Round #591 (Div. 1)  (0) 2019.10.18
Codeforces Round #588 (Div. 1)  (0) 2019.09.28