Codeforces Round 479 (Div. 3)

Dashboard - Codeforces Round 479 (Div. 3) - Codeforces

 

B

방법 1 - 메모리 절약

 

방법 2 - 메모리 좀 씀

 

 

C

방법 1 - binary serarch O(lg max(ai) x lg(N) )

 

방법 2 - index의 의미 이용 O(n lg N)

0-based index에서 index i의 앞에는 i개의 수가 있다.

 

 

D

방법 1 - 위상정렬 O(N² + V + E) 이때 |V| ≤ N, |E| ≤ N²

원소간에 선후관계 파악

위상정렬

 

방법 2 - 소인수의 개수 관찰 O(N lg max(ai) + N lg N)

올바른 순서의 순열은 각 원소의 (소인수 3의 개수)는 줄어들고 (소인수 2의 개수)는 늘어난다

 

 

F

방법 1 - binary serarch

배열 v의 작은 원소부터 큰 원소까지 차례로 살펴본다. 현재 보고 있는 수를 i라고 하자.

i로 시작하는 가장 긴 부분 순열을 생각하자.
i의 가장 빠른(작은) index a.
a보다는 뒤에 있으면서 (i+1)의 가장 빠른(작은) index b
b보다는 뒤에 있으면서 (i+1)의 가장 빠른(작은) index c
...

이때 각 index는 binary search를 활용하여 찾아준다.

추가로 한번 사용한 index는 방문 체크를 하여 중복하여 사용하지 않도록 한다.
다음과 같은 경우 N²번 index를 사용하는 것을 방지하기 위함.
v = 1 2 3 4 5 6 ... N

각 원소의 index를 저장하는 mp

 

방법 2 - dp O(n lg N)