Codeforces Round 869 (Div. 2)
A. Politics (800)
끝까지 남기위해서는 남는 사람들의 항상 모든 선택이 같아야 한다.
그렇지 않다면 어느 단계에서 분명히 탈락되기 때문이다.
$1$번이 끝까지 무조건 남아야 하므로 $1$번 문자열과 동일한 것의 개수를 세면 정답이다.
B. Indivisible (900)
$3$이상의 홀수는 불가능하다.
$\dfrac {n(n+1)}2$가 $n$으로 나뉘어지면 안되는데, $n$이 홀수라면 $(n+1)/2$ 가 정수라서 $n \mid nm$ 이 되어 불가능하다.
따라서 $1$은 가능하니까 짝수들에 대해서만 살펴보자.
뭔가 수학적 연역이 필요한 문제가 아닌 대충 찍어서 맞는지 살펴보는 풀이가 어울리는 문제이다.
짝수일 경우, $2 ~1 ~4 ~3 ~6 ~5 ~8 ~7 \cdots$ 라고 해보자. 특정 영역 $[l, r]$의 길이는 $r-l+1$ 이다.
parity가 다를 경우
길이는 $r-l+1$이고 구간의 합은 $\displaystyle \sum_{i=l}^r i = (r-l+1)(r+l)/2$ 이다.
$4,3,6,5$ 같은 부분을 보면 결국 $3,4,5,6$ 이므로 맞고 $3,6$ 같은 부분을 봐도 이건 결국 $4, 5$ 의 합과 같기 때문이다.
그런데 $(r+l)$ 항이 홀수이므로 $2$는 항상 $(r-l+1)$를 나눠야 한다.
이 경우 $r-l+1$ 은 짝수이고 $(r+l)$ 을 나누지 못하고 $(r-l+1)/2$ 도 나누지 못하므로 나눠지지 않음이 보여진다.
parity가 같은 경우
$\displaystyle \sum_{i=l}^r i=\dfrac {(r-l+1)(r+l)}2 \pm 1$ 이다.
이 경우 $r-l+1$ 은 홀수이고 $2 \mid (r+l)$이기 때문에 $r-l+1 \mid r-l+1$ 이여서 항상 나머지가 $-1$이나 $1$이 남는다.
$l < r$ 이기 때문에 구간의 길이가 항상 $2$이상이 되어 모든 곳이 나눠지지 않음이 보여진다.
C. Almost Increasing Subsequence (1500)
C. Almost Increasing Subsequence
내 풀이(간단)
모든 $1 \le i \le n-2$인 $i$들에 대해 $a_i \ge a_{i+1} \ge a_{i+2}$ 라 할 때, $a_{i+1}$ 들에 대해 구간합 배열을 만든다.
단순히 이분 탐색으로 풀어도 된다.
$[l, r]$ 쿼리가 들어오면 $[l+1, r-1]$ 구간에 저 $a_{i+1}$들이 몇개가 있는지를 보고 그 개수를 $c$라 한다면 $r-l+1-c$ 가 정답이다.
증명
항상 $a_{i+1}$를 하나 제거하면 almost increasing을 방해하는 순서가 하나 줄어든다는 것을 보이자.
일단 하나 이상이 줄어든다는 것은 자명하다. 왜냐면 그 수 자체를 없앴기 때문이다.
둘 이상 줄어들게 할 수 없다는 것을 보이면 된다.
$a_{i-1} \ge a_i \ge a_{i+1} \ge a_{i+2}$ 라 할 때, $a_{i+1}$ 를 제거해도 $a_{i-1} \ge a_i \ge a_{i+2}$ 라는 순서에 영향을 미칠 수 없다.
유사하게 $a_{i+3}$ 도 그렇다.
귀납적으로 계속 왼쪽것이 바로 오른쪽 것 이상인 경우 위와 같이 보일 수 있고, 아예 무관하게 떨어져있는 것엔 영향을 끼칠수 없으므로 둘 이상 줄어들게 할 수 없다.
따라서 $a_{i+1}$를 하나 없애면 almost increasing을 방해하는 것을 정확히 하나씩 제거할 수 있다. $\square$
에디토리얼 풀이 (접근은 다르지만 풀이 코드는 동일)
$[a_l, a_{l+1}, \dots, a_r]$ 쿼리가 들어왔을 때 $a_i < a_{i+1}$ 인 부분들을 모두 갈라보자.
예를 들어 $[4,6,7,2,2,3]$이라면 $[4], [6], [7,2,2], [3]$ 처럼 나뉜다.
모든 나눠진 subarray들은 비증가수열이다. 문제의 정의에 따라 각 subarray에서 우린 최대 두 개의 원소만 선택할 수 있다.
따라서 각 subarray에서 정답에 기여되는 개수는 $\text{min}(\lvert \text{subarray} \rvert, 2)$ 이다.
각 subarray마다 첫 원소와 마지막 원소만 취한다.
이제 첫 원소와 마지막 원소가 아닌 부분들에 대해서 $+1$를 해주고 이걸로 구간합 배열을 만든다.
이제 쿼리에서 $[l+1,r-1]$ 에 대해 연산을 한 값을 전체 길이에서 빼준다.
$[l+1, r-1]$에서 해줘야 하는 이유는 $l$과 $r$도 subarray의 처음 원소와 끝 원소로 취급해주기 위함이다.
D. Fish Graph (1900)
어찌저찌 풀다 맞았다.
$u$가 되어야 할 정점은 항상 $\text{degree} \ge 4$ 여야 한다.
그래프에 싸이클이 있고 싸이클 내의 점에서 $\text{degree} \ge 4$ 인 정점이 있다면 항상 정답은 존재한다.
$\because$ 두 개의 간선이 싸이클에 기여하고 나머지 간선들 중 싸이클에 있는 정점으로 가는 간선이 있다고 해도 그럼 더 작은 싸이클을 만들 수 있다는 말이므로 원래 싸이클에 기여하고 있던 두 개의 간선들 중 하나는 싸이클에 기여하지 않게 항상 만들 수 있기 때문이다.
에디토리얼을 열심히 읽진 않았지만 smaller cycle 어쩌구 하는말이 나오는걸 보니 대충 위에 적은 내 생각대로 증명한는 것 같으므로 스킵한다.
코드를 짜는 법은 아무 싸이클이나 찾고 거기에 $\text{degree} \ge 4$ 인 정점 $u$를 브루트포스로 찾는것이다.
그 후에 $u$의 인접한 정점들 중에 싸이클에 포함되지 않은 정점이 $2$개 이상인 경우를 선택해주면 된다.
큰 DFS를 돌리는 것이 $O(n)$이고 각 싸이클마다 검사를 해주는 것이 $O(n)$이라서 대략 $O(n^2)$면 정답을 찾을 수 있다.
Comments