ABC335 E - Non-Decreasing Colorful Path

2024-01-10

공식 에디토리얼

원문 링크
https://atcoder.jp/contests/abc335/editorial/9037

먼저, 연결 그래프이므로, \(1\)부터 \(N\)까지의 경로가 존재합니다. 여기서, 최대 점수는 \(0\) 이상이라는 것을 알 수 있습니다.
그렇게 되면 고려해야 할 것은 점수가 올바를 것 같은 경로입니다. 정점 \(u\)와 정점 \(v\)를 잇는 간선에 대해 이하와 같은 고찰을 할 수 있습니다.

• \(A_u < A_v\) 라면, 이 간선을 \(u \rightarrow v\) 방향으로 지나가는 것으로 생각하면 된다.
• \(A_u > A_v\) 라면, 이 간선을 \(v \rightarrow u\) 방향으로 지나가는 것으로 생각하면 된다.
• \(A_u = A_v\) 라면, 이 간선은 어느 방향으로도 지나갈 수 있다.

이하와 같이 DP 식을 생각할 수 있습니다.
\[dp|v| = 정점\ 1부터\ 정점\ v까지의\ 경로의\ 잠정적인\ 최고\ 점수\]

사실 다음과 같이 바꿔 말하는 것도 가능합니다.
\(A_u = A_v\)인 간선 \(u - v\) 만을 남긴 그래프를 \(G\) 라고 할 때, \(G\) 상에서 같은 연결 요소에 속하는 정점들은 하나의 정점으로 봐도 된다.

예를 들면,

• \(A_p < A_q = A_r < A_s\)
• 간선 \(p - q\) 가 존재한다.
• 정점 \(q, r\)이 \(G\) 상에서 같은 연결 요소에 속한다.
• 간선 \(r - s\) 가 존재한다.

인 정점 \(p, q, r, s\)에 대해, \(p → q → … → r → s\) 경로를 \(S\)의 단순 증가성이 무너지지 않게 지나는 것이 가능합니다.
\(q\)부터 \(r\)까지의 이동은 \(G\) 상에서 \(q, r\)이 속하는 연결 요소의 모든 영역을 하나로 묶어, 거기에 속하는 간선을 지나는 것으로 취급하면 됩니다.

그럼, 정점들을 동일시한 후 남는 것들은 \(A_u < A_v\)인 간선 \(u - v\)들 뿐입니다.
이 때, 아까 정의한 \(dp\)는 \(A_u < A_v\)인 간선 \(u - v\)를 \(A_u\)가 작은 순으로 전이하면 얻을 수 있습니다. (풀어야 할 문제가 DAG 상의 최장경로 문제가 됩니다.)

전이를 할 때, 앞서 정점들을 동일시 하기로 했다는 사실을 잊지 않게 주의해줍시다. 정점의 동일시는 Union-Find로 관리할 수 있습니다.

다익스트라를 사용하는 풀이

원문 링크
https://atcoder.jp/contests/abc335/editorial/9054

다익스트라 알고리즘을 이용하면 간선의 가중치가 음이 아닐 때 시작점부터의 최단거리를 구할 수 있습니다.

while 거리가 미확정인 정점이 있음:
  미확정인 정점 중 거리가 가장 짧은 정점의 거리를 확정한다
  그 정점과 간선으로 연결된 정점들의 거리를 갱신한다

다익스트라 알고리즘의 정당성의 증명과 마찬가지로 생각해보면 이 문제에 대해 다음과 같은 알고리즘이 성립한다는 것을 알 수 있습니다.

while 점수가 미확정인 정점이 있음:
  미확정인 정점 v 중 A[v]가 가장 작고, 그 중에서 점수가 최대인 정점의 점수를 확정한다
  그 정점과 간선으로 연결된 정점들의 점수를 갱신한다

다익스트라 알고리즘과 비슷한 구현으로, 이 알고리즘은 충분히 시간 내에 작동합니다. 예를 들면, (A[v], 정점 v의 점수 * (-1)) 의 쌍을 키 값으로 하면 됩니다.

이번에도 E에서 막혔다

ABC는 계속해서 도전하고 있지만, E를 풀어본 적은 아직까지 한 번 밖에 없고,
대부분은 D까지 30분 내외로 푼 다음 E에서 막혀왔다.

올해부터는 콘테스트 후 공식 해설을 번역하며 업솔빙해서 실력을 좀 더 올려봐야지…