대회후기: Codeforces Round #704 (Div. 2)

저녁 6시의 대회다.

이른 시간에 대회를 치게 되니 느낌이 색다르다. 정신이 더 맑은 것 같기도?

---

A: Three swimmers

Trivial.

AC: 3분

---

B: Card Deck

어렵지 않게 최대한 큰 lexicographic 값을 만드는 문제임을 알 수 있다. 따라서 간단한 greedy 문제가 된다. 덱에서 제일 큰 숫자 기준으로 옮기기를 반복하면 된다.

AC: 9분

---

C: Maximum width

이런 형식의 문제에 약한 듯 하다. 앞으로 최대한 붙여서 완성할 때 필요한 길이 배열과, 뒤로 최대한 붙여서 완성할 때 필요한 길이 배열을 각각 계산해 둔다면, 각 위치의 간격을 최대화했을 때의 간격을 $O(1)$ 복잡도로 구할 수 있다. 앞으로 붙인 글자 $i$개, 뒤로 붙인 글자 $n - i$개일 때 그 사이의 간격을 바로 구할 수 있기 때문이다.

 

떠올리는 데에 정말 오래 걸렸다. D까지 풀고 왔는데 정말 나 빼고 다 풀어놓았더라...

지난번 Round #696의 D에서도 이런 식으로 앞/뒤부터의 과정을 전처리해두고 중간을 $O(1)$만에 확인하는 문제가 있었는데, 그때도 못풀었었다. 이런 유형을 잘 숙지해 두어야겠다... (사실 그냥 웰노운 문제들을 너무 안풀어봤다.)

AC: 1시간 48분

---

D: Genius's Gambit

Constructive algorithm이다. 두 숫자에서 $1$의 개수가 일치하기 때문에, 남아돌아 필요 없는 $1$들은 같은 위치에 두어 뺄셈에서 서로 상쇄되도록 놓을 수 있다. 이제 $1$의 개수가 2 이상이고 $0$의 개수가 1 이상이라면, $110000$과 $100001$처럼 positioning하는 것이 뺄셈 후 $1$의 개수를 최대화하는 방법이다. 즉, 자릿수보다 두개 적게까지 가능하다. 이보다 크다면 불가능 판정을 주면 된다. 만약 $1$이 남아돈다면, 이 $1$들을 두 숫자에서 같은 위치에 두기만 하면 결과는 동일하다.

 

필요로 하는 $1$의 개수가 (자릿수 - 2)보다 같거나 작다면, 무조건 가능하다. $1$의 개수를 줄이는 방법은 두 가지가 있다. 우선, $1$이 남아도는 상황이라면 그 남아도는 $1$들을 두 숫자에서 함께 왼쪽으로 이동시켜 자릿수를 감소시키는 효과를 볼 수 있다. 이렇게 이동시킴으로서 $1$의 개수를 충분히 줄이지 못했다면, 윗 숫자의 마지막 $1$ 위치를 오른쪽으로 이동시키면 된다. (e.g. $110000$과 $100001$에서 $100100$과 $100001$로)

 

$1$의 개수가 1개이거나, $0$의 개수가 0이거나, 필요로 하는 $1$의 개수가 0인 경우 등의 코너케이스는 예외처리를 해줘야 한다.

AC: 1시간 8분

---

E: Almost Fault-Tolerant Database

D를 해결한 직후, C에 다시 도전하기 전에 E에 먼저 왔었다.

 

처음 보고서는 백트래킹인가..? 하다가, '복잡도가 설마 되겠어' 하는 생각에 그래프 문제라고 생각하고 포기했었다.

 

하지만 정말 백트래킹이었다 엌 ㅋㅋ

---

총평

레이팅이 떨어지는 줄 알았지만, 의외로 많은 사람들이 A와 D에서 해킹되는 덕분에 소폭 상승할 수 있었다.

군대 가기 전에 오렌지를 찍고 싶었는데, 퍼플도 간당간당한 상황이 슬프다 ㅠㅠ

 

레이팅 변화: 1879 + 17 = 1896

My Performance: ★★★☆☆

---

연습지