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

앞으로는 매주 많은 양의 셋을 돌고 후기를 한 번에 적으려고 합니다.

오늘은 이 6개의 셋에 대해서 후기를 작성하겠습니다.

Codeforces Round 1076 (Div. 3)

A번 풀이는 굳이 작성하지 않겠습니다.

체감 난이도: B3

B번

일반적으로 [1, 가장 큰 원소의 위치]를 flip하면 되는데, 가장 큰 원소의 위치가 1인 경우 그 원소를 떼놓고 뒤쪽 배열만 생각하면 됩니다.

체감 난이도: S4~S3

C번

a[i] = max(a[i+1], b[i])를 뒤에서부터 적용하면 됩니다.

체감 난이도: S3~S2

D번

관찰: Difficulty를 a[i] 중 하나로 하는 것이 최선이다.

배열 a를 정렬하고, Difficulty를 a[i] 중 하나로 정한 뒤 i번과 그 뒤의 검들로 몇 스테이지까지 갈 수 있나 확인합니다. (아마 이분 탐색을 사용하는 것이 편할 것입니다.)

체감 난이도: S1~G5

E번

에라토스테네스의 체와 비슷한 방법으로 구현하면 될 것 같이 보입니다.

dp[i]를 "i를 만드는 데 필요한 최소의 원소 개수"라 합시다.

배열에 중복된 원소를 제거해 주고, 남은 a[i]에 대해서 dp[j*a[i]]=min(dp[j*a[i]],dp[j]+1)을 적용해 주면 답이 나옵니다.

체감 난이도: S1~G5

F번

관찰 1: X축 방향으로의 이동은 항상 Bx-Ax번 일어난다.

관찰 2: 같은 X좌표를 가진 집들에 대해서 "y좌표가 최솟값인 집을 먼저 방문하고 위로 올라가기", "y좌표가 최댓값인 집을 먼저 방문하고 밑으로 내려가기" 중 하나가 최선이다.

Ax,Bx를 제외하고 서로 다른 x좌표가 k개 있다고 합시다.

dp[k][0]/dp[k][1]: k번째 x좌표까지 방문했고, 현재 위치가 x좌표가 "k번째 x좌표"인 집들 중 y좌표의 최솟값/최댓값일 때 Delivery time의 최솟값

으로 dp를 잡아 주면 해결할 수 있습니다.

체감 난이도: G3~G2?

G번

문제를 잘못 읽어서 해결하지 못했습니다.

셋을 돌고 나서 에디토리얼을 봤는데, x 또는 y를 찾는 것이 아닌 x~y 사이에 있는 한 점만 찾으면 되는 것이었습니다.

출제자는 Euler Tour Technique을 적용한 뒤 1번째 방문한 점과 2번째 방문한 점, 3번째와 4번째...에 대해 쿼리를 날리는 것을 정해로 제시했습니다. 아마 문제 내용을 알고 있었어도 저 발상을 하지 못했을 것 같습니다. 꽤나 자연스러운 발상이어서 셋에서 챙겨갈 부분인 것 같습니다.

체감 난이도: P2? idk

 

후기

이 셋에서 챙겨가고자 했던 것은 "구현 실수를 줄여서 WA를 최소화한다"였습니다. 결과적으로 F까지 해결하면서 WA 등 틀린 코드를 한 번도 제출하지 않았으므로 목표를 달성했다고 해야겠습니다. G를 해결하지 못한 것은 아쉽지만, 에디토리얼을 보고 아이디어 하나를 얻어갈 수 있다는 점에서 긍정적으로 평가합니다. 다만 G번 자리에 플래 하위 정도 문제를 놓고 H번 자리에 G번을 넣었다면 어땠을까 싶습니다. 인접한 문제의 난이도가 3~4단계 이상 급발진하게 되면 사람들의 스킬셋에 따라서 쉬운 문제들을 푼 뒤 그 다음 문제에서 아예 벽을 느껴서 불만을 가질 수 있다고 생각합니다. B~F 사이 난이도 폭을 약간 늘리고 G, H를 조금 더 쉽게 했으면 좋았겠습니다. 출제자 입장에서는 올솔 방지용으로 냈을 수도 있고 딥3 연습하러 온 딥2~1 사람들에게 Challenging한 문제를 제공하고 싶었을 수도 있기에 아예 이해가 안 되지는 않습니다.

Enjoyment: 7.5/10

 

Codeforces Round 1075 (Div. 2)

매우 좋은 퀄리티의 셋이므로, 풀이를 보기 전에 셋을 돌아보는 것을 추천합니다.

A번

a[i]를 min(h,l) 이하인 것들이 x개, min(h,l) 초과 max(h,l) 이하인 것들이 y개로 나누면 x < y일 때 x, 기타 경우에는 (x+y)/2가 답입니다.

체감 난이도: S4~S3

B번

롤백을 하지 않는 경우 갈 수 있는 최대의 거리와, (a[i]*b[i]-c[i])의 최댓값을 구해 잘 버무려 주면 됩니다.

체감 난이도: S3~S2

C번

Easy Version: p[n] = 1로 하고 p[2] ~ p[n-1]에 대해서 p[i] = i^1로 설정하면 중복 없이 완성할 수 있습니다.

Hard Version: n = 2^k꼴인 경우는 불가능. Easy Version과 마찬가지로 p[n] = 1로 하는데, n이 짝수인 경우에는 n^1 > n인지라 n을 n^(n-1)번째에 배치합니다. 이렇게 하면 p[1]만 남게 되는데, 지금까지 사용하지 않은 값 r이 어떤 수든 간에 1 <= r^1 <= n, r^1 != r입니다. 따라서 p[1] = r으로 두면 됩니다.

체감 난이도

Easy Version: S1~G4

Hard Version: G2~P5 (만약 Easy Version을 풀고 도전한다면, G2 이하)

D번

우리는 p를 다음과 같은 방식으로 구현할 것입니다.

1~i까지를 먼저 만들고, i+1을 두 숫자 사이, 또는 만들어진 순열의 맨 앞 또는 맨 뒤에 끼워넣는다.

w[i+1] = 1인 경우, i+1을 끼워넣는 경우는 2가지가 있습니다: 맨 앞 또는 맨 뒤만 가능합니다. 중간에 끼우게 되면 w[i+1] = 0, w[i+2] = 1이 됩니다.

w[j] = 1, w[j+1]~w[i] = 0, w[i+1] = 1인 경우를 생각해 봅시다.

j-1까지를 만들고 나서, 다음 조건을 만족해야 합니다.

- j+1은 i+1까지 완성된 수열의 맨 앞 또는 맨 뒤에 와야만 합니다.

- j+2~i+1이 맨 앞 또는 맨 뒤에 올 수 없습니다.

j+1 ~ i+1까지 순서대로 배치한다고 가정하겠습니다.

j+1을 배치하는 방법 2가지, j+2~i+1 사이 k에 대해서 k를 배치하는 방법이 k-1가지 있으므로

w[j+1]~w[i+1]을 만족하게 j+1~i+1을 배치하는 경우의 수는 2 * (j+1) * ... * (i-1) * i가지입니다.

여기서 다음 관찰을 할 수 있습니다.

"w[i] = 0이면 답에 i를 곱하고, w[i] = 1이면 답에 2를 곱한다"

이 방식으로 Easy Version을 해결할 수 있습니다.

 

Hard Version은 Easy Version과 마찬가지로 생각하면 됩니다.

답을 c로 나눈 나머지가 0이 되면 안 되므로, ?를 제외하고 구한 답을 c로 나눈 나머지를 먼저 구한 뒤 c와의 gcd를 구합니다.

그 gcd를 g라 하고, d = c / g라 합시다.

d가 홀수면, ?를 w[1]만 제외하고 1로 대체해도 됩니다.

d가 2의 제곱수이면, ?의 인덱스가 짝수인 것부터 먼저 0으로 대체하면서 d를 2로 나눠줍니다. ?의 인덱스가 홀수인 것들은 d = 2가 되어 2로 나누면 안 되는 경우를 제외하고 2로 대체합니다.

이 과정에서 d가 1이 되면 -1을 출력합니다.

 

체감 난이도

Easy Version: P5~P3?

Hard Version: P3~P1 (Easy Version을 정해로 해결했다면, P4 이하)

 

E번부터는 문제를 읽어보지 않았습니다.

 

후기

겨울방학 시즌에 연습하면서 돈 셋들 중 가장 만족스러웠습니다. 특히 D번에서 답을 얻어내는 과정은 복잡하지만, 얻어낸 답은 매우 간결한 점이 좋았습니다. C번에서도 나름 좋은 아이디어를 관찰할 수 있었습니다. Weak Example이나 너무 복잡한 구현 등 운빨 요소가 거의없었습니다.

Enjoyment: 9/10

 

Codeforces Round 1069 (Div. 1)

A번

t에서 s에 등장하는 알파벳들을 s에 등장하는 빈도만큼 제거한 문자열을 t'이라 하겠습니다. t'을 정렬하고, 순서대로 출력합니다.

s[i] <= t'[j]이면 s[i]를 출력하고 다음 s[i]로 넘어가면 됩니다.

체감 난이도: G4~G3

 

B번

셋을 돌 때에는 풀지 못했지만, 다음과 같은 관찰을 했습니다.

관찰 1: 항상 a[i], k 또는 0을 선택하는 것이 최선이다.

관찰 2: 선택하는 수의 값은 0을 제외하면 계속 증가해야 한다.

위와 같은 관찰을 바탕으로 (현재 인덱스, 선택한 수의 최댓값, 남은 카드의 수)를 관리하는 O(nk^2) 또는 O(nk^3)의 dp를 발상했습니다. 정해의 시간복잡도가 O(nk)라 생각하여서 최적화를 계속 시도하다가 실패했습니다.

다음 관찰을 하지 못해서 문제를 풀지 못했습니다.

관찰 3: a[i]를 선택하게 된다면 a[i] 중 가장 먼저 등장하는 것을 선택하는 것이 이득이다.

위 관찰을 통해서 최대 k개의 수만 유의미하게 되었습니다. 이제 시간복잡도를 O(k^3)으로 줄일 수 있습니다.

체감 난이도: P3 이하

 

C번은 확률론 문제인데 B번만 보다가 관찰도 내놓지 못하고 셋이 끝났습니다.

 

후기

셋 자체로만 놓고 보면 망한 셋입니다. 가져갈 수 있는 점이 별로 없었습니다. 퍼포먼스도 1700대를 내면서 Positive Delta도 챙기지 못했습니다. B번에서 관찰 3은 충분히 할 수 있는 관찰이었는데, 1시간 정도 투자하고서도 해내지 못한 것이 아쉽습니다. 셋 자체의 퀄리티는 좋?아 보입니다. 문제를 실제로 풀지 않아서 잘 모르겠지만, B번을 푸는 아이디어와 C번의 Statement를 읽어 보면 꽤나 좋은 셋이었던 것 같습니다. 이렇게 허무하게 흘려보내서 아쉽습니다.

Enjoyment: 5.5/10

Codeforces Global Round 30

A번

a[i]의 최솟값 <= x <= a[i]의 최댓값이면 가능하고, 아니면 불가능합니다.

체감 난이도: S5~S3

B번

짝수가 2개 이상이면, 항상 가능합니다.

짝수가 1개이면, 그 수와 다른 수들을 비교해 보고 가능하면 ok, 불가능하다면 홀수만 있는 경우와 동일하게 취급합니다.

홀수만 있는 경우, a[i] <= 2 * a[i-1]이면 (i-1,i)를 선택해서 가능합니다.

a[i] > 2 * a[i-1]인 i는 최대 30개 존재할 수 있으므로, 길이가 30(넉넉잡아서 60) 이하인 것과 그렇지 않은 것으로 나누어서 처리합니다.

체감 난이도: G4

C번

c[i] > 0인 몬스터와 c[i] = 0인 몬스터로 나누어서 생각합시다.

관찰 1: c[i] > 0인 몬스터의 경우 b[i] <= a[j]인 최소의 j에 대해 j번째 검으로 타격하는 것이 최선이다.

priority_queue를 이용해서 위 관찰대로 구현해 줍니다.

c[i] = 0인 경우에는 체력이 낮은 몬스터부터 순서대로 처리해 주면 됩니다.

체감 난이도: G4~G3

D번

관찰 1: s를 t로 변환할 수 있다면, t[i] = s[j] for some j in [1,i]. 또한, 각 t[i]에 대응하는 j를 a[i]라 한다면 a[i]는 단조증가한다.

관찰 2: k = max(i - a[i])

k의 값을 지정해 준다면, k번 연산 이하로 s를 t로 변환할 수 있는지 O(n)만에 확인할 수 있습니다. 이분 탐색으로 최소한의 k를 구합니다.

이후 s[i] = t[i]이면 s'[i] = s[i], 아니라면 s'[i] = s[i-1]을 적용하는 방법으로 해결할 수 있습니다.

체감 난이도: G2~P5

E번

못 풀었으나, 문제에서 요구하는 관찰을 대부분 시간 내에 했습니다.

관찰 1: 답은 (edge의 weight의 합) + 2번 연산을 수행하면서 생긴 cost의 합의 최솟값이다.

관찰 2: 차수가 홀수인 정점들 2k개를 k개의 선(2번 연산)으로 이어주면 된다.

관찰 3: Union-Find, 또는 이와 유사한 자료 구조를 사용해서 하나의 트리를 만들고, x와 y를 잇는 cost가 lca(x,y)부터 루트를 잇는 경로에서 찾을 수 있는 cost의 최솟값이 되게 하면 문제를 해결할 수 있다.

관찰 3을 "Reconstruction Tree"라는 것을 이용해서 구현할 수 있다고 하는데, 처음 보는 자료구조를 이용하는지라 못 푸는 것이 정배였던 것 같습니다.

체감 난이도: P3 이상

 

후기

풀 수 있는 문제들은 다 풀었고, E번에서 막히긴 했지만 필요한 관찰들은 다 했다는 점에서 만족했습니다. Reconstruction Tree라는 것에 대해서 나중에 알아보고 관련 문제들을 풀어봐야겠습니다. 셋 자체의 퀄리티는 만족스러웠고 추천할 만한 셋입니다.

Enjoyment: 8/10

 

Codeforces Global Round 31

A번

gcd(l,b)를 k라 하면, l%k + l-k번 선물을 최대로 받을 수 있습니다.

체감 난이도: S4

B번

a[i]를 앞에 두는 것과 뒤에 두는 것을 각각 비교하고 lexicographically smaller한 것을 선택하면 됩니다.

체감 난이도: S3~S2

C번

k가 홀수라면 n을 k번 출력하면 됩니다.

k가 짝수라면, k>30일 때 n을 (k-30)번 출력하고 시작하겠습니다.

k = min(k,30)이라 하겠습니다.

남은 30여개의 출력할 수 a[1], ..., a[k]에 대해

1. n의 최상위 비트부터 시작해서, 1인 비트가 있으면 a[i] 중 하나의 그 비트를 0으로 바꾼다. (최대한 중복되지 않는 방향으로)

2. 0인 비트가 있으면 그 비트를 1로 바꿀 수 있는 수들이 몇 개 있는지 세고, (x개라고 합시다) (x/2*2)개의 수들의 그 비트를 1로 바꾸어 줍니다.

이후 a[i]들을 출력하면 답이 나옵니다.

이 문제에 대해서 할 말이 많습니다.

1. 가장 직관적인 해에는 반례가 있는데, 그 반례를 찾는 것이 매우 힘듭니다.

맨 처음 발상한 해는 k가 짝수일 때 하나를 0으로 출력하고 나머지를 k로 출력하는 것이었습니다. "21 4"가 주어졌을 때 "19 6 21 21"이라는 반례가 있습니다.

그래서 두 개의 수들만 제외하고 나머지를 k로 출력한 뒤, 위에 정해와 같은 방법을 적용해 보았습니다. "341 4"에서 반례가 나왔습니다.

정해를 알지 못하는 입장에서 위 반례를 찾아내는 것은 상당히 어렵습니다.

2. 반례가 있음에도 불구하고 Example에 직관적인 해에 대한 반례가 없습니다.

문제 자체의 아이디어 자체는 나쁘지 않습니다. 하지만 매우 직관적으로 보이는 오답이 존재하고 그에 대한 반례를 알고 있으면 Example에 넣어서 많은 사람들이 폭사하는 일을 안 만들었어야 한다고 생각합니다. 대회 중간에 스코어보드를 확인했는데, 1200명이 제출했지만 정답자 수는 두 자릿수에 불과했습니다. 이것이 정상적이라고는 생각되지 않습니다.

3. B와 C 사이의 난이도 차이가 매우 심합니다.

C번의 Clist 기준 난이도는 1800입니다. 평균적인 C 치고도 어려운 편에 속하는데, B가 쉬운 편에 속하는지라 둘 사이 난이도 차이가 매우 심해졌습니다. 블루 미만의 사용자들에게는 "A번B번빨리풀고C에서폭사하기" 대회가 된 것 같습니다. 80% 가량의 참가자들이 블루 이하라는 점을 고려한다면 현재 C번을 D번으로 미루고 조금 더 쉬운 문제를 준비하는 것이 나았을 것 같습니다.

 

D번은 정해와 유사한 그리디를 발상했지만, 2번 WA를 받고 던졌습니다. CP를 연습하는 입장에서 셋을 던지는 모습이 바람직하진 않습니다. 하지만 C번을 풀고 나서 D번에서도 막히니 이 셋을 더 잡고 있을 동기부여가 되지 않았습니다.

 

후기

만약 본인이 코포 민트 or 그린이라면, 이 셋을 돌지 않는 것을 추천합니다. 이 셋을 돌 시간에 차라리 딥4 버추얼을 연습하는 것이 나을 것입니다. 딥4에는 이 셋 기준 A번~C번 난이도가 7~8개씩 있으니 연습에는 더 도움 될 것 같습니다.

Enjoyment: 3/10

 

이렇게 1월 29일부터 1주일 반동안 6개의 셋을 돌았습니다.

셋을 돌면서 가져갈 수 있는 점들이 있었습니다.

- 본인이 CP 연습을 하고자 한다면, 문제를 틀리지 않는 방향으로 쉬운 난이도의 셋을 연습하는 것이 필요합니다. 옛날 딥2~3을 파먹는 것이 상당히 도움이 될 것입니다.

- Reconstruction Tree에 대해 공부할 필요가 있어 보입니다.

- ETT를 적용하고 in[i]가 1인 것과 2인 것, 3인 것과 4인 것...을 이어 주면 방문하지 않았던 점 정확히 2개를 방문한다는 사실이 있습니다. 흥미로운 아이디어라 생각됩니다.

- 업솔빙을 거의 하지 않고, 하더라도 시간 날 때 생각하다가 모르겠으면 풀이 까는 방식으로 진행했습니다. 몇 시간씩 문제를 붙들면서 자력솔을 시도하는 것보다 실력 상승이 덜하겠지만 스트레스를 적게 받으면서 새로운 아이디어들을 발견할 수 있는 계기가 될 것 같습니다.

 

다음 주에도 웬만하면 1일 1셋을 실천하고, 주말에는 ICPC셋과 함께 후기를 업로드하겠습니다.

감사합니다.