Codeforces Round 896

Dashboard - Codeforces Round 896 (Div. 1) - Codeforces

A - Fill in the Matrix

우선 M이 1이면 답은 0이다.

예제로 주어지지 않았다면 반례 찾는데 한참 걸렸을 것 같다.

 

M이 1이 아니라면 답은 min(N + 1, M)이다.

먼저 최대 (M - 1)개의 행을 다음과 같이 채우자.

0 1 2 ... (M - 2) (M - 1)

1 2 3 ... (M - 1) 0

...

(M - 2) (M - 1) 0 ...

 

여기까지 하면 답은 min(N + 1, M)이 된다.

나머지 행도 적절히 채워야 하는데 그 다음 행을 동일한 규칙으로 채우는 순간 답은 0이 되어버린다.

간단한 방법으로 이를 방지할 수 있다.

나머지 모든 행을 첫 번째 행과 동일하게 채우면 된다.

00:11 AC

 

B1 - Candy Party (Easy Version)

sum(A)가 N의 배수가 아니라면 return No

다음과 같은 배열 B를 정의하자.

B[i] = A[i] - avg;

(2^x - 2^y) 꼴로 표현할 수 없는 B[i]가 존재한다면 return No

배열 C를 만들고 모든 B[i]에 대하여 ++C[x], --C[y]를 수행하자.

배열 C에 0이 아닌 원소가 존재한다면 return No

return Yes

00:24 AC

 

B2 - Candy Party (Hard Version) (not solved)

Easy 버전과 풀이가 매우 유사하다.

우선 기존 방식대로 동일하게 풀이한다.

배열 C에 0이 아닌 원소가 존재한다면 return No

2^k or -2^k 꼴인 B[i]에 대하여 기존의 (2^x - 2^y)를 2^y 또는 -2^x로 대체할 수 있는지 확인한다.

이는 msb부터 시작해서 그리디하게 확인할 수 있다.

그런데 틀렸다.

00:33 WA

00:36 WA

00:44 WA

01:25 WA

 

가끔 문제를 풀다보면 아무리 눈 씻고 찾아봐도 오류를 찾을 수 없는 순간이 있다.

이 문제가 바로 그런 경우였고 결국에는 데이터를 까서 반례를 찾았다.

원인은 구현 실수였는데 사소한 실수가 아니어서 대가리를 후두려 맞은 느낌이었다.

 

기존 구현에서는 배열 D를 만들었는데 의미는 다음과 같다.

D[i] > 0인 경우에는 C[i]를 1만큼 감소시키고 C[i - 1]를 2만큼 증가시키는 연산을 D[i]번 수행할 수 있다는 의미이다.

D[i] < 0인 경우에는 C[i]를 1만큼 증가시키고 C[i - 1]를 2만큼 감소시키는 연산을 -D[i]번 수행할 수 있다는 의미이다.

 

잘 구현한 것 같은데 문제가 발생한다.

다음과 같은 입력을 고려해보자.

1

6

2 4 7 9 11 15

평균 = 8을 빼고 다시 적으면 다음과 같다.

-6 -4 -1 1 3 7

 

답은 Yes이며 각 원소를 8로 만드는 방법은 다음과 같다.

-6: 2 - 8

-4: -4

-1: 1 - 2

1: 1

3: 4 - 1

7: 8 - 1

 

기존 구현에서의 동작을 살펴보자.

-1은 (2^0 - 2^1)이며 -2^0으로 대체할 수 있으므로 --D[1]을 수행한다.

1은 (2^1 - 2^0)이며 2^0으로 대체할 수 있으므로 ++D[1]을 수행한다.

결과를 보면 --D[1]과 ++D[1]이 상쇄되어 D[1]이 0이 되어버렸다.

의도와 다르게 위에서 언급한 배열 D에 대한 연산을 수행할 수 없게 된다.

 

이를 방지하려면 기존의 --D[i] 연산을 새로운 배열 E에서 ++E[i] 연산으로 수행하면 된다.

이 부분만 수정하니 바로 AC를 받았다.

 

C - Travel Plan (not solved)

Pass

 

D - Flower-like Pseudotree (not solved)

Pass

 

E - Min-Sum-Max (not solved)

Pass

 

F - LIS? (not solved)

Pass

 

끝

B2 풀이를 금방 찾았는데 구현에서 꼬인 부분이 조금 아쉽기도 하다.

하지만 그게 내 실력이고 다음 라운드에서 더 잘 하면 된다.

지난 두 라운드에서 레이팅이 100점이나 떨어졌는데 기분이 별로 나쁘지가 않다.

오히려 다음 라운드에서 레이팅 폭등 기회가 생겼으니 이득이다.

또 떨어진다면 레오님처럼 퍼플 -> 찐렌지 폭등 기회가 생기니 이득이다.

결과가 어떻든 대회를 치는 것이 이득이라는 결론에 도달하였다.

 

이틀 후에 SCPC인데 지금 더 공부한다고 의미가 있을지 모르겠다.

내일은 브실컵 26 문제 랭작이나 하다가 쉬려고 한다.

끝