Codeforces Round #849 (Div. 4)

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

 

div. 4에서 되게 오래 걸린 것 치고 순위가 나쁘지 않다. 고수들이 별로 참여 안 해서 그런가

 

Prob. A

string의 find와 npos를 쓰면 편하다. 물론 난 몰라서 못 썼다.

 

Prob. B

해보면 된다.

 

Prob. C

양쪽에서 될 때까지 빼면 된다.

 

Prob. D

살짝 까다로운데, 2번 이상 등장하는 문자 중 양쪽에 모두 위치한 개수를 관리하면서 스위핑하면 된다. 더 쉬운 풀이가 있을 수도

 

Prob. E

음수가 짝수 개면 모두 양수로, 홀수 개면 하나 뺴고 모두 양수로 만들 수 있다. 끝에서부터 밀어주면 잘 된다.

따라서 짝수 개면 절댓값의 합, 홀수 개면 절댓값의 합 - 가장 작은 절댓값 * 2 를 계산하면 된다.

 

Prob. F

한 자리 수가 되면 더이상 변하지 않기 때문에, 실제로 갱신이 일어나는 횟수는 매우 적다고 추측할 수 있다. 두 자리 수 이상인 수의 인덱스를 관리하는 set을 이용해서 각 쿼리를 naive하게 처리할 수 있다.

또는 세그 트리 비츠를 쓰면 된다.

 

Prob. G1

$i + a_i$를 정렬하고 그리디하게 먹어준다.

 

Prob. G2

하나를 시작점으로 고정하고 나머지는 G1처럼 그리디하게 먹어주면 된다. 나는 업데이트와 이분탐색이 필요하다고 판단해서 kth 펜윅과 카운팅을 위한 세그를 사용했는데, 그냥 누적합과 이분탐색으로 할 수 있더라.