[Atcoder] ABC 407 후기

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

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

A (1:30)

$N$ % $M$이 $(M + 1) / 2$ 이상이면 $ceil(N/M)$ 아니면 $floor(N/M)$을 출력하면 된다.

B (3:14)

주사위 2개의 모든 경우의 수를 세면서 정답을 찾으면 된다.

C (7:39)

뒤의 값들을 증가시키면 앞의 값들이 전부 증가하므로 뒤에서부터 현재 값에서 $S_{i}$를 만들기 위한 개수를 더하면 된다.

0을 추가하는 것도 하나의 연산이므로 $|S|$도 정답에 추가해줘야 한다.

D (29:22, -1)

$N * M \leq 20$ 이므로 블록을 최대 10개까지 넣을 수 있다.

각 $i, j$에 대해서 세로 블록, 가로 블록, 블록을 넣지 않는 경우의 수 3개로 백트래킹을 돌리면 된다.

E (87:33, -3)

처음에 우선순위 큐 + 그리디로 접근하다가 반례가 있는걸 알고 40분 동안 시간을 날렸다.

올바른 괄호열의 조건은 $($를 1, $)$를 -1이라고 했을 때 모든 인덱스에 대해서 누적 합의 값이 음수이면 안되고 마지막 인덱스의 누적 합의 값이 0이여야 한다.

모든 인덱스에 대해서 누적 합의 값이 음수이면 안된다. 즉 모든 인덱스에 대해서 현재 인덱스가 $i$라고 할 때 $($가 최소 $(i + 1) / 2$개가 존재해야 한다.

1 ~ $2 * N$까지 돌면서 각 인덱스 $i$에 대해서 현재 고른 $($의 개수가 $(i + 1) / 2$보다 작으면 우선순위 큐를 사용해서 최댓값을 구해주면 된다.