Codeforces Round 917 (Div. 2)

이번 라운드가 역대 최저점 퍼포먼스를 찍은 라운드였다...

A번을 풀고 B를 보는데 풀이가 바로 생각나는 게 없어서 나머지 문제들을 둘러봤다.

E를 풀 수 있을 것 같아서 여기에 시간을 다 쏟아부었는데, 왜 틀리지 하다가 반례가 생각났고 고칠 수 없어서 그냥 포기해버렸다.

 

---

A - Least Product   (00:04)

배열에 $0$이 있거나 음의 원소 개수가 홀수이면, 아무런 작업을 하지 않았을 때 전체 곱이 최소가 된다.

그렇지 않으면, $0$이 아닌 원소들 중 아무 원소에 작업을 1회만 하면 전체 곱이 최소가 된다.

 

 

B - Erase First or Second Letter

???

 

C - Watering an Array

???

 

D - Yet Another Inversions Problem

???

 

E - Construct Matrix

처음에는, $k$가 $4$의 배수 꼴이 아니면 불가능하다고 생각했다.

$k$가 $4$의 배수일 때와, 그렇지 않으면서 $2$의 배수일 때로 케이스를 나누어 규칙성을 찾고 출력해주었는데 틀렸다고 떴다.

$4$의 배수일 때는 확실히 가능했는데, 그렇지 않은 경우에서 내 단순 constructive 풀이에 대한 반례를 찾아버렸다.

 

내 풀이는 대략적으로, 전체 정사각형을 두 개의 부분 직사각형으로 나누어 각각에 대해 $1$을 적절히 할당해주는 것이었는데, 두 개 이상의 사각형으로 나뉠 수 있는 모든 경우가 반례에 해당됐다.

당연히 두 개 이하로 나뉠 거라 생각하고 풀었던 내 불찰이었다.

 

F - Construct Tree

???

 

---

Rating

-134

1691 $\rightarrow$ 1557

 

집중해서 3솔이라도 했어야 했는데, 한 문제에 너무 오래 묶여있었던 게 하락의 원인이었던 것 같다.