[Atcoder] ABC 405 후기

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

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

A (0:59)

문제 조건에 따라서 조건 분기를 잘 처리 해주면 된다.

B (3:26)

각 숫자의 카운트와 한개라도 있는 숫자의 카운트를 세주면서 한개라도 있는 숫자의 카운트가 $M$이 아닐 때의 수를 출력해주면 된다.

C (5:03)

각 $A_{i}$에 대해서 이전의 값들과 전부 곱해준 값이고, 덧셈과 곱셉이 결합법칙이 성립하기 때문에 누적 합으로 이를 빠르게 구해줄 수 있다.

D (14:38)

각 간선의 비용이 $1$이므로 $"E"$와의 최단거리를 BFS로 구할 수 있고 이를 역추적해서 정답을 구해주면 된다.

E (--)

DP로 푸는건 아닌 것 같고 조합론으로 푸는 것 같은데 발상이 전혀 안 떠올라서 15분 정도 잡다가 그냥 넘어갔다.

에디토리얼에서는 포도의 오른쪽에는 사과와 오렌지가 존재하면 안되고 포도의 왼쪽과 오른쪽의 바나나가 존재할 수 있으므로, 포도의 왼쪽의 바나나를 개수를 기준으로 반복문을 돌면서 경우의 수를 구한다.

가장 앞에 있는 포도의 왼쪽에는 $A$개의 사과, $B$개의 오렌지, $i$개의 바나나가 존재하고, 사과와 바나나는 순서가 정해져 있으므로 사과와 바나나 사이에 오렌지를 끼워 넣는 방법과 같다.

이는 $\binom{A + B + i}{B}$와 같다.

가장 앞에 있는 포도의 오른쪽에는 $C - i$개의 바나나와 $D - 1$개의 포도가 존재하고 바나나와 포도에는 순서가 정해져있지 않으므로 자유롭게 배치 할 수 있다.

이는 $\binom{D - 1 + C - i}{D - 1}$와 같다.

각 $i (0 \leq i \leq C)$에 대해서 위의 두 값을 곱한 합을 출력 해주면 된다.

F (89:52)

어떤 선분과 쿼리의 선분이 교차하기 위한 조건은 쿼리의 선분의 시작점 또는 종료점이 다른 선분에 포함 되어야 한다.

나는 시작점을 관리해주는 세그먼트 트리와 종료점을 관리해주는 세그먼트 트리를 사용해서 문제를 풀었다.

우선 각 쿼리와 선분을 시작점과 종료점으로 분리를 해주고 각 반대편의 점, 시작점 -> 종료점, 종료점 -> 시작점의 정보도 함께 넣어주고 정렬을 해준다.

각 쿼리마다 현재 포함될 수 있는 선분들을 세그먼트 트리에 업데이트 해준다.

현재 쿼리가 시작점이 기준인 쿼리면 시작점을 관리해주는 세그먼트 트리의 현재 쿼리의 시작점까지의 값을 더한다.
이는 현재 포함되는 선분의 개수를 더한 것과 같다.

그리고 종료점을 관리해주는 세그먼트 트리의 현재 쿼리의 종료점부터 끝까지의 값을 빼준다.
이는 시작점과 종료점이 동시에 포함되는 선분의 개수를 뺀 것과 같다.

반대로 현재 쿼리가 끝점이 기준인 쿼리면 종료점을 관리해주는 세그먼트 트리의 현재 쿼리의 종료점부터 끝까지의 값을 더하고, 시작점을 관리해주는 세그먼트 트리의 처음부터 현재 쿼리의 시작점까지의 값을 빼준다.

각 쿼리를 정렬해서 오프라인 쿼리로 값을 구했으므로 각 원래 인덱스 또한 쿼리에 저장해서 원래 인덱스에 정답을 저장 후에 출력해야 한다.