Codeforces Round #703 Div.2

codeforces.com/contest/1486
총평: 전체적으로 문제 셋이 재밌었고 선방했다.

정확히 1달만에 즉흥적으로 친 코포라 걱정 반 설렘 반이였는데 오히려 더 나은 결과를 얻었다

A -> B -> C1 -> C2 -> E 순으로 풀었다.

A는 직관적으로 생각하면 쉬울 것을 너무 성급하게 찍어버렸다.
i -> i+1 단방향만 가능하므로 i=0->n-1까지 따라가면서 가능한지 검사하는게 중요 포인트

B는 수학. 무난히 빨리 풀었다.

C1, C2는 재미있는 인터랙티브 문제이니 꼭 풀어보는 것을 추천한다.
로그를 붙이는 다양한 알고리즘에 관하여 숙고한 경험이었다.
C1 구현에 오래 걸리고, C2는 자칫 못 풀 뻔 했지만 
관점을 완전히 바꾸니 시간 투자 후 해결할 수 있었다.

E는 다익스트라 문제인데, 내가 푼 방법이 intended보다 더 빠르고 범용적이다. 

a,b 타입 정점 모두 1번 정점에서부터의 거리로 pq에 집어넣는다. b타입의 정점의 경우 직전 간선의 가중치도 같이 저장해야 한다.
이때 a 타입 정점을 갱신할 조건은 거리, b 타입 정점을 갱신할 조건은 직전 간선의 가중치다.

이 다익스트라가 성립하는 이유는
b타입 정점을 살펴볼 때 항상 
거리가 짧은 경우부터 보기 때문에
나중에 들어온 정점은 거리가 항상 더 크거나 같다. 
이때 직전 간선의 가중치가 기존보다 크다면 이 정점은 더 이상 볼 필요가 없다.
w1<=w2,    a<=b 일 때 w1 + (a+w)^2  <= w2 + (b+w)^2
따라서 w가 더 작을 경우에만 갱신되기 때문에 이 다익스트라가 성립한다.

w가 클 경우에도 될 줄 알았는데 지금 보니 w <= 50 이여서 O(M log 50N)에 돌아가는 거였다.