2023 Benelux Algorithm Programming Contest (BAPC 23)

https://codeforces.com/gym/104790

https://www.acmicpc.net/category/detail/4010

 

BAPC 치고도 조금 쉬운 셋 같다. 백준에서의 난이도도 조금 과평과된 느낌...?

버추얼을 친 시점 직후에 div2가 있어서 채점 큐 밀리기 전에 후다닥 풀었다.

꽤 오랜만에 풀어서 여러모로 좀 피곤했는데, 3시간 반 정도 걸렸다.

후기를 쓰는 순서는 문제 푼 순서이고, 문제는 대시보드를 참고해서 순서를 정했다.

 

A. apt upgrade

 

(정렬해서 얻은 제일 큰 min(n, m + k)개의 합) / (전체의 합)

 

B. Battle Bots

 

log2(n) + 1.

내장함수를 썼다가 틀렸다... 굳이?

 

D. Democratic Naming

 

각 m개의 자리마다 제일 많이 선택된 char를 고르면 된다.

 

F. Funicular Frenzy

 

단순하게 모든 시점 i에 대해 i부터 기다렸을 때 필요한 시간을 계산해보면 된다.

-> 모든 시점에 대해 항상 a[i]명이 추가되고 c명이 제거된다고 생각할 수 있다. (단, 0명 미만이 되지 않도록)

-> 남는 사람의 수가 j명이라면, 기다리는 시간은 단순히 j / c가 된다.

-> j / c + i가 n 이하인 경우들만 잘 고려해주면 된다.

 

C. Compressing Comands

 

단순하게 모든 file path를 트리 형태로 만들어두면 된다.

 

그러면 i번에서 i + 1로 넘어갈 때

-> depth가 같아지도록 조정하는 과정

-> i번과 i + 1이 속한 file이 같아지도록 조정하는 과정

을 고려해주면 간단하게 답을 셀 수 있다.

 

보통 이렇게 단순하게 거리를 재주면 문제가 생길 수도 있지만, file path의 특성상 괜찮다.

모든 file path의 깊이의 합은, 모든 file path의 길이의 합 이하이기에, 시간을 걱정할 필요는 없다.

 

J. Jungle Job

 

dp[i][j] = (제일 낮게 있는 원숭이가 i번 칸에 있고, 총 원숭이가 j명 있는 경우)

그러면 매번 i번 칸의 적당한 child에 대해서 new_dp[i][p + q] += old_dp[i][p] * dp[child][q]의 계산을 하면 된다.

 

이 dp는 무식하게 굴려도 시간 내에 돌아간다.

https://codeforces.com/blog/entry/100910 #7 참고

 

E. Exam Study Planning

 

dp[i] = (i개의 시험을 통과하였을 때 남는 공부 시간)

그렇다면 s, p, e, a라는 입력이 들어왔을 때, 

-> 우선 s라는 시간이 주어졌으니 사실 공부할 시간이 s 추가된 것이나 다름 없다.

-> 어떤 시간 T에 시험이 끝난다면, -T를 해주어, T만큼 회수해간다고 여기면 된다.

-> 시험을 그냥 낙제한다면, 공부시간이 (e - s)만큼 감소한다 생각할 수 있음. new_dp[i] = max(dp[i] - e + s, new_dp[i])

-> dp[i] >= a이고 공부할 경우 공부시간이 a + (p - s)만큼 감소하므로, new_dp[i] = max(dp[i] - a - p + s, new_dp[i])

 

G. Geometry Game

 

진짜 단순구현

 

L. Locking Doors

 

우선 SCC로 묶이면, 그 그룹은 exit가 한 개라도 있으면 되니, SCC로 모두 묶는다.

이후에는 X -> Y 문을 닫아야 하면 deg[Y]++를 하고, deg값이 0인 그룹의 수를 세주면 된다.

-> 어떤 Z의 deg가 0이 아니라면, 적당히 deg가 0인 W에서 도달 가능할 것이고, W에만 exit이 있으면 된다.

 

K. King of the Hill

 

맞는지 모르겠다.

일단 기본 아이디어는 높아지는 방향으로 계속 가는 것이다. -> 이거만으로는 안되며, 반례만들기 쉬움

그래서 랜덤을 존나 쳐서 높이가 계속 높아질 때까지 했다.

흠...

아무튼 계속 높아지는 방향으로 이동하는데, 중간중간 충분히 랜덤으로 위치를 잘 옮겨주면 된다.

 

H. Hidden Art

 

W가 작은것을 보았으니, W를 중심으로 푼다.

적당히 (i, X), (i, Y), (j, X), (j, Y)가 possible을 이룬다고 가정하자.

사실 i, j, X, Y는 모두 H, W를 넘어가도 상관 없는데, 편의상 이들에게 %H, %W를 시켰다고 하자.

그렇다면 Y = (X + j - i + W * (원하는 만큼) ) % H일 것이다.

이때 (원하는 만큼)은 말 그대로 아무 숫자나 될 수 있다.

따라서 g = __gcd(H, W)라고 한다면, Y % g = (X + j - i) % g만 만족해주면 된다.

 

모든 i, j (단, i < W, j < W) 쌍에 대해서,

어떤 k번째 열에서 grid[i][k] = 'W', grid[j][k] = 'R'이라면 chk[k % d]["WR"] = 1로 저장을 해두자.

그리고 chk[(k + j - i ) % d]["BG"] = 1인지 확인을 하면 된다.

만일 chk[(k + j - i) % d]["BG"] = 1이라면, 적당한 k'이 존재해서 행은 i, j 열은 k, k'을 고르면 사각형이 나올 것이다.

 

I. International Irregularities

 

u -> v를 가는 방법은 오직 2가지이다

1) quarantine 없이 u에서부터 살살 v로 이동한다.

2) 한 번에 어떤 지점 w로 가서 t[w]만큼 시간을 보내고, w에서부터 살살 v로 이동한다.

여러 해결 방법이 있겠지만, 다음과 같이 진행했다 (꽤 쉬운 풀이도 있을 것 같다.)

 

일단 트리를 만들건데, 어떤 점 i의 parent는 자신이 m 이하로 감소했을 때 최대한으로 앞으로 갈 수 있는 위치이다.

오프라인 쿼리를 할 것인데, 도착지가 n - 1인 것부터 차례대로 0까지 진행할 것이다.

seg1은 초기에 모든 값을 1로, seg2는 t[i] + 2로 세팅해둔다.

seg1은 앞으로 1)의 방식으로 도달하는데 필요한 값을, seg2는 2)의 방식으로 도달하는데 필요한 값을 줄 것이다.

 

seg1을 생각해보자.

이미 1로 초기에 설정한 이유는, u -> v 이동시 만일 u < v라면 비행기를 1번 타야 하기 때문이다.

도착지가 x인 것을 고려하다가 x - 1인 것으로 바뀌면, 어떤 노드들에서 값이 바뀌어야 할까?

단순하게 x가 ancestor로 있는 노드들에만 1을 추가해주면 된다.

예를 들어, a -> b -> c -> x 로 트리에 연결되어 있었다면,

기존에는 그대로 a -> b -> c -> x로 끝났겠지만, 이제는 a -> b -> c -> x -> x - 1이 되기 때문이다.

따라서 오일러 투어 트릭으로 seg1.add(in[i] + 1, out[i], 1)만 해주면 된다.

이제 만일 u -> x라는 쿼리를 처리해야하면 seg1.read(in[u], in[u] + 1)이 곧 1)에 필요한 시간이다.

 

seg2를 생각해보자.

t[i] + 2로 모두 세팅해둔 이유는 u -> i -> v로 이동하고, i에서 자가격리하면 t[i] + 2의 시간이 들기 때문이다.

얘도 비슷하게 자기보다 아래에 있는 애들에만 1을 더해주면 된다.

대신애 1)은 꼭 u에서 시작되어야 하지만, 2)는 아무 곳이나 경유할 수 있으니 seg2.read(0, n)이 곧 2)에 필요한 시간이다.

 

seg1, seg2 공통으로 만일 x -> x - 1로 자가격리 없이 이동이 불가능하면, 끊어버릴 필요가 있다.

따라서 parent[x] = -1이라면 x 밑의 모든노드에 1e9등을 더해주어야 한다.

설명이 긴데, 발상 자체는 오프라인 쿼리이고, 구현도 그리 빡세지 않다.