ABC 395

https://atcoder.jp/contests/abc395

 

 

Performance Rating : 1960

 

A

단조증가수열인지 판단하는 단순한 문제였다.

 

B

바깥에서부터 '#', '.'을 번갈아가면서 찍어주면 되는데 구현 과정에서 시간이 꽤 걸렸다.

 

C

$10^6+1$크기의 배열에 각 숫자가 나온 최근 인덱스를 저장해 두면 되는데, 답을 출력하는 것에 삼항 연산자를 잘못 사용했다가 디버깅하느라 시간이 조금 소요됐다.

 

D

배열 3개를 활용해서 풀면 되겠다는 생각을 했다. 둥지의 새들을 서로 바꿀 때 새들의 둥지 번호를 직접 바꾸면 시간 초가가 날 것이 분명하기 때문에 $nest$를 정의해서 $nest$의 값을 swap 해주면 $nest[v[i]]$로 새의 둥지 번호를 알 수 있기 때문에 $nest$를 활용해 주고 $inv$를 $nest$의 역함수로 정의하면 풀 수 있다. 그러나 이를 처리해 주는 과정이 헷갈려 2번의 WA를 받았다.

 

E

문제를 보자마자 다익스트라 그래프 모델링 문제라는 생각이 들었다. 원래 그래프와 간선을 뒤집은 그래프를 저장해 두고 $(0,i)$를 원래 그래프에서 $i$에 도달하는데 드는 최소비용, $(1,i)$를 간선을 뒤집은 그래프에서 $i$에 도달하는데 드는 최소비용으로 정의해 모델링했다.

 

F

위와 아래의 합을 같게 맞추는 과정에서는 어느 쪽의 크기를 줄일지 정하기가 힘들기 때문에 이웃한 이빨 사이의 높이 차이를 줄이는 과정을 먼저 수행하고 길이를 맞추자는 생각을 했다. $A_i=U_i-Xi$로 정의했을 때 $A_i$가 내림차순이 되도록 하고 $B_i=U_i+Xi$로 정의했을 때 $B_i$가 오름차순이 되도록 2번 크기를 줄여주면 되기 때문에 이를 통해 이웃한 이빨들의 높이 차이가 $X$이하가 되도록 맞추어주고 위와 아래의 합이 같아지도록 조정해 주어 답을 구했다.

 

G

$k$가 작다는 사실을 활용해야 할 것 같았으나 방법이 떠오르지 않았고 dsu와 다익스트라 모델링으로 풀 생각을 했으나 시간 안에 코드를 완성하지 못했다.