코드포스 후기 (2월 4주차)

안녕하세요.

주말에 백준 한두 문제 풀고 침대에 누워만 있는 것이 너무 비생산적이라 느껴져서 코포도 조금씩 돌기로 했습니다.

총 2개의 셋을 돌았고 하나는 선방 하나는 폭망했습니다.

Codeforces Round 1082 (Div. 1)

토요일에 충분히 최근인 딥1 대회를 찾아서 쳤습니다.
다른 부대이지만 같은 생활관을 쓰는 ComPhyPark과 같이 돌았는데, 저는 4솔을 했고 ComPhyPark은 5솔을 했습니다.

A1번 (00:03 WA, 00:05 AC)

주어진 배열을 여러 개의 구간으로 나누어서 한 개의 구간에서는 맨 앞에 있는 수로부터 다른 모든 수를 만들 수 있게 해 봅시다.
그러면 각 구간은 다음 조건들을 만족해야 합니다.
조건 1: 구간의 맨 앞에 있는 원소가 나머지 원소들보다 strict하게 작아야 한다.
조건 2: 구간 a와 어떤 정수 i에 대해서 a[i] + 2 <= a[i+1]인 경우는 없어야 한다.
이 두 조건만 만족하면 하나의 구간으로 묶을 수 있습니다.

여기까지 발상했으면 구현은 자명한 편이므로 생략하겠습니다.
조건 2를 틀리게 구해서 1틀을 했고 바로 고쳐서 맞았습니다.

체감 난이도: G4~G3

A2번 (00:17 AC)

주어진 배열의 각 원소 a[i]에 대해서 a[i]가 구간의 맨 앞에 오게 되는 경우의 수를 구할 것입니다.
구간이 i 뒤쪽으로는 얼마나 길건 상관없으므로 구간을 [i,i]에서 오른쪽으로 확장하는 경우는 (n-i+1)가지가 있고, 왼쪽으로 확장하는 경우는 두 가지로 나뉩니다.
1) a[i]가 A1번에서 한 구간의 시작점인 경우
왼쪽으로는 끝까지 확장할 수 있으므로 i가지가 있습니다.
2) 이외 경우
a[i]는 전체 배열에서 i보다 왼쪽이면서 가장 늦게 등장하는 a[i]-1로부터 만들어졌습니다. 즉, 각각의 수가 가장 늦게 등장하는 위치가 어디인지 map을 이용해서 관리해 주면 이 경우도 구할 수 있습니다.
와 같이 구현해 주어서 AC를 받았습니다.

체감 난이도: P3 (A2만), G1~P5 (A1을 풀고 난 상태라면)

B번 (00:27 WA, 00:29 AC)

관찰 1) n번 미만, 또는 2n번 이상의 턴을 소모하는 경우는 없다.
전자가 성립함은 자명합니다. 후자는 다음과 같이 증명할 수 있습니다.
pf) 우선, 한 카드를 3번 이상 뒤집어 보는 없으므로 뒤집어 보는 카드의 수는 최대 4n입니다. 또한 "매칭"을 두 카드에 적힌 수가 같에 뽑는 행위라 하겠습니다.
하지만 맨 마지막 카드는 1번만 뒤집어도 됩니다. 한 턴의 첫 번째에 마지막 카드를 뒤집는 경우, 앞선 카드들에 적힌 수를 모두 알고 있으므로 바로 매칭을 할 수 있고, 1번만 뒤집어도 됩니다.
한 턴의 두 번째에 마지막 카드를 뒤집는 경우에도 앞선 카드들에 적힌 수를 모두 알고 있으므로 첫 번째에 뒤집은 카드와 매칭이 안 된다면 모순입니다. 즉 1번만 뒤집어도 바로 매칭을 할 수 있습니다.
따라서 뒤집어 보는 카드의 수는 4n 미만이고, 2n번 미만의 턴을 소모해야만 합니다.

관찰 2) 1 n 2 1 3 2 ... n n-1 순으로 카드가 배열되어 있을 때 2n-1번의 턴을 소모한다.
즉, n+k번의 턴을 소모해야 한다면 1 k+1 2 1 ... k+1 k k+2 k+2 k+3 k+3 ... n n 순으로 늘어놓으면 됩니다.

체감 난이도: P5~P4

C번 (01:23 AC)

1~i번째 문자까지 열린 괄호의 수 - 닫힌 괄호의 수를 c[i]로 정의하겠습니다.
선택한 subsequence의 끝점을 기준으로 생각해 봅시다.

끝점이 열린 괄호라면, 모든 인덱스 i에서 c[i]가 2 또는 0만큼 증가합니다.
따라서 1~i-1번까지 어떤 괄호를 subsequence의 원소로 선택하건 right shift 이후 regular bracket sequence가 된다는 사실은 변하지 않습니다.
즉 끝점 i를 선택한 경우라면 2^(i-1)가지가 가능합니다.

끝점이 닫힌 괄호라면, 인덱스 i에서 (1~i까지 열린 괄호의 수 - 닫힌 괄호의 수)가 2 미만이면서 i 직전에 subsequence로 뽑힌 괄호가 열린 괄호여서는 안 됩니다.
즉, i번과 j번을 연달아 뽑았고 i번이 열린 괄호라면, c[i], c[i+1], ..., c[j-1]은 모두 2 이상이어야 합니다.

dp[0][i]를 "i번까지 sequence에 어떤 원소가 들어갈지 결정됐고, 마지막으로 열린 괄호를 뽑은 경우의 수", dp[1][i]를 "i번까지 sequence에 어떤 원소가 들어갈지 결정됐고, 마지막으로 닫힌 괄호를 뽑은 경우의 수"라고 정의하면 O(n)에 해결할 수 있습니다. c[i]값에 유의하면서 dp배열을 채워야 합니다.

체감 난이도: P3?

D번 (Did not solve)

관찰 1) a[i] = a[j]이면 (i,i+1,j-i)는 S(b)의 원소이다.
관찰 2) k = k_max(b)인 (i,j,k) 중 j-i = 1인 것이 존재한다.
관찰 1을 잘 응용하면 증명할 수 있습니다. 저는 증명을 Proof by AC로 대체하려고 했으나, AC를 받지 못하여 Proof by Editorial로 대체했습니다.

1 <= a[i] <= n이 성립하므로 a[i] = k인 k의 최댓값/최솟값을 관리해 주면 O(n log n)에 k_max(a)를 구할 수 있습니다.

관찰 3) (i,i+1,k), (i+1,i+2,k), ..., (i+x-1,i+x,k)가 모두 S(b)의 원소이면 (i,i+x,k)도 S(b)의 원소이다.
즉, 연속되는 x개의 (j,j+1,k)가 모두 S(b)의 원소이면, x(x+1)/2개의 S(b)의 원소를 derive할 수 있습니다.
이제 "연속되는 (j,j+1,k)들을 구간처럼 관리해 주면 각 k에 대해서 k_max(a) = k일 때 f(a)의 값을 충분히 빨리 구할 수 있다"가 에디토리얼의 주장입니다.
저는 이 작업을 O(n) 미만으로 줄이지 못해서 완전히 해결하지 못했습니다.

에디토리얼은 구현 방법으로 Set을 사용하는 것을 제안하는데, 저는 에디토리얼을 봐도 잘 모르겠습니다.
clist.by 기준 2400의 난이도였음에도 문제에서 요구하는 모든 관찰을 하였다는 점에서 위안을 찾아야겠습니다.

체감 난이도: At least D5

Educational Codeforces Round 187

일요일에도 셋을 하나 잡고 돌았습니다. 4솔을 했고 E번의 모든 관찰을 했지만 구현에서 터졌습니다.

A번 (00:01 AC)

하나의 tower는 최대 1+d/m개의 박스를 포함할 수 있습니다.
따라서 (n + d/m) / (1 + d/m)을 출력해 주면 됩니다.

체감 난이도: B2~B1

B번 (00:05/00:12 WA, 00:19 AC)

관찰: F(x) = x if and only if x < 10.
따라서 x의 자릿수들을 0(맨 앞 자리라면 1)로 바꾸어서 F(x) < 10이 되게 하면 됩니다.
구현에서 말려서 2틀을 박았습니다. 최소한 E는 풀어야 본전은 찾겠다는 생각을 했습니다.

체감 난이도: S4

C번 (00:25 WA, 00:31 AC)

관찰) 길이가 n이면서 조건을 만족하는 배열이 있다면, n+1인 경우도 가능하다.
따라서 주어진 문제를 이분 탐색을 사용해서 결정 문제로 바꿀 수 있습니다.
길이가 n으로 주어졌다면, m의 가장 큰 2^i의 자릿수부터 최대 n번씩 사용하면서 합이 s가 되게 할 수 있는지 확인하면 됩니다.
이상하게 구현해서 1틀을 박았고 고쳐서 맞았습니다.

체감 난이도: S1~G5

D번 (00:36 TLE, 00:39 AC)

배열 b의 subsequence c를 Alice가 고를 수 있는 수, d를 Bob이 고를 수 있는 수라고 합시다.
관찰 ) Alice와 Bob에게 최적의 전략은 c \cap d의 원소들부터 먼저 고르는 것이다.
a의 중복된 원소들을 제거하고, 에라토스테네스의 체를 돌리듯이 해 주면 c와 d의 원소를 O(n log n + m)에 구할 수 있습니다.
구현에서 매 TC마다 2^21 크기의 배열을 새로 선언하는 바람에 TLE를 받았고, 고쳐서 AC를 받았습니다.

체감 난이도: G4~G3

E번 (많은 양의 WA, RTE, TLE)

관찰 1) Alice가 어떤 위치 i를 고르면, Bob은 i+1 또는 i-1을 고르는 것이 최적이다.
관찰 2) Alice가 위치 i를 골랐을 때, Bob이 i-1을 고른 경우 기댓값을 L(i), i+1을 고른 경우 기댓값을 R(i)라 하자. L(i)는 증가함수, R(i)는 감소함수이다.
출력해야 되는 값은 max(L(i),R(i))의 최솟값이므로 관찰 2에 의해서 L(i)와 R(i)가 만나는 지점 근방에 답이 있음을 알 수 있습니다. 즉, 하나의 배열이 주어졌을 때 세그먼트 트리와 이분 탐색을 사용해서 O(n log^2 n)에 기댓값을 구할 수 있습니다.

원소가 하나씩 추가되는 경우에는 오프라인 쿼리를 사용해서 미리 모든 원소가 추가되었을 때를 기준으로 각 원소들이 어디에 배치되는지 알아내고, 그 위치에 추가되는 원소를 업데이트함으로서 여전히 시간복잡도를 O(n log^2 n)으로 유지할 수 있습니다. 구간 최대, 최소, 합, 원소의 개수를 관리하는 구조체 세그를 이용하면 됩니다.
다만 L(i)와 R(i)가 만나는 지점을 찾기 위해서 이분 탐색을 하는 과정에서, 현재까지 주어진 원소들 중 k번째 수를 O(log n)에 구해야 했으나 O(log^2 n)에서 더 줄이지 못했고 TLE를 받은 상태에서 끝났습니다.

edit: 방금 글을 작성하면서 O(log n) 풀이가 생각났습니다. 구간 원소의 개수를 관리하는 세그에서 맨 위에서 시작하고, 왼쪽 child가 맡는 구간의 원소의 개수를 기준으로 왼쪽/오른쪽으로 내려가는 방법으로 O(log n)에 구할 수 있습니다. 이걸 왜 생각하지 못했는지는... 잘 모르겠습니다.

체감 난이도: P2~P1

D번이 골드 하위, E번이 플래 상위인지라 D번까지 빨리 풀어야 좋은 퍼포를 받을 수 있었습니다. 하지만 ABCD에서 총 4틀을 해버리면서 1900 턱걸이에 해당하는 퍼포를 받았고 -53을 먹어 버추얼 레이팅이 퍼플로 떨어졌습니다.

결론

• 2월 2주차까지 친 코포 셋에서는 2200 이상의 문제들에 대해서 제대로 된 접근조차 하지 못했습니다.
• 어제오늘 돈 셋에서는 최대 2400에 달하는 문제들도 모든 관찰을 했고 올바른 풀이를 냈습니다. 좋은 신호라고 생각합니다.

• 하지만 풀이를 내는것과 구현을 해서 AC를 받는 것은 다른 영역입니다. 제가 구현해서 AC를 받은 문제의 최고 난이도는 2050입니다.
• 높은 수준의 구현력을 유지하기 위해서 셋 돌기 or 코포/앳코더 버추얼을 주말에 계속 돌아야겠습니다.
• 아마 이 두가지가 맞물린다면 크게 말리지 않는 이상 2300 이상의 퍼포가 보장될 것입니다. 그러면 버추얼 레이팅은 2400을 찍을 수 있겠죠??

3월 중으로는 버추얼 레이팅을 2300까지 끌어올리고 기존에 진행하던 Pseudo-다이아스트릭도 이어나가는 것을 목표로 해야겠습니다.

감사합니다.