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

2월 9일~2월 15일 코드포스 후기입니다.
버추얼만 5번 돌아서 마참내 오렌지를 달성했습니다.
이제 당분간 코드포스를 안 할 예정인데, 그 이유는 밑에 설명하겠습니다.

Codeforces Round 1078 (Div. 2)

A번
n - n/w가 답입니다.
체감 난이도: B2

B번
각 bank마다 transition되지 않고 남아 있어야만 하는 루비의 수를 구합니다. 남아 있어야만 하는 루비의 수가 최댓값인 은행으로 모든 루비를 보내는 것이 최적입니다.
체감 난이도: S5~S3

C번
관찰: n이 주어졌을 때 가능한 Informativity의 값은 n의 약수들 뿐이다. 즉 최대 O(sqrt(N))가지의 Informativity만 확인하여도 충분하다.
Informativity가 정수 x로 주어졌을 때, 한 문자 c가 존재해서 한 string의 1번째 원소가 c이고, 한 string의 k+1번째 원소가 c이고...를 만족하는지 확인하면 됩니다.
저는 구현에서 별의별 실수를 다 해서 3틀을 했는데, 그 정도로 문제가 어렵거나 구현이 빡세지는 않습니다.
체감 난이도: G3 이상, 하지만 solved.ac 기준 G5~G4일 것 같습니다.

D번
주어진 2차원 배열을 위에서 아래로, 오른쪽에서 왼쪽으로 탐색해 봅시다. 탐색하면서 찾은 1의 개수가 전체 1의 개수의 절반이 되는 순간이 최적입니다.
즉 note의 이미지 기준으로 답이 각각 DRRRDRRDDD, DDRRRRDDD입니다.
체감 난이도: G5 (C보다 쉬웠습니다.)

E번
소스를 뿌리지 않는 경우를 가정한다면, 2차원 dp를 이용해서 O(nm)에 답을 구할 수 있습니다: dp[i][j] = max(dp[i-1][j],dp[i][j-1]) + a[i][j]
편의상 이 녀석을 정방향 dp라고 부르겠습니다.

소스를 뿌리는 경우를 가정한다면, 문제를 두 가지 경우로 나눌 수 있습니다.
1) 소스가 뿌려진 위치를 지나가는 경우
2) 그렇지 않은 경우

1번 경우에 대해서는, (n,m)에서 (1,1)로 가는 최단 경로를 구하는 dp를 이용하면 해결할 수 있습니다.
편의상 이 녀석을 역방향 dp라고 부르겠습니다.

2번 경우에 대해서는, 한 가지 관찰이 필요합니다.
관찰) (i,j)를 거치지 않고 (1,1)에서 (n,m)으로 가려면, 0이 아닌 정수 k에 대해서 (i+k,j-k)를 통과해야만 한다.
(i+k,j-k)를 통과하는 경우의 최댓값은 정방향, 역방향 dp의 합 - a[i+k][j-k]입니다.
이 값을 모든 k에 대해서 빠른 시간에 구하려면 누적 maximum을 대각선 방향으로 구해 주어야 합니다.
예를 들어서 (4,3)의 누적 maximum은 max(f(4,3), f(5,2), f(6,1))입니다.

정방향/역방향 dp를 구한 뒤 누적 maximum을 구해 주면, (i,j)에 소스를 뿌리는 경우 얻을 수 있는 최대의 pleasure를 O(1)에 구할 수 있습니다.

체감 난이도: G1~P5

F1번
편의상 트리의 루트를 1번 노드로 하겠습니다.
트리에서 하나의 서브트리를 잘라내었는데 그 서브트리의 노드들에 적힌 값을 xor하면 b[i]가 나온다고 합시다. 이것을 편의상 b[i]를 사용하였다고 하겠습니다.

관찰: b[i]를 홀수 번, 짝수 번 사용했는지만 의미가 있다. 즉, b[i]를 2번 사용한 것은 0번 사용한 것과 같은 상태로 취급할 수 있다.
b[i]를 2번 더 사용하더라도 잘라내진 노드들의 값을 xor한 것은 변하지 않습니다.

저는 여기서 각 노드마다 각 b[i]를 홀수 번/짝수 번 사용했을 때 경우의 수를 기록하는 dp를 생각했습니다. 즉 O(n * 2^k)만큼의 메모리를 사용합니다.
각 상태마다 남아있는 노드들의 값을 xor한 것은 일정합니다. 즉 O(1)에 b[i]를 현재 정점을 루트로 하는 서브트리에 사용할 수 있는지 판단할 수 있습니다.

우선 각 child들이 가지고 있는 2^k개의 상태를 xor convolution으로 합쳐 줍니다. 즉 k의 child를 c1, c2라 한다면 dp[k][i^j] += dp[c1][i] * dp[c2][j]...와 같은 식입니다. child가 2개보다 많은 경우도 같은 방식으로 해 주면 됩니다.
그 다음에 b[i]를 적용할 수 있으면 dp[k][x^(1<<i)] += dp[k][x]를 적용해 줍니다. dp[k][x]의 값을 따로 저장해 놓고 더해 줘야 정확한 구현이 되겠습니다.

체감 난이도: P3~P1

후기
총합 7틀을 하면서 겨우겨우 6솔을 했고 118등으로 대회를 마쳤습니다. C/E/F1에서 각 2/2/3틀을 했는데, C에서 2틀은 하면 안 되는 WA였습니다. 여기서 퍼포먼스를 상당히 깎아먹었습니다. 라운드 종료 이후 2181이라는 퍼포먼스를 받았습니다. 아무리 7틀을 하고 F1을 대회 종료 5분 전에 풀었다 해도, Clist.by 기준 2200이 넘는 문제를 풀고 2181이라는 퍼포먼스는 상당히 낮았습니다. 딥2가 전체적으로 상향 평준화되서인지 원래는 빠르게 5솔하면 2200~2300정도 퍼포를 받을 받을 수 있었지만 이제는 오렌지 퍼포도 안 됩니다. 딥2의 (셋 퀄리티/참가자 실력) 상향 평준화를 느낄 수 있었던 셋이었습니다.
Enjoyment: 7.3/10

Educational Codeforces Round 183

A번
x + i가 3의 배수인 최소의 i를 출력하면 됩니다.
체감 난이도: B4~B3

B번
제거할 수 있는 top card의 최대 개수 / bottom card의 최대 개수를 구하면 됩니다. k = n인 경우 무조건 모든 카드를 제거할 수 있음에 유의해야 합니다.
체감 난이도: B1~S5

C번
Monocarp가 할 수 있는 연산을 다음과 같이 변환해 봅시다.
"시작 지점에서 처음 i개를 지운 뒤, 처음 j개를 다시 되돌려 놓는다."

처음 i개의 원소들 중 a의 개수 - b의 개수를 c[i]라 합시다.
c[i] - c[j] = c[n]인 i,j중 i-j의 최솟값을 구하면 됩니다.

c[i] = k인 i의 최댓값을 관리하면 O(n)에 구할 수 있습니다.
체감 난이도: G5~G4

D번
길이 n인 수열에 대해서 n(n-1)/2 - (Inversion value)를 Correct value라고 합시다. 수열 [1, 2, ..., m]의 Correct value는 m(m-1)/2입니다.

Correct value를 구하는 과정은 Inversion value를 구하는 과정에 비해서 매우 간단합니다.
연속하는 증가하는 구간들에 대해서 각 구간의 길이를 l이라 하면 l(l-1)/2의 합을 구하면 됩니다.

이제 dp[n][k]를 길이 n인 수열의 Correct value가 k일 수 있으면 1, 아니면 0이라 합시다. dp[i][j]가 1이면, dp[i+1][j], dp[i+2][j+1], dp[i+3][j+3]...이 1이어야 합니다.
처음에 dp[0][0]=1로 놓고 돌려주면 dp[n][k]를 구할 수 있습니다.

주어진 Inversion value k에 대해서 dp[n][n(n-1)/2-k]가 1인지 아닌지 판단하고, 1이면 거꾸로 거슬러 올라가면서 어떤 방식으로 Correct value가 k가 되게 했는지 알아낼 수 있습니다.
체감 난이도: G1~P5

E번
유저의 preference를 max(a[i]-ac, 0) + max(d[i]-dr, 0)이라 합시다. preference가 n을 초과하면 편의상 n+1로 통일하겠습니다.

x[i]를 preference가 i인 유저의 수로 정의합시다. 우리는 x[0] + ... + x[i] < i+1인 최소의 i를 구해서 x[0] + ... + x[i]를 출력할 것입니다.
y[i] = x[i] - 1로 정의합시다. 이제 y[0] + ... + y[i] < 0인 최소의 i를 구한 뒤 i+1 + (y[0] + ... + y[i])를 출력할 것입니다.
z[i]를 y[0] + ... + y[i]로 정의합시다. 이제 z[i] < 0인 최소의 i를 구한 뒤 i+1 + z[i]를 출력할 것입니다.

배열 z를 레이지 세그를 이용해서 관리하고 구하고자 하는 답을 이분 탐색으로 찾으면 모든 쿼리에 대한 답을 O(n + m log^2 n)에 구할 수 있습니다.

체감 난이도: P2~P1
태그를 봤더니 더 쉬운 풀이가 있는 것 같은데, 일단 저는 이 풀이가 가장 직관적이었습니다.

F번은 풀지는 못했지만, '대충 2520 * 10개의 정점을 가지는 그래프를 가지고 풀면 되지 않을까'라는 발상을 했습니다. 에디토리얼을 보니까 행렬 제곱을 이용하는 풀이가 있던데, 어떻게 저런 풀이로 이어지는지는 모르겠습니다.

후기
A~E까지를 51분만에 0틀로 풀어냈습니다. F번은 30분 이상 박았지만 풀이에 이르는 유의미한 관찰을 내지 못했습니다.
Clist.by 기준 어떤 지점이 있어서 그 지점을 기준으로 문제를 대회 시간에 풀 수 있는 확률이 크게 낮아지는 것 같습니다. 아마 2200~2400 사이에 있는 것 같습니다.
퍼포는 2239를 받아서 버추얼 계정 레이팅이 2076까지 올랐습니다. (codeforces-anytime.firebaseapp.com에서 가상의 레이팅을 확인할 수 있습니다.)
저번 셋과 마찬가지로 딥2의 상향평준화를 크게 느꼈습니다.
Enjoyment: 7.5/10

Codeforces Round 1079 (Div. 1)

A번
2/3 <= p/q < 1이면 Bob이 항상 승리합니다.
전략: Alice가 고르는 것의 반대되는 수를 고른다.

1 <= p/q이면 Alice가 항상 승리합니다.
전략: 항상 q를 고른다.

p/q < 2/3이면 Alice가 항상 승리합니다.
전략: 항상 p를 고른다.

체감 난이도: S2

B번
문제를 살짝 변형해서, a[i] * a[j] = |j-i|인 i,j의 쌍을 구해 봅시다.

wlog, a[i] >= a[j]. a[i] >= sqrt(n)이면 최대 n / a[i] <= sqrt(n)개의 인덱스만 관찰해도 됩니다.
a[i] < sqrt(n)이면 최대 a[i]개의 인덱스만 관찰해도 됩니다.

j < i인 경우에 a[i] = a[j]인 경우도 세 주고, i < j인 경우에는 a[i] = a[j]인 경우를 세지 않으면 a[i] = a[j]인 경우를 한 번만 셀 수 있습니다.

체감 난이도: G3~G2

C1번
모든 정점 i에 대해 "1 i"는 하나의 경로로 존재하고, 모든 간선 i -> j에 대해 "2 i j"는 하나의 경로로 존재합니다.
이분 탐색을 n+m번 해서 "1 i"와 "2 i j"를 모두 찾아내면 됩니다.

체감 난이도: G4?

C2번
관찰: ? x 이후 ? x+1 쿼리를 날리면 둘 중 한 개의 정보를 얻을 수 있다.
- 새로운 간선
- 어떤 정점 p에서 시작하는 경로의 개수
새로운 간선이 나오지 않는다면, 사전순으로 정렬했을 때 x번째 경로와 x+1번째 경로의 교집합은 x번째 경로보다 strict하게 짧습니다.
그러면 x번째 경로의 끝에 등장하는 점 p에서 시작하는 경로의 개수 route[p]를 알 수 있습니다. 다음에 점 p를 만나게 된다면 route[p]개만큼의 경로를 생략해도 됩니다.

새로운 간선은 최대 m개, p에서 시작하는 경로의 개수는 최대 n개 구해야 하므로 n+m번의 쿼리로 정점 p에서 시작하는 경로의 개수를 구할 수 있습니다.
그 과정에서 존재하는 모든 간선을 한 번씩은 탐색하고 지나가므로, p에서 시작하는 경로의 개수가 모두 특정되었다면 현 시점에서 구한 그래프를 출력하면 됩니다.

체감 난이도: P? (Rough하게 P3 정도 돼 보이지만 매우 부정확합니다.)

후기
D번은 해결하지 못했고, 나중에 에디토리얼을 보니 어떤 그리디를 사용해서 해결해야 한다고 합니다. 왜 성립하는지는 잘 모르겠습니다.
D번의 Clist.by 기준 난이도는 2467인데, 확실히 2400을 넘어가는 문제들에 대해서는 올바른 방향으로 접근하는 것 조차 힘듭니다.
언젠가 코포 수련보다는 앳코더 or OI 문제들을 풀면서 더 어려운 문제들에도 접근할 수 있도록 연습하는 것이 필요해 보입니다.
그래도 A~C2까지 플래로 추정되는 것들은 전부 풀어냈고, 퍼포 2117을 받아서 양수 델타에 성공했습니다.

Enjoyment: 7.5/10

Codeforces Round 1077 (Div. 1)

A번
관찰: 배열의 최댓값을 mx, 최솟값을 mn이라 하자. mx-a[i] >= k or a[i]-mn >= k이면 a[i]는 움직일 수 있지만, 아니라면 a[i]는 움직일 수 없다.
움직일 수 있는 원소들끼리는 서로 정렬할 수 있지만, 움직일 수 없는 원소들은 정렬된 상태로 있어야만 합니다.
주어진 piggy integer k에 대해 움직일 수 없는 원소들이 정렬된 상태인지는 O(n log n), 또는 충분한 전처리를 통해 O(log n)에 확인할 수 있습니다.
k에 대해 이분 탐색을 하면 풀 수 있습니다.

체감 난이도: G5~G3

B번
관찰: p = x or q = y일 때가 항상 최적이다.
wlog p = x, p에서 사용하던 비트 (1<<i)를 q로 옮기면 (즉, p += (1<<i), q -= (1<<i) |p-x|는 (1<<i)만큼 증가하지만 |q-y|는 최대 (1<<i)만큼 감소합니다.
즉 p = x일 때보다 더 최적일 수 없습니다.

p = x일 때 |q - y|의 최솟값, q = y일 때  |p-x|의 최솟값을 각각 구하면 됩니다.

체감 난이도: G3

C번
관찰 1: 제리는 각 정점 i에서 갈 수 있는 정점들 중 정점 번호가 최대인 쪽으로 가는 것이 최적이다.
문제에서 주어진 그래프의 제약 조건에 의해 위 관찰이 성립합니다.
관찰 1을 통해 주어진 그래프를 정점 n을 루트로 하는 트리로 해석할 수 있습니다.

관찰 2: 톰의 처음 위치를 t, 제리의 처음 위치를 j라 하면, dist(t,n) <= dist(j,n)이면 톰은 항상 제리를 잡을 수 있다. 즉, 톰이 제리를 잡을 수 있는 경우의 수는 (n*n + (dist(t,n) = dist(j,n) = 1인 경우의 수)^2 + ... + (dist(t,n) = dist(j,n) = n인 경우의 수)^2 - 2 * n)/2이다.

관찰 3: 톰이 항상 n번 정점으로 가서 기다린다고 가정하면, 문제에서 요구하는 답을 O(n)에 구할 수 있다.

톰이 i번 정점에서 제리를 잡는 경우의 수를 a[i]라고 하고, i번 정점에서 "처음" 제리를 잡을 수 있는 경우의 수를 b[i]라고 합시다.
a[i]는 관찰 2와 작은 집합에서 큰 집합으로 합치는 테크닉을 사용해서 O(n log n)에 구할 수 있다고 생각했고, b[i]는 a[i]에서 i번 정점의 모든 child u에 대해 b[u]의 합을 빼면 구해집니다.
전자에서 어떤 문제가 있거나, 제 풀이가 충분히 효율적이지 않아서 TLE를 여러 번 받고 던졌습니다.

에디토리얼에서도 식 정리를 다르게 했지만 결국 작은 집합에서 큰 집합으로 합치는 테크닉을 사용해야 된다고 합니다.
아마 제가 구현을 이상하게 해서 틀린 것 같은데, tag:작큰인 문제들을 백준에서 찾아서 풀어봐야겠습니다.
AC를 받고 나면 체감 난이도가 P2~P1일 것 같습니다.

후기
C번을 푸는 데 필요한 모든 관찰을 했고 작큰이라는 알고리즘까지 발상했지만 해당 알고리즘을 사용하는 문제를 거의 안 풀어서인지 구현에서 AC를 받지 못했습니다.
평소에 저는 내 발상력 < 내 구현력을 주장하고 있었는데, 요즘 풀이를 내고 구현에서 터지는 경우가 조금씩 생기고 있습니다.
ICPC 셋은 그래도 괜찮게 돌고 있으니까 발상력이 늘어서 이런 거겠죠??

암튼, 작큰처럼 기본 티어가 플래 이하임 AND 내가 아직 모름 에 해당하는 알고리즘들을 더 연습해야겠습니다.
Enjoyment: 7.7/10

Codeforces Round 1051 (Div. 2)

A번
주어진 배열을 증가수열 하나와 감소수열 하나로 쪼갤 수 있으면 가능, 아니면 불가능입니다.
체감 난이도: S4~S3

B번
b[i]가 최소인 바우처부터 적용하면 됩니다.
체감 난이도: S4~S3

C번
관찰: 각 간선에 부여된 가중치 쌍 (x,y)에 대해 항상 max(x,y)를 선택할 수 있다.
x와 y의 대소 관계에 따라 각 정점의 가중치 간의 대소 관계 n-1개를 만듭니다. 위상 정렬을 통해 각 정점의 가중치를 결정하면 됩니다.
체감 난이도: G3

D1번
관찰: b[i] > b[j] > b[k]이면서 i < j < k인 경우가 존재하면 b는 good한 수열이 아니다.
다음과 같은 dp를 발상했습니다.
dp[i][j][k]: a[1]~a[i]까지의 good subsequence들 중 최댓값이 a[j]이고 b에 더 이상 a[k] 미만의 원소들을 넣을 수 없는 경우의 수
즉 a[k]를 포함하고, 최댓값이 a[j]이면서 a[x] > a[y]인 x<y가 존재하고 y들에 대해서 a[y]의 최댓값이 a[k]인 good subsequence의 개수입니다.
이 dp 테이블을 O(n^3)에 완성할 수 있습니다.

체감 난이도: G1?

D2번
관찰: b가 good subsequence라면 b를 감소하지 않는 부분수열 2개 x,y로 쪼갤 수 있다.
dp[i][j]: x.back() = i, y.back() = j인 경우의 수
이 때, 항상 i > j인 경우만 생각해야 중복 없이 처리할 수 있습니다.
새로운 a[k]를 만났을 때, a[k] >= i이면 a[k]를 x 맨 뒤에 추가할 수 있습니다. 즉 dp[k][j] += dp[i][j] for i in [0,k], j in [0,i-1] (예외로 (i,j) = (0,0)은 가능)
j <= a[k] < i이면 a[k]를 y 맨 뒤에 추가할 수 있습니다. 즉 dp[i][a[k]] += dp[i][j] for i in [a[k+1],n], j in [0,a[k]]
O(n^3)처럼 보이지만 세그나 루트질을 통해서 제곱로그 또는 O(n^2.5)로 시간복잡도를 줄여서 해결할 수 있습니다.

체감 난이도: P2~P1

E번은 이렇다 할 관찰을 내놓지 못하고 풀지 못했습니다.

후기
D2가 많이 어려워서인지 D2를 여러 번 틀린 뒤에 풀었음에도 2151이라는 퍼포먼스를 받았습니다.
풀이 발상하는 난이도도 난이도지만 1 차이 오류와 같이 실수할 건덕지가 너무 많아서 여러 번 틀렸던 것 같습니다.
한편 이 셋을 마지막으로 버추얼 계정의 가상 레이팅이 2100을 넘겼습니다. 이제는 코포를 계속 도는 것보다는 2400+ 문제들을 해결할 수 있는 능력을 키워야겠습니다. 당분간 코포를 돌지는 않을 것 같습니다.
Enjoyment: 7.0/10

결론

지난 2~3주동안 1주일에 3번 이상씩 셋을 꾸준히 돌았는데, 이번 주에는 1번을 제외하면 모두 오렌지 이상 퍼포먼스를 받았고 결국 가상 레이팅도 2100을 찍었습니다.
다만 "작큰과 같이 잘 할 줄 모르는 플래 이하 알고리즘이 존재함"과 "2400 이상 난이도의 문제는 접근도 못하고 폭사함"이라는 한계도 느낄 수 있었습니다.
즉, 지금까지는 발상하지 못했던 새로운 아이디어들을 접하면서 해결할 수 있는 문제의 범위를 넓히는 것이 필요합니다.
당분간 OI 문제들을 풀거나 문자열 알고리즘을 공부하는 등 원래 생판 몰랐던 것들을 새로 알아나가는 시간을 가져야겠습니다.
그리고 미뤄뒀던 ICPC 셋 후기도 내일 올려야겠습니다.

감사합니다.