https://codeforces.com/contest/1628
A를 봤는데 막막했다. 그래서 일단 D부터 잡았고(사실은 standing을 봤는데 Petr가 D1을 4분만에 풀었길래 풀만해 보여서) $O(nm)$ 풀이는 15분정도에 나왔으나 D2도 딱히 어려워보이지 않아서 일반화를 거친 후 45분만에 D1 D2를 모두 AC 받았다. 다만 시간 패널티를 고려해봤을 때, 앞으로는 이런 문제에서 D1을 일단 빨리 맞는 편이 나을 것 같긴 하다. 아무튼 그 이후에 A를 세그 2개씩 써야 하는 건가 할 정도로 뇌절하다가 그냥 하면 된다는 걸 깨닫고 30분이나 걸려 AC를 받았다. 이후 B를 잡았는데 도저히 모르겠어서 C로 넘어갔다가 그냥 하면 된다는 걸 깨달았지만, 대충 짜다가 컷당하고 다시 일반화시켜 AC를 받았다. 그러고 나서 B 풀이를 종료 10분 전에 알았지만 짜다가 결국 맞지 못하고 끝나버렸다. 충분히 평정심을 유지했다면 100등에서 150등 사이도 가능했을 것 같은데, 결국 270등이라는 아쉬운 성적으로 마무리했다. 분명 D1 D2를 맞을 때만 해도 100등 정도에 퍼포 2800정도였는데 말이다. 그래도 39나 올랐다. 2270.
A
배열이 주어지고, 앞에서 적당히 $k$를 골라 MEX 값을 계속 새로운 배열에 추가한다. 배열을 모두 쓸 때까지 이 행위를 반복할 때, 새로운 배열 중 사전 순으로 가장 큰 배열은?
생각해보면 현재 남아있는 숫자들의 MEX값이 앞의 $k$개의 값에 대한 MEX값과 같을 때 자르면 된다. 처음에 각 숫자의 개수를 세고, 0인 위치를 찾고, MEX 값을 구한 후 그 값보다 작은 숫자들의 인덱스 중 최댓값을 찾는 것으로 생각하여 엄청난 뇌절을 했다. 세그 2개 짜고 이제 연산을 시작하는데, 생각해보니 새로운 배열의 원소의 총합이 $n$을 넘을 수 없더라. 그래서 그냥 처음에 MEX를 구하고 chk배열을 만들어서 MEX보다 작은 숫자가 모두 등장하면 그 숫자를 추가한 뒤 MEX를 다시 찾으면 된다. 이렇게 해도 시간 안에 들어간다.
B
최대 길이 3인 string들의 배열이 주어진다. 이 배열의 부분배열에 대해 순서대로 string들을 이어붙였을 때 팰린드롬이 될 수 있는가?
A를 AC 받고 이 문제를 봤는데 처음에는 dp스럽게 접근해야 된다고 생각했다. 일단 길이 1짜리는 무조건 팰린드롬이니 거르고, 이제 길이 2짜리와 3짜리만 남는데... 그러다가 C로 넘어갔다. C를 AC 받고 다시 생각해보니, 어차피 긴 팰린드롬이 있다고 친다면 맨 양옆의 2개가 무조건 팰린드롬을 형성한다. 그래서 2개에 대해서만 검사하면 되고, 간단한 케이스워크를 하면 되는 문제였다. 업솔빙에서 string 한 개가 자체로 팰린드롬인 경우와 길이 3짜리끼리 이어붙는 경우를 세지 않아 조금 고생했다.
C
짝수 $n$에 대하여 $n \times n$ 격자가 있다. 각 격자의 숫자는 모르지만, 각 격자에 대해 인접한 격자의 XOR한 값은 알 때, 전체 숫자를 XOR한 값은?
일단 체스판처럼 컬러링을 해보자. 그러면 흑에 해당하는 값들은 백에 해당하는 값들의 XOR 값이고, 이런 식이다. 우선 맨 왼쪽 윗칸을 흑색이라고 생각하고, 흑색 칸들의 전체 XOR을 구해보자. 생각해보면 적당히 겹치지 않게 흰색 칸을 골라 모든 흑색 칸이 적어도 하나의 골라진 흰색 칸과 인접하도록 하면 된다. 처음에는 그냥 맨 윗줄부터 그리디하게 고를 수 있으면 고르도록 했으나, 뭔가 잘못된 것 같았다. 그래서 그림을 조금 더 그리다가, $2 \times 2$ 단위로 잘랐을 때 각 단위 격자를 하나의 칸으로 본다면 $i \leq j, i+j \equiv 0 \mod 2$인 칸들에서 오른쪽 위를 고르고, $i > j, i + j \equiv 1 \mod 2$인 칸들에 대해 왼쪽 아래를 고르면 조건을 만족시킴을 알 수 있었다. 흰 칸에 대해서는 판을 좌우반전시키고 비슷하게 해주면 된다. 고른 칸들의 전체 XOR 값을 출력하자.
D
두 명이 게임을 한다. 처음 숫자 0에 대해, 한 명이 실수 $[0, k]$중 하나를 고르고, 다른 한 사람은 그 수를 뺄지 더할지 고를 수 있다. 이 행위를 $n$번 반복한다. 숫자를 고르는 사람은 최종 숫자를 최대화하고 싶고 더할지 뺄지 고르는 사람은 숫자를 최소화하고 싶다. 다만 더할지 뺄지 고르는 사람은 최대 $m$번 더할 수 있다. 두 사람이 최적으로 게임을 진행할 때, 최종적으로 숫자는 어떻게 되는가?
우선 숫자를 고르는 사람 입장에서 생각해보자. "최적"이라는 것이 무엇일까? 이것은 내가 현재 어떤 숫자를 주었을 때 다른 사람이 이 숫자를 더하거나 빼거나 최종적으로는 결과가 같도록 해야 된다는 것이다. 이제 어떤 게임의 상태를 (더해야 할 횟수, 빼야 할 횟수)로 생각해보자. 그러면 최종 상태는 $(0, 0)$일 것이고, 적당히 $(m, n-m)$에서 출발할 것이다. 여기서 $(0, 0)$에서 역으로 올라가며 생각을 해보자. 일단 $(i, 0)$꼴은 $ik$임이 자명하고, $(0, j)$꼴은 0임이 자명하다. 이제 다른 상태들에 대해, 생각해보면 $(i, j)$ 상태에서 어떤 수 $x$를 골랐다고 하면 $(i, j-1)$는 $(i, j)$에서 $x$를 뺀 값일 것이고, $(i-1, j)$는 $x$를 더한 값일 것이다. 이 때 이미 $(i, j-1)$, $(i-1, j)$의 답을 안다고 가정하면, $(i, j)$의 답은 $(i, j-1), (i-1, j)$의 답의 평균일 것이다. 즉, $dp_{i,j}= \frac{dp_{i,j-1}+dp_{i-1,j}}{2}$와 같은 $dp$를 하는 것이다. 이를 $O(nm)$에 구현하면 D1을 맞을 수 있다.
여기서 이제 조금 더 관찰을 하면, 결국 $(i, 0)$꼴의 값들만 적당한 계수로 더하면 된다는 사실을 알 수 있는데, 그 계수가 이항계수와 관련이 있음을 알 수 있을 것이다. 그림에 표시해가며 조금 더 생각해보면, $i=n-m$일 때 $(n-i,0)$인 상태의 계수는 $ \frac{_{i}C_{0}}{2^{i}}$, $n-m < i < n$인 $i$에 대해 $(n-i, 0)$의 계수는 $ \frac{_{i}C_{i-n+m}-_{i-1}C_{i-n+m-1}}{2^{i}}$가 계수임을 알 수 있다. 원래는 이항계수를 $2^i$꼴로 나눈 것이 계수가 되어야 하지만, 빼야 할 횟수가 0이 된 이후에는 전파(?)가 없으므로 그 없어진 전파를 빼주면 되는 것이다. 아무튼 각 계수를 알았으니 계수에 $(n-i)k$를 곱해서 더하면 된다. 팩토리얼, 그 역원, 2의 거듭제곱, 그 역원을 적당히 전처리해서 구해주자. $O(n)$에 풀 수 있게 된다.
D를 맞은 이후 ABC를 빨리 맞았다면 좋았을텐데, 아쉽게 되었다. 그래도 이제 진짜 한번만 더 올리면 인생 처음 IM이 될 것으로 보인다. 2400도 빨리 가야지..
