Educational Codeforces Round 87 (Rated for Div. 2)

a

A. Alarm Clock (00:07, +)

문제를 이해하기 힘들어 예제를 보고 문제를 예측했다. 문제 자체는 간단한 if문을 사용하면 풀린다.

 

B. Ternary String (00:10, +)

각 문자별로 마지막에 나온 위치를 저장하며 가면 \( O(N) \)에 해결할 수 있다.

 

C. (Not So) Simple Polygon Embedding (00:41, +)

공책에서 풀고 \(O(1)\) 로 출력하는 기하 문제이다. 이외에도 이진탐색을 이용해 해결하는 방법이 있다고 한다.

 

D. Multiset (01:00, +2)

Multiset을 구현하는 문제인데, 메모리 제한이 \(O(N)\)이라 Heap 자료구조를 사용하기 힘들다.

이는 펜윅 트리를 사용하면 해결된다. 주어지는 값이 최대 \(10^6\) 이기 때문에 그만큼의 배열을 잡아줄 수 있고, 각 index에 해당 숫자가 등장한 횟수를 저장하며 이진탐색을 이용해 누적합이 \(k\)이상인 인덱스의 값을 하나씩 줄여주는 것으로 해결할 수 있다.