Problem Solving Diary #22 - Codeforces Round 934 (Div. 1)

조이슥 맛 셋을 하나 돌고 싶었는데, 리프가 추천해줘서 풀었다. 딱히 시간을 재면서 풀진 않았다.

https://codeforces.com/contest/1943

A. MEX Game 1

Alice가 $[0, v]$ 사이의 모든 값을 가져갈 조건이 다음과 동치임을 보일 수 있다.

• $[0, v]$ 사이의 모든 값이 1개 이상 있다.
• $[0, v]$ 사이의 값 중 $a_1, \cdots, a_n$에 정확히 1개 있는 값이 최대 하나이다.

증명은 단순하다. 저 조건을 만족하기만 하면, Alice는 현재 남아 있는 가장 적은 값을 가져가는 그리디로 모든 값을 가져갈 수 있다. 반면, 저 조건을 만족하지 않는다면, Bob은 정확히 1개 있는 여러 개의 값 중 하나를 소진해 Alice가 해당 수를 가져가지 못하게 막을 수 있다.

 

따라서 이 조건을 만족하는 최대 $v$를 $\mathcal{O}(N)$에 구해 문제를 풀 수 있다.

B. Non-Palindromic Substring

어떤 문자열 $[l, r]$이 $k$-good substring일 조건이 다음과 같음을 보일 수 있다.

• $k=1$인 경우 불가능하다. 즉, 어떤 문자열도 $1$-good substring일 수 없다.
• $k = r-l+1$인 경우, 전체 문자열이 팰린드롬이 아닌 경우에만 가능하다.
• 위 두 경우에 해당하지 않는 경우,
  • $k$가 짝수인 경우, $[l, r]$의 모든 문자가 같은 경우 불가능하고, 아닌 경우 가능하다.
  • $k$가 홀수인 경우, $[l, r]$의 문자열 형태가 ababa…ba꼴인 경우 불가능하고, 아닌 경우 가능하다. (단, $a=b$인 경우도 고려)

증명은 간단한 케이스워크로 가능하다.

 

해싱과 누적합을 적절히 이용하여 문제를 $O(N+Q)$에 해결할 수 있다. 다만, 케이스워크가 복잡하고, 해싱에 대한 반례를 사람들이 친절하게도 데이터에 많이 넣어 놨기 때문에, 이중 해싱 등을 사용해서 회피하거나 (업솔빙 한정으로) 사람들이 잘 안 쓰는 MOD를 이용해야 한다.

C. Tree Compass

다음 전략이 최적이다.

• 트리의 지름에 있는 정점의 수가 $4$의 배수가 아닌 경우, 지름의 중심 (여러 개라면 그 중 한 점)에서 $0$부터 가장 먼 거리까지의 쿼리를 모두 날린다.
• 트리의 지름에 있는 정점의 수가 $4$의 배수인 경우, 지름의 중심 두 점에서 거리가 $1$, $3$, $\cdots$인 쿼리를 날린다.

증명은 대략적으로 이렇다. 트리가 일직선형이라면 저 위가 최적임을 보일 수 있다. 이제 지름을 제외한 다른 점들을 생각해보면, 일단 지름 위의 점을 모두 색칠해야 하므로 위의 전략 이하로 줄이는 건 불가능하고, 위 전략을 사용하면 지름의 특성에 따라 지름 밖의 점들도 모두 색칠되기 때문에 위 전략이 최적임을 보일 수 있다.

 

간단한 문제였지만 너무 많은 시간을 낭비한 것 같다. $\mathcal{O}(N)$에 문제를 해결할 수 있다.

D. Counting Is Fun

일단 배열 $A$가 주어졌을 때, 좋은 배열인지 확인하는 방법부터 생각해 보자. 이것은 간단한데, $A$를 여러 구간으로 나타낸다고 생각하면 쉽다. 이것은 구간의 집합 $S$를 만들어, $A_i$가 $S$에서 $i$를 포함하는 구간의 개수가 되도록 하는 것이다. 구간을 직접 construct하면서 생각하면 좋다. 앞에서부터 필요한 만큼 구간을 만들다가, 구간을 끊을 때는 오래 전에 만들어졌던 것부터 끊으면 된다.

 

그러나 이 방식이 항상 작동하는 것은 아니다. 작동 조건을 수식으로 간단하게 표현할 수 있을까? $A_{i-1} + A_{i+1} < A_i$인 $i$가 없으면 된다. (단, $A_0 = A_{n} = 0$이라고 가정) 따라서, 이 조건을 만족하는 것의 개수를 세어 주면 된다. D1은 이것을 $i$, $A_{i-1}$, $A_i$를 관리하는 단순한 $O(NK^2)$ DP로 해결하면 된다. 정말 나이브하게 짜면 $O(NK^3)$인데, 여기에서 $K$ 하나를 떼는 것은 어렵지 않다.

 

이제 이 조건을 만족하는 수열을 더 빠른 방법으로 찾아보자. $DP[x][y][d]$를 다음과 같이 정의하자.

• $d=0$인 경우, $DP[x][y][d]$는 $A_{x-1} > A_{x}$이고 $A_{x-1} = y$인 경우의 수를 의미한다.
• $d=1$인 경우, $DP[x][y][d]$는 $A_{x-1} \le A_x$이고 $A_{x} - A_{x-1} = y$이며 $A_{x} > A_{x+1}$가 확정된 경우 $A_x$까지의 경우의 수를 의미한다. (즉, $A_{x+1}$은 최소 $y$, 최대 $A_x - 1$이여야 한다.)
• $d=2$인 경우, $DP[x][y][d]$는 $A_{x-1} \le A_{x}$이고 $A_x = y$이며 $A_{x+1} \ge A_{x}$가 확정된 경우 $A_{x}$까지의 경우의 수를 의미한다.
• $d=3$인 경우, $DP[x][y][d]$는 $A_{x-1} \le A_{x}$이고 $A_x = y$이며 $A_{x} > A_{x+1}$이 확정된 경우 $A_x$까지의 경우의 수를 의미한다. (전제조건은 $d=1$과 같으나, $y$의 정의가 다르다.)

각각의 $d$의 용도에 대해 간단히 설명하자면, $d=0$은 $A_{x-1} > A_x$로 $A_{x+1}$에 무엇을 놓든 상관없는 상황을 나타낸다. $d=1$은 $A_{x-1} \le A_{x}$로 $A_{x+1}$에 최소 하한이 있는 경우에서, $A_{x} > A_{x+1}$로 감소하는 경우를 나타내기 위해 사용한다. $d=2$는 $A_{x-1} \le A_x$로 $A_{x+1}$에 최소 하한이 있으나, 오히려 $A_x \le A_{x+1}$로 증가하는 경우를 나타내기 위해 사용한다. $d=3$은 $d=1$을 보조하기 위해 사용한다.

이제 이 DP를 전이해주면 된다.

• $d=0$인 경우, $A_{x+1}$에 무엇을 놓든 상관이 없다. 따라서 아래와 같은 세 가지 케이스로 나눈다.
  • $d=0$으로 전이: $y$ 미만의 수를 놓는 경우 $d=0$으로 전이할 수 있다. $y' \in [0, y-1]$ 구간에 더해 준다.
  • $d=1$로 전이: $y$ 이상의 수를 놓는 경우 $d=1$로 전이할 수 있다. $y' \in [0, k-y]$ 구간에 더해 준다.
    • $d=3$으로 보조 전이: $d=3$으로 전이를 해야 한다. $y' \in [y, k]$ 구간에 더해 준다. 왜 이 전이가 필요한지는 추후 설명한다.
  • $d=2$로 전이: $y$ 이상의 수를 놓는 경우 $d=2$로도 전이할 수 있다. $y' \in [y, k]$ 구간에 더해 준다.
• $d=1$인 경우, $A_{x+1}$에 $y$ 이상의 수를 놓아야만 한다. 이때, $d=1$이므로, $A_x$ 이하의 수를 놓아야 한다는 상한 조건 역시 있다. 그러나 상한 조건은 $d=3$인 경우에서 빼주는 것으로 처리할 것이기 때문에, 일단은 $d=0$인 경우로 전이해 $y' \in [y, k]$ 구간으로 더해 주면 된다.
• $d=2$인 경우, $d=0$인 경우와 비슷하게 전이하지만 $d=0$으로의 전이를 제외해 준다.
• $d=3$인 경우, $d=1$인 경우에서 세어지면 안 되는 구간을 빼 주면 된다. $d=0$인 경우로 전이해 $y' \in [y, k]$ 구간에서 빼 주면 된다.

위 전이를 모두 처리하면 문제를 $\mathcal{O}(NK)$에 해결할 수 있다.

E1. MEX Game 2 (Easy)

A번 문제와 비슷하나, Bob이 한 번에 $K$개를 가져간다는 차이점이 있다. A번 문제는 $K=1$인 경우라고 생각하면 좋다. 문제를 이렇게 바꾸면 좋다: Alice가 $[0, m]$ 구간의 돌을 모두 가져갈 수 있음이 보장되는 최대 $m$은 얼마인가? 그리고 우리는 이 문제에 대한 $K=1$일 때의 답이 있다. $[0, m]$ 구간의 돌이 모두 존재하고, $1$개만 존재하는 돌이 하나 이하여야 한다.

 

이제 $K$가 더 커졌을 때의 상황을 생각해 보자. $m$을 고정하고, 가능성 여부를 판단한다고 생각해 보자. 이렇게 하면 실제로 필요한 것은 $f_0, f_1, \cdots, f_m$이며, 그 순서는 크게 중요하지 않다. 일반성을 잃지 않고, 편의상 $f_0 \le f_1 \le \cdots \le f_m$이라고 하자.

 

우선 첫 턴에 Alice는 $f_0$부터 $f_m$까지 중 무엇이든 확정적으로 하나를 가져갈 수 있다. 무엇을 가져가는 것이 이득일까? 당연히 $f_0$일 것이다. 남은 수들이 많을수록 Alice가 유리하기 때문이다. 마찬가지로, 굳이 첫 턴이 아니더라도, Alice는 가장 작은 수를 가져가는 것이 고정적으로 유리한 전략임을 알 수 있다.

 

그렇다면 Bob의 전략은 어떨까? Alice가 가장 작은 수를 항상 가져간다는 것을 Bob이 알고 있으므로, Bob 입장에서 가장 꺼림찍한 상황은 자신이 이미 많이 가져간 수를 Alice가 가져가는 것이다. 이러한 상황이 Bob에게 좋지 않은 이유는, 자신의 수 일부를 낭비한 셈이 되기 때문이다. 따라서 Bob은 최대한 "균등하게" 수들을 가져가야 할 것이다. 그런데 이 균등이 어떤 의미인가? 말하자면, 가장 많은 수를 한 개 제거하는 것을 $k$번 반복하는 것을 의미한다.

 

다만, 이렇게 하면 Bob이 놓칠 수 있는 경우가 있다. 예를 들어, $f$의 배열이 $[2, 3, 7]$이고 $k=2$일 때, Bob의 차례라면 Bob은 단순히 저 $2$를 가져가는 것으로 이길 수 있지만, 위 전략대로 하려면 Bob은 $7$에서 2를 감소시키며 $[2, 3, 5]$를 만들게 된다. 따라서 Bob은 '선택과 집중'을 해야 한다. 이것이 의미하는 바는, Bob이 가져갈 $f$의 집합을 전체가 아니라, $f$ 배열의 적당한 prefix $[f_0, \cdots, f_{p-1}]$로 한정시키는 것을 의미한다. 즉, 너무 개수가 많은 수들은 Bob이 가져가도 딱히 의미가 없으니 그들은 양보하고, 가장 개수가 적은 수들 몇 개만 없애는 전략을 사용하겠다는 것이다.

 

이런 식으로 코딩을 하면 가능성 판별 한 번을 $\mathcal{O}(N^2)$ 정도에 할 수 있고, 하나의 테스트 케이스를 $O(N^2 \log N)$에 해결할 수 있다. 이걸로 Easy를 해결할 수 있다. (Easy는 $\mathcal{O}(N^3 \log N)$으로 코딩해도 맞는 것 같았다.)

 

Hard부터는 감이 안 온다.