[Atcoder] ABC 404 후기

https://atcoder.jp/contests/abc404/tasks

코드
https://github.com/kss418/Atcoder/tree/main/ABC/400/404

A (1:16)

각 알파벳에 대해서 모두 시도해보고 없는 것을 출력하면 된다.

B (5:36)

어차피 4번 회전하면 동일한 격자가 되기 때문에 각 회전에 대해서 다른 칸의 개수를 구하고 그 중 최솟값을 구하면 된다.

C (9:42, -1)

그래프가 사이클 그래프인 조건은 각 정점의 indegree가 2이고 연결 요소가 1개인 것이다. 첫 제출에 연결 요소가 1인 것을 판단을 해주지 않아서 틀렸다. 연결 요소가 1인 것은 유니온 파인드로 판단 해줬다.

D (17:43)

한 동물원에 대해서 두 번 이상 방문할 필요가 없기 때문에 $N$개의 동물원을 $2 * N$으로 만들어주고 모든 경우의 수에 대해서 브루트포스를 해주면 된다.

E (31:34)

각 칸을 정점으로 보고 각 칸은 $C_i$ 거리 이내의 앞의 칸과 간선으로 연결 되어 있는 그래프를 생각해보자. 또한 각 정점의 콩을 앞으로 옮기면 콩을 한번에 옮길 수 있는 양에는 제한이 없으므로 하나로 합쳐서 옮길 수 있다.

각 정점에 대해서 간선으로 연결 된 칸에 콩이 있으면 이전의 콩과 합쳐서 옮길 수 있으므로 1의 비용이 든다. 만약 간선으로 연결 된 칸에 콩이 하나도 없으면 콩이 있는 정점과 최단거리만큼의 비용이 든다. 사이클이 없는 그래프이기 때문에, 이는 DP로 해결 할 수 있다.

G (--, -4)

처음 풀이는 두 정점의 값의 차이를 weighted union find로 관리를 해줬다. 각 간선에 대해서 모순이 있는지 또한 weighted union find로 판단 할 수 있다. 이 문제에서는 배열의 최소 합까지 구해야 하는데 이를 DP로 해결 하려고 했다. $DP[i]$를 $i$번째 인덱스에서의 최소 합으로 놓고 weighted union find의 값들로 DP식을 채웠는데 이 부분에서 틀린 것 같다.

대회 시간 내에 못 풀어서 에디토리얼을 봤는데 예전에 백준에서 풀어본 문제의 변형 문제였다.
https://www.acmicpc.net/problem/7577

각 간선 $S, E, C$는 다음과 같은 부등식으로 나타낼 수 있다.
$Sum[E] - Sum[S - 1] = C$

위의 등식에 대해서는
$Sum[E] \leq Sum[S - 1] + C$
$Sum[E] \geq Sum[S - 1] + C$ -> $Sum[S - 1]\leq Sum[E] - C$
와 같이 두개의 부등식으로 나눌 수 있다.

또한 $1 < i < N$에 대해서
$Sum[i] - Sum[i - 1] \geq 1$ 이여야 한다.

각 부등식을 모두 성립하게 만드는 값의 최댓값을 구하는 것은 벨만포드로 구할 수 있다.

이 문제에서는 최솟값을 구하는 것이므로 음수 벨만포드를 돌려서 정답을 구해주면 된다.
또한 음수 사이클이 발생하면 부등식을 만족하는 해가 존재하지 않는 것이므로 -1을 출력해주면 된다.