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

몰아쓰는 후기 #3

이번 주는 대회가 많다.

---

A: Three Strings

빨리 Div. 1에 안착해서 이런 문제 후기들 생략하고 앉아있지 않아도 되면 좋겠다.

3분에 AC

---

B: Motarack's Birthday

몇몇 칸이 비어있는 정수 배열이 입력으로 들어온다. 그 비어있는 칸들은 일관되게 $k$로 채울 것이다. 인접한 값들 사이의 차의 최댓값을 $m$이라고 할 때, $m$을 최소화하는 $k$값을 구해 $m$과 $k$ 모두 출력해야 한다.

다들 이진탐색으로 많이 푼 것 같고 problem tag에도 binary search가 있지만 나는 이 문제를 왜 그렇게 푸는지도 모르겠고 어떻게 그렇게 푸는지도 모르겠다.

그냥 빈 칸과 인접한 수들 중 제일 큰 값과 제일 작은 값 중간의 값을 $k$로 택하면 된다.

$k$를 채워넣고 $m$만 판별해주면 끝.

12분에 AC

---

C: Ayoub's function

경우의 수 문제이다. 0의 개수와 1의 개수가 주어졌을 때, 이들을 일렬로 배열해 만든 이진 문자열의 substring 중 1이 포함되어 있는 substring의 개수를 최대화하고자 한다. 최적의 배열로 문자열을 만들었을 때, 1이 포함된 substring의 개수는?

여집합으로 접근했다.

(전체 substring의 개수)에서 (0으로만 이루어진 substring의 개수)를 빼면 된다. 그런데 저 값을 최대화시켜야 하므로 (0으로만 이루어진 substring의 개수)는 최소화시켜야 한다. Intuition tells me that I want to split the 0s apart as much as possible. 1들을 이용해 0들을 최대한 잘고 균등하게 찢어주고, 경우의 수 계산만 잘 해준다.

21분에 AC

---

D: Time to Run

이게 문제냐.

입력으로 column 수와 row 수, 그리고 $k$가 들어온다. 위의 화살표와 같이 길이 깔린다. 이때 같은 길을 두번 지나지 않으면서 총 길이가 $k$인 경로를 문제에서 요구하는 형식에 맞춰 출력하면 된다.

근데 위 그림을 보고 나니 모든 길을 한번씩 전부 다 통과하는 경로가 그냥 보여버렸다. (아래 연습지 참고)

그래서 구현만 했다.

1 RTE 1 WA 후 56분에 AC

---

총평

문제들이 쉽기도 했고, 풀이들이 바로바로 보이기도 했다. 운이 좋은 날이다. E는 풀 시간이 많이 있었지만 해결하지 못했다. 아직 모르는 알고리즘/자료구조를 사용해야 하는 듯 하다. (아래 연습지 두번째 페이지가 E 내용이다.)

 

레이팅 변화 1795 + 160 = 1955

My Performance: ★★★★☆

 

연습지