Codeforces Round 1004 후기

어제 코포에서 다시 한번 2600플마단 퍼포먼스를 받고 레이팅을 2380까지 올렸다.

 

0:00

A번을 잡았다. 인터랙티브여서 탈주하고 싶었는데 일단 문제를 읽고 생각해보기로 했다.

문제 읽으니까 바로 풀이가 나왔다.

풀이

x_i가 모두 다른 경우에는 x_i = 1인 i를 a, x_i = n인 i를 b라고 했을 때

? a b

? b a

를 출력하고 두 결과가 모두 n-1 이상이라면 B, 아니면 A

 

x_i 중 같은 것이 있는 경우에는 모든 i에 대해서 x_i != j인 j 가 존재한다.

? j ( j%n+1)

을 출력하고 0이면 A, 아니면 B

 

최대 두 번의 쿼리로 A/B를 구분할 수 있다.

 

물음표 하나 빼먹어서 프리텟 1에서 틀리는 소란이 있었지만 암튼 0:15에 AC를 받았다.

0:15

B번을 잡았다.

일단 아래 관찰은 자명하게 할 수 있다.

관찰 1

* 모든 i에 대해서 a_i >= mex(a_{i+1}, ...., a_n)을 만족시키기만 하면 된다.

* 우변의 mex값은 n을 초과하지 않는다.

위 관찰을 바탕으로 풀이를 냈다.

풀이 1

오른쪽에서 왼쪽으로 순회하며, a_i < n인 경우와 a_i >= n인 경우로 나눈다.

전자의 경우 mex <= a_i일 때에만 a_i를 부분수열에 넣어주고 mex값을 업데이트한다.

후자의 경우 a_i를 부분수열에 넣는다.

 

4

0 1 0 1

을 입력하면 2가 나오는 풀이다.

예제에서 틀려서 몇 가지 관찰을 더 하고 풀이를 냈다.

관찰 2

* 0은 최대 1개만 포함될 수 있다.

* 가장 왼쪽에 있는 0 1개만 포함하는 것이 가장 이득이다.

풀이 2

0을 0개 쓰는 경우와 1개 쓰는 경우로 나눈다.

전자의 경우에는 0이 아닌 모든 원소들을 부분수열에 포함시켜 개수를 센다.

후자의 경우에는 풀이 1대로 하는데, a_i = 0인 경우에만 가장 왼쪽에 있는 0이 포함되도록 따로 처리해준다.

 

두 방법으로 얻은 부분수열의 크기의 최댓값을 출력한다.

 

이 풀이로 AC를 받았다.

0:33

C번을 잡았다.

한 5분정도 생각하고 다음 관찰을 했다. (스포: 틀린 관찰임)

관찰 1

i번 시행까지 했고, 두 수가 같고 하나만 다른 경우, 예를 들어 P = Q라고 하자.

P의 값은 일정하다.

풀이 1

dp0[i]: i번 시행까지 했을 때 세 수가 모두 같은 경우의 수

dp1[i]: i번 시행까지 했을 때 두 수만 같은 경우의 수

관찰 1에 의해 두 수 (wlog P, Q)가 같다고 하면, P^R의 값은 일정하다.

P^R = a[i+1]이면 dp0[i+1] = dp1[i] / dp1[i+1] = dp0[i]*3 + dp1[i]*2

아니면 dp1[i+1]=dp1[i]

예제에서 틀려서 디버깅을 하다가 관찰 1이 잘못되었음을 알아냈다.

3

1 1 2

가 주어진 경우 PPR / PQR 순서로 시행을 하면 두 경우 모두 P = Q이지만, 전자에서 P = 0, 후자에서 P = 1이다.

위 예제를 어떻게 처리할지 생각하다가 다음 관찰을 했다.

관찰 2

* i번 시행까지 했을 때 P^Q^R의 값은 일정하다.

* 즉 P = Q이면, R의 값은 일정하다.

* P = Q일 때, P ^ a[i+1] = R이면 "같은 두 수의 값"이 달라질 수 있다. (P => P ^ a[i+1] or P로 분기점이 된다.)

* 위 식을 만족하는 P는 유일하므로 "같은 두 수의 값"은 최대 n가지 존재한다. 그리고 "같은 두 수의 값"을 인덱스로 하는 dp 배열을 만들면 한 번의 시행마다 O(1)개의 원소를 조작한다.

풀이 2

dp[i]: "같은 두 수의 값"이 i인 경우의 수

b[i]: i번 시행까지 했을 때 세 수의 값이 같은 경우의 수

a[i]들의 누적 xor을 x라는 변수에 저장하자.

i번째 연산을 할 때, x = a[1] ^ ... ^ a[i]이다.

b[i] = dp[x], dp[x^a[i]] = b[i-1] * 3 + dp[x]  * 2, dp[x] = 0을 i = 1~n까지 한다.

b[n]과 모든 dp값들을 합친 것이 답이다.

같은 두 수의 값이 2^30-1까지 갈 수 있는데, map을 사용해서 해결했다.

C번에서 처음에 풀이를 잘못 냈고 수정하는데 시간이 걸려서 1:19에 AC를 받았다.

1:19

D1번을 잡았다.

10분정도 생각하고 다음 관찰을 했다.

관찰

* c개의 비행기를 n층에서 던져야 한다.

* 0~c개의 비행기를 n-1층에서 던지는데, n층에서 던진 것들과 합쳤을 때 c번째 이후로는 n-1층에서 던질 수 없다.

* 0~c개의 비행기를 n-2층에서 던지는데, 위에 층들과 합쳤을 때 c번째 이후로는 n-2층에서 던질 수 없다.

...

풀이

dp[i][j]를 n층부터 시작해서 j층까지 비행기를 던졌을 때, 총 i개의 비행기를 던진 경우의 수라고 하자.

초깃값: dp[c][n]=1

점화식: dp[i][j] = dp[i-c][j+1] * cCc + dp[i-(c-1)][j+1] * cC(c-1) + ... + dp[i-0][j+1] * cC0

구하고자 하는 값: dp[m][1]

c <= 100이므로 nCr 값들은 전처리하면 되고, O(nmc)에 도니까 시간 내에 해결할 수 있다.

한 번에 맞는 관찰을 해서 그런가 C번보다 훨씬 쉬웠다.

1:39

D2를 잡으려고 시도했다.

D1에서 내가 발상한 풀이가 아예 통하지 않다고 생각해서 새로운 풀이를 발상해야 했는데, 20분 내에 발상 -> 구현까지 도저히 할 수 없을 것 같아 GG쳤다. (나중에 들어보니까 D1 풀이를 조금만 변형하면 된다고 하는데 잘 이해하진 못했다.)

2:00 (끝)

사람들 의견이랑 걸린 시간을 보니 A~D1까지 난이도는 모두 골상위~플하위 정도로 비슷했던 것 같다. 결국 A~D1을 빨리 쓱싹하면 점수가 오르는 라운드였다. 나는 C에서 조금 말리긴 했는데 ABD1을 모두 0틀 20분컷해서 퍼포먼스 2600플마단에 합류했다. 라운드 구조가 웬만한 플레하위까지 스피드포스가 되는 나한테 유리해서 퍼포가 잘 나온 것 같다.

방학 시작할 때 개강 전까지 레드를 찍겠다고 다짐했었다. 일주일에 세번씩 팀셋 혼자서 돌기도 하고, 다이아1 찍는다고 하루에 10시간씩 앉아서 PS만 하기도 했었다. 19점 차이로 레드를 찍지는 못했지만 최근 두 번의 라운드에서 레드를 충분히 갈 수 있다는걸 쇼앤프루브 했다. 

앞으로 목표는

* 다음 코포에서 레드 가기

* 플레 중상위를 코포에서 꾸준히 풀어내기

* 5시간 셋이면 플레를 혼자서 다 밀수 있게 하기

정도이다.