대회후기: Educational Codeforces Round 82 (Rated for Div. 2)

몰아쓰는 후기 #2

---

A: Erasing Zeroes

이진 문자열. 1 사이에 낀 0들의 개수를 출력하면 된다.

2분에 AC

---

B: National Project

$n$칸짜리 highway 수리를 해야 하는데, 하루에  $1$칸 이하만 수리할 수 있다. 수리를 시작하는 날부터 좋은 날 $g$일과 나쁜 날 $b$일의 주기가 반복된다. 좋은 날에 수리한 highway의 비율이 절반 이상이기 위해서 필요한 최소 날의 수는?

그냥 대놓고 이진탐색이다.

1 WA 후 15분에 AC

이진탐색의 범위를 잘못 잡아서 WA를 한번 띄웠다.

---

C: Perfect Keyboard

26개 알파벳을 일렬로 배열해 키보드를 만들어야 하는데, 입력으로 들어오는 문자열에서 인접한 알파벳은 키보드에서도 인접해야 한다.

일렬로 배열할 경우 한 알파벳이 인접할 수 있는 다른 알파벳의 수는 최대 2개 이므로, 알파벳들끼리의 인접 관계를 나타낸 그래프에서 모든 node의 degree는 2 이하이어야 한다. 또한, 그래프에 cycle이 있어서는 안된다.

이러한 성립 조건들을 판별한 이후, 그래프로부터 키보드 배열을 뽑아내는 일은 구현만 해주면 된다.

 

근데 그 구현에서 좀 많이 넘어졌다.

4 WA 1 RTE 이후 1시간 7분에 AC

---

D: Fill The Bag

목표 integer $n$이 있다. 재료가 되는 integer들은 문제의 입력으로 주어지며 2의 거듭제곱들이다. 목표 integer를 몇몇 재료 integer들의 합으로 표현하고 싶은데, 주어진 integer들로 $n$을 만드는 것이 불가능하다면 주어진 integer들을 크기가 같은 둘로 쪼갤 수 있다. 이러한 operation의 최소 횟수를 출력하는 문제이다.

 

뭔가를 해봤지만 못풀었다 ㅠ ==> editorial을 보니 내 풀이가 거의 맞은 듯 하다. 단지 동작 순서가 조금 달랐다. 결국 틀린것은 틀린것.

2 WA

---

총평

C 때문에 기분이 나쁜 대회이다. 디버깅에 시간을 허비하지 않았다면 D는 풀어내지 않았을까.

 

레이팅 변화 1835 - 40 = 1795

My Performance: ★★☆☆☆

 

연습지