[Atcoder] ABC 403 후기

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

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

A (0:38)

홀수의 인덱스들의 값만 더해서 출력해주면 된다.

B (3:16)

$T$의 인덱스를 순회하면서 $U$와 일치 할 수 있는지 확인한다. $T[i]$가 $"?"$가 아니면서 $U[j]$와 다르면 일치 할 수 없으므로 건너 뛴다. 만약 한번이라도 일치 할 수 있으면 Yes, 아니면 No를 출력하면 된다.

C (5:42)

각 유저가 어떤 페이지를 접근 할 수 있는지 빠르게 확인하기 위해서 셋을 사용했다. 1번 쿼리가 들어올 때는 셋에 삽입, 2번 쿼리는 따로 배열에 1값을 넣어줬다. 3번 쿼리가 들어왔을 때 셋에 그 페이지 번호가 있거나 배열 값이 1이라면 Yes, 아니면 No를 출력하면 된다.

D (27:04, -1)

처음에 DP인걸 깨닫고 나는 대부분 DP를 탑다운으로 풀기 때문에 아무 생각 없이 탑다운 코드를 짰다. 하지만 샘플 케이스조차 돌아가지 않았는데, 배열의 값이 1e6까지 들어오기 때문에 무조건 메모리 초과가 날 수 밖에 없다.

이 문제는 배열에서 값을 제거할 수 있을 때 $M$만큼 차이가 나는 값을 없게 만드는 문제이다. 다르게 말하면 $M$으로 나눈 나머지가 같은 값들을 중복 없이 오름차순으로 정렬 했을 때 인접한 값이 존재하면 안된다.

이는 DP로 해결 할 수 있다.
$DP[i][j]$를 $j$가 $0$일 때 $i$를 제거했을 때, $j$가 1일 때는 $i$를 제거하지 않았을 때 최소 값 제거 수 라고 정의 하고, $MIN(DP[i][0], DP[i][1])$ $0\leq i < m$ 의 값을 더해주면 된다.

$M$이 $0$일 때는 $DP$식의 사이클이 생기기 때문에 예외 처리를 해줘야 한다. 처음 제출 할 때 예외 처리를 안해줘서 1번 틀렸다.

E (53:15, -1)

집합 $X,Y$를 트라이로 관리해주자. 그러면 $X$에 원소가 들어올 때는 $Y$에 $X$가 접두사가 되는 값들을 전부 제거해주고 $X$에 원소를 삽입해준다.

$Y$에 원소가 들어올 때는 $X$에 원소의 접두사가 되는 값이 있으면 건너뛰고 아니면 원소를 삽입하면 된다.

첫번째 제출에서 $X$에 원소를 삽입할 때 $Y$의 원소를 제거하는 로직을 잘 못 짜서 틀렸다.

F (--, -3)

처음에 백준에서 풀어본 DP문제와 비슷에서 코드를 바로 짜기 시작했다. 코드를 짜다 보니 괄호를 치는 부분에서 예외 처리 해야 할 것이 많았어서 결국 풀지 못했다. 곱하기를 하는 부분에서 반례가 있었다.

대회가 끝나고 에디토리얼을 보니 DP 배열 두개를 사용한다. 한 배열은 길이가 최소가 되는 값을 저장하고, 한 배열은 항이 되는 식 중 최소가 되는 값을 저장한다.

DP1을 길이가 최소가 되는 값, DP2를 항이 되는 식 중 길이가 최소가 되는 값으로 정의하자.

우선 1로만 만들 수 있는 값인 1, 11, 111, 1111을 그대로 DP1, 2식에 초기화를 시켜준다.
그러면 점화식은 다음과 같아진다.

$DP1[i] = DP1[j] + "+" + DP1[k](j + k == i)$
$DP1[i] = DP2[j] + "*" + DP2[k](j * k == i, j> 1)$

DP2는 항이 되는 식이기 때문에 괄호를 추가해준다.
$DP2[i] = "(" + DP1[j] + "+" + DP1[k] + ")"(j + k == i)$
곱하기는 + 보다 연산자 우선순위가 높기 때문에 괄호가 필요 없다.
$DP2[i] = DP2[j] + "*" + DP2[k](j * k == i, j>1)$