[2020-09-16] Codeforces Round 625 (Div.1)

ABC는 빠르고 정확하게 풀었는데 D를 90분이나 시간이 있었음에도 못 풀었다. 심지어 풀이는 거의 10분만에 나왔는데.. 이런 류의 문제를 항상 잘 못 푸는 것 같다. 풀이를 좀 더 깔끔하게 생각을 하든, 구현을 좀 더 잘 하든 둘 중에 하나는 해야하는데. 오늘 업솔빙까지 끝내고 싶었지만 너무 피곤해서 D 업솔빙은 내일로 미룬다. AC 받고 나서 풀이 업뎃해야지

이 사이트 퍼포먼스를 좀 짜게 주는 것 같다. 본 대회에서 나랑 비슷한 점수 기록한 사람이 오렌지에서 레드까지 레이팅이 올랐던데? 그러면 이것도 퍼포먼스 수치가 레드 언저리여야하는 것 아닌가... 흠... 일부러 가상 참가는 약간 과소평가하게 만들어놓은건가 싶기도 하고.

 

A. Journey Planning

 가끔 보이는 종류의 문제. 각각을 하나의 일차함수로 보면, 절편을 기준으로 묶어줄 수 있다. 따라서 map 등을 이용해 절편값을 기준으로 각 직선 위에 있는 값들의 합을 계산해서 그 중 최댓값을 취하면 AC를 받을 수 있다.

B. Navigation System

 목적지가 고정인데 여러 시작점에서 최단 거리를 구해야 하니, 모든 간선의 방향을 거꾸로 뒤집어서 각각의 v에 대해 T->v의 최단거리를 구해두자. 이러고 나면, 어떤 정점 x에서 y로 진행하는 path의 한 순간에 대해 다음 케이스들이 생긴다.

1. x -> y 에서 y가 최단거리 경로에 속하지 않는 정점 : rebuild 횟수 최소든 최대든 무조건 rebuild가 필요하다. 

2. x -> y 에서 y가 최단거리 경로에 속하는 정점 : x에서 진행할 수 있는 최단경로에 속하는 정점이 둘 이상인 경우와 그렇지 않은 경우로 나뉜다. 둘 이상인 경우, rebuild를 할 수도 / 하지 않을 수도 있다. 따라서 max case에는 +1, min case는 유지. 하나밖에 없는 경우, 둘 다 rebuild를 하지 않는다. 값 변화 없이 진행.

 

 따라서 모든 path[i], path[i+1]에 대해 위 케이스 분류를 이용해 rebuild 횟수 최소, 최대치를 계산해주면 된다.

C. World of Darkraft: Battle for Azathoth

먼저 공격력을 기준으로 모든 몬스터를 정렬해보자. 무기도 정렬하고 나면, 무기를 한단계 업그레이드할 때마다 잡을 수 있는 몬스터의 set은 점점 더 커진다(i+1번째로 강한 무기를 써서 잡을 수 있는 몬스터 집합은 i번째로 강한 무기를 써서 잡을 수 있는 몬스터 집합을 항상 포함한다). 따라서, 투 포인터 같은 방식으로 무기를 바꿀 때마다 잡을 수 있는 몬스터 셋을 추가할 수 있다. 이렇게 몬스터를 추가할 때, 방어도를 기준으로 하는 세그트리에 구간 업데이트를 해준다. 즉, value[i] = 방어도를 i이상으로 맞출 때 얻을 수 있는 최대 이득 이라고 정의하면, 몬스터의 방어도가 w일 경우 value[w+1] ~ value[10^6] 까지는 전부 그 몬스터의 이득만큼 추가가 되는 것이다. 맨 처음에 세그트리를 초기화할 때 방어도 k를 맞추기 위해 필요한 비용(방어구 값)을 이용해서 배열을 초기화해놓고 시작하면 된다.

 

무기 수준을 높일 때마다 이렇게 세그트리를 갱신해주면 답을 O(Nlog(100만)) 정도에 구할 수 있다.