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

맞웨틀(맞앗는대 웨 틀렷지?)

---

A: Display The Number

LCD 패널에서 흔히 볼 수 있는 7 segment display가 있다. $n$개의 segment만 활성화 시킬 수 있을 때, display 가능한 최대의 수를 출력해야 한다.

생각과정: 가성비가 최고로 좋은 9를 최대한 많이 출력해야겠다 -> 한 숫자의 가성비가 중요한 것이 아니라 자릿수가 최대한 많아야겠군 -> 1만 잔뜩 출력하다가 segment 개수가 남으면 첫 자리수를 키우자!

1 WA 후 11분에 AC

A 치고는 쉽지 않은 편이었으나 11분이나 걸린 것은 unacceptable이다.

---

B: Infinite Prefixes

주어진 이진문자열 $s$가 무한히 반복되는 문자열 $S=sssss...$와 주어진 정수 $x$가 있다. 임의의 문자열에 대해 $D=(0의 개수) - (1의 개수)$로 정의할 때, $S$의 prefix 중 $D=x$가 되는 prefix는 몇개인가?

문자열은 주기를 갖고 반복되므로 한 주기마다 $D$값이 얼마나 shifting하는지 살펴보아야한다. Prefix의 길이 $l$에 대한 $D$의 그래프를 그려놓고 이 shift 값을 어떻게 활용할 지 생각해보니, 한 주기의 그래프만 그려놓고 $x$값을 shift만큼 움직여가며 교점의 수를 확인하면 되는 것이었다(고등학교 수학에서 함수를 이동시켜 상수함수와의 교점을 구할 때, 함수를 이동시킬 수도 있지만 상수함수를 반대방향으로 이동시킬 수 있다는 사실은 자주 쓰인다). 시작하는 $x$값에서 shift값을 유한번 더한 값들을 훑으면서 첫번째 주기에서 그 $D$값이 나오는 횟수를 더해주면 된다.

어렵지 않은 문제였다.

하지만 결과는

10 WA

Array index를 잘못 access해서 무한 맞웨틀에 빠졌다. 하지만 풀이를 다 떠올리고도 AC를 못 받는다는 빡침에 한시간 반을 붙잡고 있었다. 버그를 발견하고 통과시킨것은 대회 종료 이후이다.

---

C: Obtain The String

Target 문자열과 source 문자열이 있다. 편의를 위해 각각 $t$와 $s$로 부르겠다. 빈 문자열 $z$에 $s$의 subsequence를 여러번 append해 $t$를 만들고자 한다. 이러한 작업의 최소 횟수는 무엇인가? (1 append = 1 move)

 

$z$를 만들어 가면서 $s$가 소진되었을 시 작업 횟수를 하나 늘리고 새로운 $s$를 가져오는 느낌으로 풀면 된다. 다만 처음 구현체에서는 subsequence를 만들 때 character의 order가 보존되어야 한다는 점을 생각치 못해 단순히 필요한 알파벳의 개수가 남아있는지만을 확인하는 코드를 짰다.

정신을 차리고 나서는 각 알파벳별로 $s$ 내부의 index를 저장해두고 이진 탐색을 이용해 필요한 알파벳을 하나씩 가져오는 알고리즘을 짰다. 필요한 알파벳이 소진되었을 시, 작업 횟수를 하나 늘리고 $s$의 가장 앞부터 다시 시작한다.

1 WA 후 1시간 41분에 AC

---

총평

Trivial한 버그도 오랫동안 찾지 못할 수 있음을 다시 한번 느꼈다.

코드를 짤 때에는 신.중.하.고. 정.확.하.게. 짜는것이 더 빠른 AC를 위한 길이다.

 

레이팅 변화 1920 - 97 = 1823

My Performance: ★☆☆☆☆

 

연습지