Codeforces Round 849 (Div. 4)

Dashboard - Codeforces Round 849 (Div. 4) - Codeforces

 

D

배열 a[0...N-1] 을 왼쪽과 오른쪽 두 개의 subsequence로 나누었을 때, 나눌 수 있는 모든 경우에 대해, 왼쪽/오른쪽 subsequence에 포함된 알파벳의 개수를 세는 방법은 다음과 같다.

배열 a[0...N-1]에 포함된 알파벳의 개수를 모두 센다. -> 오른쪽 subsequence에 포함된 알파벳.
이제 왼쪽 subsequence의 영역을 하나씩 넓혀간다.

 

E

편의상 0을 positive integer, -0을 negative integer 이라고 하자. 그러면, 모든 정수(0, -0 포함) negative 이거나 positive 이다. 이때 임의의 두 원소의 부호를 바꾸어도 (negative interger 개수)의 parity는 변하지 않는다.

한편 greedy 방식으로, 왼쪽 원소부터 차례로 보면서 음의 부호를 가지면 부호를 바꿔주는 방식으로 가장 오른쪽 원소를 제외한 모든 원소를 positive로 바꿀 수 있다.

parity가 유지되는 성질에 의해, 준 배열의 negetive 원소의 개수가 짝수였으면 모든 원소를 양수로 바꿀 수 있다. 홀수였으면 절대값이 가장 작은 원소만이 negative integer이 되게 바꿀 수 있다.

 

F

함수 f := (입력으로 x가 주어지면, x를 구성하는 digit 의 합을 돌려주는 함수)
ex) f(101) = 2

이때 배열의 임의의 원소는 f에 의해 많아야 3번 변화가 일어난다.(editorial 참고)

변화가 일어날 수 있는 원소(자리수가 두자리 수 이상인 원소)들의 index를 set 으로 관리하자.

 

 

G2

처음 사용하는 teleport를 제외하면 두 번째 이후의 teleport는 (point 0이나 n+1 중) 유리한 위치에서 출발하여 탈 수 있다. 따라서 두번째 teleport부터는 코인이 적게드는 방식으로 그리디 하게 teleport를 이용하면 된다.

한편, 첫 번째 teleport를 어떤 것을 이용해야 하는지는 모른다. 따라서 임의의 teleport 를 처음 이용하는 경우에 대해 최대로 이용할 수 있는 teleport 의 수를 모두 구해봐야 한다.

어떤 teleport i 를 가장 먼저 이용했다고 할 때, 최대로 이용할 수 있는 telport 의 수는 누적합과 파라메트릭 서치를 이용하여 구할 수 있다.