Codeforces Round #742 (Div. 2)

Dashboard - Codeforces Round #742 (Div. 2) - Codeforces

 

 

점수가 오르기는 했지만 여러모로 아쉬운 라운드였다.

 

Prob. A

'U', 'D' 만 서로 바꿔준다.

 

Prob. B

$0$ ~ $a-1$ 을 모두 사용하면 최대 두 개를 더 사용해서 $b$ 를 만들 수 있다. 이제 적당히 case-work 해주면 되지만 xor을 naive하게 계산하면 TLE를 받는다. 아마 누적 xor을 전처리하는 것이 정해인 것 같고, 나는 그걸 생각 못해서 $n=4k+3$ 꼴마다 누적 xor이 0이 된다는 이상한 성질을 관찰하여 해결했다. 이때 시간이 꽤 지나서 2700등 정도까지 떨어졌었다.

 

Prob. C

인접한 자리끼리는 영향을 주지 못하므로 홀수 자리만 모은 수와 짝수 자리만 모은 수 각각에 대하여 경우의 수를 구하면 된다. 그런데 $n$ 을 만드는 경우의 수는 $n+1$ 로 쉽게 구해지고, 따라서 답은 $(n1+1)*(n2+1)-2$ 이다.

굉장히 좋은 문제라고 생각한다. 하지만 이 정도 관찰이 한 시간이나 걸리면 안 된다.

 

Prob. D

큰 자릿수부터 빼주는 그리디가 성립한다. C보다 쉬웠음. 백준에서 비슷한 문제를 본 기억이 있는데 못 찾겠다.

 

Prob. E

아이디어성 쿼리 문제라 생각하고 시간 없어서 버렸는데, 알고 보니 그냥 금광 세그였다. 진짜 거의 복붙하듯이 가져오면 맞는다. 대회 중 금광 세그로 풀릴 것 같다는 생각을 하긴 했지만 이걸 시도도 안 해본 것이 너무 후회된다. 웰논 자료구조는 정말 노오력만 하면 거의 맞아오는데 이런 문제를 놓치면 정말 힘 빠진다...