ARC 193 - Div 1

 

https://atcoder.jp/contests/arc193

 

 

 

Performance Rating : 1400

 

A

A와 B 모두 처음에 풀이가 떠오르지 않았는데 A 솔브수가 올라가는 속도를 보고 A를 먼저 풀었다. 이 문제는 $[L_i,R_i]$에서 겹치지 않는 구간을 활용하여 $[L_j,R_j]$에 도달하는 문제인데, 도달하는 과정에서 최소한의 $w$를 사용해야 한다. $L_i\leq L_j$라고 하자.  $[L_i,R_i]$와 $[L_j,R_j]$가 겹치지 않으면 바로 이동하는 것이 최선이고 중간에 3개 이상의 구간을 거치는 경우 하나를 제외시키고도 충분히 도달 가능하다는 것을 깨달았다. $R_p<L_i$이거나 $L_p>\mathrm{max}(R_i,R_j)$인 경우 $p$번 노드 하나만 거치고도 도달할 수 있고 $R_i<R_j$인 경우에 한해서 $R_p<L_j$, $L_q>R_i$인 $p$, $q$번 노드 2개를 거쳐서 도달 가능하다. 이를 계산하는 것은 $L$기준 정렬을 한 뒤 $w$의 suffix min, $R$기준 정렬을 한 뒤 $w$의 prefix min을 구해놓는다. 그 후 이분탐색으로 $R_p<L_i$인 $x$의 최댓값, $L_y>\mathrm{max}(R_i,R_j)$인 $y$의 최댓값을 구하고 $R_i<R_j$인 경우에 한해서 $R_r<L_j$, $L_s>R_i$인 $r$, $s$의 최댓값과 최솟값을 구해놓고 앞서 계산해 두었던 prefix min과 suffix min을 사용하면 답을 구할 수 있다. 두 노드를 사용할 수 있는 것은 $R_i<R_j$인 경우 뿐인데 이를 고려하지 않았다가 50분을 날렸다.

 

B

DP로 풀릴 것 같다는 생각은 들었지만 구체적인 식을 세우지 못하였다.