Educational Codeforces Round 161 (Rated for Div. 2)

Dashboard - Educational Codeforces Round 161 (Rated for Div. 2) - Codeforces

D, E가 쉽게 나와서 나름 잘 쳤다. F도 접근은 다 했는데 디테일에서 부족한 부분이 있었다.

 

Prob. A

사실 얘는 아직도 지문을 이해하지 못했다. 그냥 예제만 보고 가능한 코드를 다 짜보니 두 번째에서 맞았다.

 

Prob. B

뽑은 세 수 중 가장 큰 것이 다른 두 수보다 strict하게 크면 안 된다. 그래서 세 수가 모두 같거나, 두 수가 같고 남은 수가 그것보다 작은 두 가지 경우만 가능하다. 같은 수를 편하게 처리하기 위해 map을 사용해서 풀었다.

 

Prob. C

$u$에서 $v$로 갈 때 항상 일직선으로 이동하는 것이 최선이다. 그리고 이동 중에 $1$의 비용으로 이동할 수 있는 곳이 나오면 항상 그렇게 이동하는 것이 최적이다. 이는 누적합으로 처리해줄 수 있다.

 

Prob. D

처음에만 다 확인해보고 다음부턴 없어지는 부분 근처만 확인해보면 잘 된다. 그냥 배열로 연결 리스트를 구현했다.

 

Prob. E

길이가 $l$인 증가수열은 $2^l$만큼 기여를 한다. $x$를 이진법으로 나타내고 가장 큰 비트만큼 일단 증가수열을 만든 다음, 나머지 켜진 비트를 거꾸로 붙여주면 된다. 수열의 길이도 $120$이면 충분하고, 수 범위도 $0$~$60$이면 충분한데 제한이 과하게 큰 것 같다.