Codeforces Round 1002 (Div. 2)

https://codeforces.com/contest/2059

문제 풀이

A. Milya and Two Arrays

00:04

$a$나 $b$ 배열중 어느 한 배열에 서로 다른 원소 3개 이상인 배열이 하나라도 있으면 yes를 출력할 수 있다. 일반성을 잃지 않고 서로 다른 원소가 3개 이상인 배열이 a라고 하고, 서로 다른 원소 3개를 각각 $a_i$, $a_j$, $a_k$ ($a_i<a_j<a_k$)라고 하자. 이 원소 3개에 매칭할 $b$의 원소도 크기 순서대로 각각 매칭 시켜주면 각각의 $a$원소에 대응되어 새로 생성되는 $c$배열의 항목들에 대해서 대소관계가 유지되기 때문이다.

그리고 이 외에도 $a$, $b$ 배열 모두 서로 다른 원소가 2개 이상이면 yes를 출력할 수 있다. 각각 $a_i$, $a_j$, $b_k$, $b_l$ ($a_i<a_j, b_k<b_l$) 이 존재한다고 가정하자. $a_i+b_k<a_i+b_l<a_j<b_l$ 혹은 $a_i+b_k<a_j+b_k<a_j<b_l$ 가 만족됨을 쉽게 보일 수 있다.

나머지의 경우는 모두 no이다.

• 문제를 처음 읽고 A번을 빨리 풀어야 된다는 생각에 당황해서 감으로 제출해서 낸 코드가 패널티 없이 accept 되었다. 아이디어는 $a$와 $b$를 각각 오름차순으로 정렬하고 $c$를 $c_i=a_i+b_{(i+1)\mod{n}}$으로 구성하는 것이다. 작은 원소는 작은 것끼리, 큰 원소는 큰 것끼리 합치면 좋지 않을까 하는 막연한 발상에서 시작됐는데, 당시 엄밀한 증명은 하지 않았지만 콘테스트 이후에 풀이를 적으면서 발견했는데 주어진 $a$, $b$의 모든 원소는 같은 값을 가지는 다른 원소가 무조건 하나 존재한다는 성질로 인해서 어찌 저찌해서 답이 구해진다는 것을 확인했다… 실력이 아니고 운이 좋았다고 말할 수 있다.
• 아니면 n이 50 이하이기 때문에 $a$에서 가능한 3개 원소의 모든 조합을 뽑고, 그리디하게 중복이 발생하지 않는 방향으로 $b$원소를 매칭시키는 방법을 사용했어도 됐을 것 같다. 어쨌든 주어진 제한을 잘 활용하는 것이 중요하니…

B. Cost of the Array

00:25

$n=k$인 경우, 배열을 자르는 경우가 유일하게 주어지므로 답을 시뮬레이션 하면 된다.

그렇지 않은 경우에는 답이 $2$를 초과하지 않을 것이라는 관찰이 필요하다. 첫번째 부분배열과 두번째 부분배열의 길이만 주어진 제한을 사용하여 조절한다고 생각해보자. 첫번째 부분배열은 새로운 배열을 구성할때 버려지고 두번째 부분배열은 새로운 배열을 구성할때 prefix로 사용될 것이다. 두번째 배열의 첫번재 원소가 될 수 있는 기존 배열 인덱스의 범위는 $[2, n-k+2]$ 이다(1인덱스 사용). 만약 해당 범위안의 모든 요소가 $1$이라면 답은 $2$다. 두번째 부분배열의 첫번째 원소가 $1$이 되는 경우를 피할수가 없지만, 두번째 원소가 $1$이 되게 만들 수 있기 때문이다. 아니라면 (범위안의 요소가 최소한 하나는 $1$이 아니라면), 답은 $1$이다. 해당 원소를 두번째 부분배열의 첫번째 원소로 사용하면 되기 때문이다.

만약 이 관찰이 어렵다면 아래 예시 두가지를 참고해보자. 정답에 영향을 주지 않는 배열의 수는 $x$로 표기함을 참고하라 ($n=8, k=6$):

첫번째는 범위 $[2,4]$안의 원소중 $1$이 아닌 원소 (4번째 원소)가 포함되어 있어 해당 원소를 두번째 부분배열의 첫 원소로 사용하여 답이 1인 경우이다.

두번째는 범위 $[2.4]$안의 모든 원소가 $1$이여서 두번째 부분배열의 첫번째 원소는 $1$로 사용하되, 두번째 원소는 $2$를 사용하지 않아 답이 2인 경우이다.

• B번치고 관찰이 조금 어려운 편이 아닌가 하는 생각이 들었다.

C. Customer Service

00:37

주어지는 $a$행렬의 모든값이 최소 $1$이라는 점이 중요한 관찰이다. 남은 $x$시간안에 $x$명의 고객이 남아있게 하려면 남은 시간동안은 매시간 1만큼의 고객을 받는 것이 유일한 방법이라는 것은 자명하다. 따라서 모든 큐에 대해서 시간 역순으로 1만큼의 고객이 연속으로 몇번 들어오는지 기록한다. 예를 들어 다음과 같은 입력이 주어졌다고 생각하자 (3번째 예제와 동일):

4번째 행(한 큐에 해당)은 끝에서 $1$이 연속으로 $2$개 있으므로 고객이 $1$만큼 연속으로 $2$번 들어온다고 볼 수 있다. $i$번째 큐가 $1$만큼 연속으로 최대 $x$번 들어올 수 있다면 $s_i=x$ 라고 하자. 위 예제는 $s=\{0,1,0,2\}$ 이다. $s$를 오름차순으로 정렬한후 그리디하게 MEX값을 최대화 하는 방향으로 $s$의 원소를 선택하면 된다 ($s$의 각 원소는 MEX 집합 구성시 사용될 수 있는 최대값을 나타내므로 필요하다면 $s$의 원소의 값에서 일부를 빼야할 수도 있음에 유의).

D. Graph and Graph

01:48

$n$이 최대 1000 정도로, 주어진 그래프 두개를 합쳐서 하나의 그래프로 만들 수 있다. 주어진 두개의 그래프를 $G_1=\{V_1,E_1\}$, $G_2=\{V_2,E_2\}$, 새로 구성할 그래프를 $G=\{V,E\}$이라고 하자. $G$의 정점은 $G_1$, $G_2$ 의 정점쌍으로 구성되어 $V = \{ (v_1 \times v_2) \mid v_1 \in V_1, v_2 \in V_2 \}$ 이고 (여기서 $(A\times B)$ 는 단순히 두 정점의 조합 tuple을 나타낸다고 생각하자), 간선은 다음과 같이 생성된다:

주의: 정점간 빼기 연산은 정점 인덱스간 빼기 연산임에 유의하라.

기존의 $G_1$, $G_2$에 반해 새로운 $G$는 유향그래프가 되기 때문에 한개의 $E_1$, $E_2$ 간선 조합마다 4개의 간선이 발생하게 된다. 간선을 타고 위치이동을 무한번 진행해도 유한의 이동 코스트를 가지기 위해서는 가중치 $0$인 사이클을 발견해야한다. 가중치 합이 $0$인 사이클에 포함된 정점에 도착하면 해당 사이클에 머무르면 되기 때문에 모두 최종 도착지 정점으로 취급할 수 있다. 가중치 합이 $0$인 사이클을 모두 발견하는 것은 새 그래프에서 간선이 0인 정점만 사용하는 식으로 DFS를 돌려 찾아낼 수 있고, 무향그래프인 기존의 $G_1$ 과 $G_2$에서 동시에 같은 인덱스를 가지는 정점쌍을 잇는 간선에 접해있는 정점들을 도착지로 취급해도 된다. 예를 들면 $G_1$에서 $i$, $j$ 인덱스의 정점을 잇는 간선이 있고 $G_2$에서도 $i$, $j$ 인덱스의 정점을 잇는 간선이 존재한다면 $G$의 $(i\times i)$, $(j\times j)$ 모두 최종 도착지라고 볼 수 있다.

시작정점이 한군데 정해져있고, 나머지 도착지들에 대해 최단거리를 구하면 되기 때문에 다익스트라를 사용하면 문제를 해결할 수 있다. 시간복잡도는 $\mathcal{O}(m_1\cdot m_2 \log{(m_1\cdot m_2)})$.

• 비슷한 유형의 문제를 풀어봤다면 문제를 읽는 순간 솔루션을 떠올릴 수도 있는 웰노운 문제이다. 2023 APC Div.1 G - K-지폐가 비슷한 유형의 문제라서 추천. 풀이는 이 블로그의 APC 2023 Div.1 참여 후기 포스트를 참조하면 된다.
• 그럼에도 불구하고 구현이 너무 느렸다… 반성

E1. Stop Gaming (Easy Version)

N/A

E2. Stop Gaming (Hard Version)

N/A

총평

12월말 시험기간 ~ 1월초 여행 등등 핑계로 1달 넘게 PS를 쉬다가 오랫만에 다시 참가한 콘테스트이다. A번 찍어 넘겨서 운좋게 퍼포먼스가 나쁘지 않았는데, 이런 퍼포먼스를 빨리 안정적으로 낼 수 있는 실력을 가지고 싶다. 오후 11시 35분에 2시간동안 PS를 하는것이 쉬운일이 아닌데, 레이팅을 따면 기분좋지만 잃으면 얻는 스트레스가 심해서 그동안 좀 피해왔던 부분이 있기도 하다. 그런것 신경안쓰고 그냥 즐겨야겠다. 어쨌든 참여도 하지 않으면 기회는 없는 것이니까…