AtCoder Beginner Contest 318

문제풀기

lml 2023. 9. 2. 23:15

A. Full Moon

단순하게 M, M + P, M + 2P, ...을 체크하면 된다.

수학에 자신 있으면 바로 답을 내도 됨.

B. Overlapping Sheets

모든 직사각형을 미리 칠해두고, 마지막에 칠해진 직사각형의 수를 세면 된다.

C. Blue Spring

만일 x개의 pass를 사는게 확정된다면, 제일 비싼 xD개의 trip을 얘네로 때우는게 제일 이득이다.

따라서 모두 정렬해두고 모든 x에 대해서 필요한 비용을 계산해보고, 최솟값을 답으로 내면 된다.

D. General Weighted Max Matching

{1, 2, ... N}의 부분집합들에 대해서 비트마스킹을 합시다.

dp[s] = (set s내에 포함된 점에 대해서 얻을 수 있는 최대값)

그렇다면 s의 제일 작은 원소가 i라면

dp[s] = max( dp[s - i - j] + d[i][j] ) 가 된다.

따라서 비트마스킹 dp를 하면 O(2^n * n)으로 답을 구할 수 있다.

E. Sandwiches

모든 숫자 1 ~ N에 대해서 pos[x] = { a[i] = x인 모든 i } 라고 정의하자.

그렇다면 모든 x, k, i (i < k) 쌍에 대해서 pos[x][k] - pos[x][i]을 모두 더해주면 된다.

이때 위의 값은 k에 대해 (pos[x][k] - pos[x][k - 1] - 1) * (k - 1) + (pos[x][k - 1] - pos[x][k - 2] - 1) * (k - 2) + ...이다.

k가 아무리 변하더라도 (pos[x][i] - pos[x][i - 1] - 1) * i 가 더해짐에 주목하자.

따라서 각 pos[x]에 대해 앞에서부터 (pos[x][j] - pos[x][j - 1] - 1) * (j - 1)를 tmp에 더해주고, 답에 tmp를 더해주면 된다.

F. Octopus

모든 i, j에 대해 X[i] - L[j] <= START <= X[i] + L[j] 여부가 같다면 두 시작위치 P, Q는 가능한지 여부가 같다.

따라서 모든 시작위치는 X[i] - L[j], X[i] + L[j] + 1들로 표현할 수 있다.

이렇게 N^2개의 시작위치에 대해서 가능한지 여부를 확인하면 된다.

저 위치들을 정렬해둔게 event이고 event[i]가 가능하다면, event[i + 1] - event[i]를 더하면 된다.

가능한지 여부는 단순하게 abs(START - X[i])를 정렬한게 Y라면, Y[i] <= L[i]인지만 확인하면 된다.

아주 잘 구현하면, O(N^3)이 가능할 것 같다.

근데 N^3lgN도 통과하니 잘 구현할 필요는 없고 대충 구현해도 된다.

G. Typical Path Problem

이 문제는 플로우로 표현 가능하다

모든 점 x는 (들어오는 점 2x) -> (나가는 점 2x + 1)로 두 점으로 쪼갤 수 있다.

B를 제외한 모든 점은 (2x -> 2x + 1)의 capacity를 1, B는 2로 설정하자.

Source -> 2B의 capacity는 2, 2A + 1 -> sink, 2C + 1 -> sink에 capacity 1을 부여

이러면 각 점을 한 번만 들리므로 simple path가 된다.

Dinic의 복잡도는 V^2E로 알려져있다.

하지만, 이 복잡도는 사실 flow 값이 매우 작아지면 훨씬 작은 값으로 떨어진다.

이 사실을 모르면 다시 플로우에 대해서 공부하면 된다.

이게 그정도로 떨어지는지는 잘 몰랐는데 대충은 알아서 믿음의 제출을 했다.

Ex. Count Strong Test Cases