Codeforces Round #847 (Div. 3)

Dashboard - Codeforces Round #847 (Div. 3) - Codeforces

 

ㅋㅋㅋ 꺼억

 

Prob. A

예제에서 30자리를 주고 있다는 것을 빠르게 관찰하는 것이 핵심이다.

 

Prob. B

그리디하게 큰 거 꽉꽉 채우고 작은 거 넣어주면 된다. div3 B 치고는 어려웠다.

 

Prob. C

가장 앞 원소 중 뭐가 가장 많은지 확인하고, 앞에서 제거한다.

 

Prob. D

[BOJ 23845] 마트료시카 에서 범위가 커졌다. 같은 로직을 map을 섞어서 구현해주면 된다.

 

Prob. E

[BOJ 25367] 너무 시시했다 에 한 줄을 추가하면 실례를 찾을 수 있다.

 

Prob. F

[BOJ 13514] 트리와 쿼리 5 를 복붙하면 된다.

 

Prob. G

일단 토큰이 1번 노드에 있거나 그와 인접한 노드에 있으면 항상 가능하다. 그 이후엔 여러 관찰이 필요한데, 우선 보너스들과 1번 노드를 유파로 합쳐주자. 먼저, 한 번 이동했을 때 1번 노드와 같은 그룹에 도달할 수 있는 토큰만 1번 노드에 도달할 가능성이 존재한다. 그런 토큰 중에서 1번 노드와 거리가 가장 가까운 노드를 1번 노드에 보내려고 시도하는 것이 최적이다. 다른 토큰 중에서 한 번 이동했을 때 크기가 2 이상인 그룹에 들어갈 수 있는 토큰이 존재한다면 앞에서 정한 토큰을 1에 보내는 것이 항상 가능하다. 그렇지 않으면, 한 번 이동했을 때 크기가 1인 그룹에 들어갈 수 있는 토큰의 개수가 앞에서 정한 토큰이 한 번 이동했을 때 1번 노드와의 거리보다 크거나 같을 때만 가능하다.

초기화를 안해서 1틀했다... 대체 예제는 왜 통과하지.. 0틀 놓친 거 너무 아쉽다