[Atcoder] ABC 402 후기

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

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

A (0:35)

문자열을 돌면서 대문자인 경우에만 출력을 해주면 된다.

B (1:56)

1번 쿼리일 때 Enqueue, 2번 쿼리 일 때 Dequeue 연산을 해주면 된다.

C (5:50)

각 $A[i]$값들을 $i$에 연결된 간선으로 모델링 후에 차례대로 간선을 지우면서 정점의 indegree가 0이 될 때마다 정답에 1씩 추가해주면 된다.

D (33:30)

문제를 읽고 떠오르는게 없어서 바로 E로 넘어갔다.
E에서 20분 정도 삽질하다가 다시 돌아와서 문제를 다시 봤는데 문제 풀이를 바로 떠올렸다.

기울기가 같은 선들은 항상 중앙에 대해서 대칭이다. 다시 말해서 기울기가 같은 선들은 정점 두개의 합이 같다. 물론 MOD M을 해줘야 한다.

배열로 각 합들의 개수를 관리해주고 현재 보는 인덱스에 현재 합과 같은 값들의 개수를 빼준 것의 총 합을 구하면 된다.

E (71:16, -1)

처음에 문제 이해를 잘 못 해서 문제를 틀린 방식으로 풀고 있었다.

$DP_{i, j, k}$를 $i$번째 정점을 보고 있을 때, $j$의 비트가 1이면 이미 그 정점의 점수를 얻었고 0이면 점수를 얻지 않았고, $k$엔을 갖고 있을 때 최댓값이라고 정의하자.

$DP_{i, j, k}$는 $j$의 비트가 꺼져있는 정점을 순회하면서 다음 값들의 기댓값 중의 최댓값으로 갱신해주면 된다.

점화식은 다음과 같다.
$DP_{i, j, k} = MAX(DP_{nxt, j ,k - c[nxt]} * (100 - p[cur]) / 100 + (DP_{nxt, j | (2^{nxt}) ,k - c[nxt]} + s[cur]) * p[cur] / 100)$
앞의 값은 문제를 푸는데 실패 했을 때, 뒤의 값은 문제를 푸는데 성공 했을 때 기댓값이다. 또한 $nxt$의 값은 $j$의 비트가 0인 값들이다.

F (--, -3)

옛날에 풀었던 앳코더 문제랑 거의 비슷해서 아이디어는 바로 떠올렸다.
https://atcoder.jp/contests/abc271/tasks/abc271_f

$N*N$의 배열에서 오른쪽 또는 아래쪽으로만 이동 할 수 있고 $1, 1$에서 $N, N$까지 가야 할 때 항상 가운데 대각선을 지나게 된다. 그러므로 $1, 1$에서 가운데 대각선으로 갈 때 만들어지는 숫자들과 $N, N$에서 가운데 대각선으로 갈 때 만들어지는 숫자들의 합에서 $M$으로 나눴을 때 최댓값을 구해주면 된다.

E까지 풀고 시간이 얼마 안남았기 때문에 촉박하게 풀었는데 처음 제출 했을 때에는 $1, 1$에서 출발 했을 때 생긴 값들에 $10^N$을 곱해줬는데 $N$이 20까지 들어오기 때문에 오버플로우가 났다.

그래서 이 값들을 애초에 $M$을 중간 중간에 나눠주면서 계산을 했는데도 TLE가 나서 결국 풀지 못했다. 정답을 계산할 때 $1, 1$에서 출발한 값과 $N, N$에서 출발한 값을 모두 순회해서 구했었는데 여기서 TLE가 난 것이다.

대회가 끝나고 에디토리얼을 봤는데 정답을 구할 때 모두 순회한 로직을 이분탐색으로 바꿔서 푸니 통과했다.