NCPC 2022

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

할만한 셋을 훑어보다가 이 셋을 발견했는데 괜찮아보여서 풀어봤다.

3시간에 ABCDEGH만 풀었는데, F를 뭔가 시간에 쫓겨서 구현을 다 못한게 아쉽다.

쉬운 것부터 살펴보자. (백준 기준)

 

C. Coffee Cup Combo

 

i번째 수업에서 잠을 자려면 i번째, i - 1번째, i - 2번째 수업 모두에서 커피를 뽑을 수 없어야 한다.

단순하게 이를 체크해서, 잠을 안 자는 수업의 수를 세주면 된다.

 

D. Disc District

 

상당히 웃긴 문제인데, x^2 + y^2을 최대한 r^2에 가져다 붙이면 된다.

그러면...? (r, 1)이 제일 가깝다.

 

H. Highest Hill

 

h[j]가 peak가 되려면, 왼쪽으로 몇개와 오른쪽으로 몇개가 점점 더 작아져야 한다.

이때 (i, j, k)와 (i - 1, j, k)가 모두 peak일 때 (i - 1, j, k)의 높이가 (i, j, k) 이상이다.

따라서 j를 기준으로 최대한 작아지면서 왼쪽으로, 그리고 최대한 오른쪽으로 가서 i, k를 잡아야 한다.

-> i에서부터 최대한 커지면서 j를 잡고, 최대한 작아지면서 k를 잡으면 된다.

-> 이후 i 값은 k로 설정해주면, 모든 점을 최대 2번만 보기 때문에 O(N)으로 된다.

 

A. Ace Arbiter

 

우선 X + Y 값을 통해서 누가 서브인지는 확실히 알 수 있다.

모순이 될만한 상황이 무엇이 있을까?

1) 이전보다 갑자기 점수가 낮아지는 경우

2) 11점이 이미 만족되었는데, 게임이 끝나지 않은 경우

3) 뜬금없이 경기가 11 - 11이 된 경우

 

G. Graduation Guarantee

 

사실 문제만 딱 읽었을 때는 맞출 확률이 50%를 모두 넘기기에 모두 푸는게 좋지 않나란 생각이 든다.

하지만 그렇다면 문제가 이런식으로 나오진 않겠죠?

아무튼 적어도 확실한 것은 맞출 확률이 더 높은 문제를 푸는게 무조건 이득이다.

모든 문제를 정답률에 대해 내림차순으로 정렬하자.

그러면 무조건 앞쪽의 x 문제를 푸는게 제일 이득일 것이다.

dp[x][y] = (정답률이 높은 x문제를 풀었을 때, 점수가 y일 확률)

-> dp[x + 1][y + 1] += dp[x][y] * p[y], dp[x + 1][y - 1] += dp[x][y] * (1 - p[y])를 통해 O(N^2)으로 모두 구할 수 있다.

점수가 K점을 넘길 확률은 dp[x][K] + dp[x][K + 1] + ... dp[x][N]이다.

-> 이 값의 최댓값을 구해주면 된다.

DP table을 채우는 것도, K점을 넘길 확률을 구하는 것도 총 O(N^2)이니 총 O(N^2)

 

B. Berry Battle

 

예제와 같이 (1, 2), (2, 3) 형태의 그래프는 불가능하다.

하지만 (1, 2), (2, 3), (3, 4) 형태의 그래프는 가능하다.

claim) star graph만 아니라면, 이것은 무조건 가능하다.

-> 우선 star graph라면 반드시 그 중앙의 베리를 먹을 때 모든 개미를 모으므로 불가능하다

 

star graph가 아닌 경우 다음의 방법으로 가능하다 

1) 제일 인접한 노드가 많은 노드를 root이라고 하자 (문제풀이 당시에는 이를 centroid로 했다.)

-> root과 인접한 노드가 N - 1개인지를 확인함으로써 우선 star graph를 걸러낼 수 있다.

2) root와 인접한 노드 중 인접한 노드가 2개 이상인 또 다른 노드를 chk이라고 하자.

3) root을 우선 제일 먼저 따먹는다.

-> 이러면 (chk, root)이렇게 두 노드에는 최소한 한 마리의 개미가 올라탄 상태가 된다.

4) 이후 root를 기준으로 depth 순으로 하되, chk가 첫 번째가 되지 않도록 한다.

-> 이 과정을 진행한다면, (chk, root)에 있던 두 개미들은 절대로 같은 노드 위로 올라갈 수 없다.

-> 둘을 같은 노드에 올리려면, 둘 중 하나가 있는 노드를 따먹어야 하는데, 매번 한 템포 늦게 따라온다.

    마지막으로 따먹은 노드를 x라고 하면, 둘 중 하나는 x에, 하나는 p[x]에 존재한다

    이때 다음으로 따먹을 y는 depth가 x 이상이기에 절대로 x와 p[x]가 될 수 아니다.

 

J. Junk Journey

 

로봇이 (-50, -50), (50, -50), (-50, 50), (50, 50) 사각형의 변 위를 이동하면, 박스와 만날일이 없다.

우선 로봇이 왼쪽 아래 구석에 쳐박아 둔다. (-50, -50)정도로 가게 하면 된다.

이후 어떤 박스를 제거한다고 생각해보자.

그러면 슬그머니 그 박스의 L/R로 다가가서 우선 depot와 x좌표를 맞춘다.

이후 다시 왼쪽 아래 구석으로 온 길을 따라서 그대로 이동

그 다음에 그 박스의 U/D로 다가가서 depot로 박스를 밀어넣으면 된다.

이후 다시 온 길을 따라서 역주행.

 

E. Enigmatic Enumeration

 

Shortest cycle을 찾아야 한다.

사실 그래프에서는 BFS보다는 DFS를 먼저 고민해보지만, 진전이 없어서 DFS를 유기했다.

마침 'Shortest cycle'이기에 'Shortest distance'를 찾기 편한 BFS가 무언가 관련이 있다고 생각함

아무튼, N = 3000으로 매우 널널하게 주어지기에 모든 노드를 루트로 BFS를 돌린다고 가정해보자.

이때 어떤 점까지의 거리를 d[x]라고 하고, 어떤 점까지 가는 최단거리 방법의 수는 cnt[x]라고 하자.

cur -> nxt로의 간선이 존재한다고 하였을 때, 이 간선이 완성하는 cycle의 정보는 다음과 같다

1) length = d[cur] + d[nxt] + 1

2) count = cnt[cur] * cnt[nxt]

이때, 중복으로 세는 경우를 처리해주어야 하는데

1) 모든 cycle은 각 점을 root로 했을 때 세지기 때문에 ans /= len

2) length가 홀수라면, d[nxt] = d[cur]일 때 세지기에 (nxt, cur), (cur, nxt)로 두 번 세지고 ans /= 2

 

조심해야될 테스트 케이스는 다음과 같다.

5 6

1 2

2 5

1 3

3 5

1 4 

4 5

ans = 3

 

F. Foreign Football

 

s[0]의 길이를 고정한다면 확인해야할 것들은 다음과 같다.

문제에서 주어진 input은 grid[x][y]이라고 지칭한다.

 

1) 0행과 0열에 모순이 존재하는가. 

-> grid[0][x]와 grid[x][0] 간에 모순이 존재하지 않아야 한다.

-> grid[x][0]로 실패함수를 만들어, KMP를 굴렸을 때 맨 마지막 시점에 일치하는 개수가 P라고 하자.

-> 그러면 s[0]의 길이는 P, fail[P - 1], fail[fail[P - 1] - 1], ...만 가능하다.

->  마찬가지로 grid[0][x]로 실패함수를 만들어도 가능한 s[0]의 길이를 추릴 수 있다.

-> N * 2 - 2번의 KMP에 대해서 모두 가능한 s[0]의 길이만 x로 가능하다.

-> 이것은 O(TOTLEN = 1e6)으로 미리 계산해둘 수 있다.

 

2) 0행과 0열을 제외한 나머지에 모순이 존재하는가

-> 0행, 0열이 맞다고 인정하면, 모든 s들이 결정된다.

-> 그러면 grid[x][y]가 앞에서부터 s[x]와 len[x]만큼, 뒤에서부터 s[y]와 len[y]만큼 일치하는지 확인하면 된다.

-> 다른 말로는 grid[x][0]와 앞에서부터 일치하고, grid[0][y]와 뒤에서부터 일치하면 된다.

-> grid[x][0]와 앞에서부터 일치하는 횟수 L[x][0]와 grid[0][y]와 뒤에서부터 일치하는 횟수 R[0][y]를 미리 구한다.

-> 이러면 O(1)로 각 grid[x][y]가 적합한지 판단가능하므로 고정된 s[0]의 길이에 대해 O(N^2)

 

따라서 총 복잡도는 O(TOTLEN + (가능한 s[0]의 개수) * N^2)이 된다.

이때 S[0]의 길이는 최대 TOTLEN / (2N)이기 때문에 1e3을 넘을 수 없고 잘 돌아간다.

 

I. Icy Itinerary

 

Connected graph임이 주어지거나 한다면 살짝 adhoc하게 설계하는게 할만할 것이다.

하지만 딱히 조건 없이, 그냥 valid ordering이 존재함만 주어지기에 이런 설계법은 쉽지 않다.

일단 이런 경로가 무조건 생기긴 하는걸까?

 

상당히 풀이가 흥미롭다.

우선 1번 마을부터 돌아야한다는 조건은 무시하자.

그냥 적당히 (Bike로 가능한 경로) + (Ski로만 가능한 경로)의 deque가 있다고 생각하자.

다음에 i번째 마을을 추가한다고 생각해보자.

1) 맨 앞과 연결되어 있다면 -> 그대로 맨 앞에 추가

2) 맨 뒤와 연결되어 있지 않다면 -> 그대로 맨 뒤에 추가

3) 맨 앞과 맨 뒤가 연결되어 있다면 -> (ans[0], ~, ans[back])을 (i, ans[back], ans[0], ~)로 수정

4) 맨 앞과 맨 뒤게 연결되어 있다면 -> (ans[0], ~, ans[back])을 (~, ans[back], ans[0], i)로 수정

이렇게 N개의 마을로 이루어진 적당한 경로가 존재한다.

 

이때 1번 마을을 맨 마지막에 추가한다면, 1번 마을이 무조건 맨 앞이나 맨 뒤에 있다.

경로를 그대로 뒤집어도 valid한 경로이므로 무조건 답을 구할 수 있다.

 

K. Keyboard Queries

 

일단 당연히 if and only if [a, b]와 [x, y]의 길이가 달라야 Not Equal이다.

길이가 같으면 Equal인지 Unknown인지 판단해야 한다.

[a, b]와 [y, x]를 비교하는게 아닌 [a, b]와 [x, y]를 비교해야하기에 Manacher적인 생각으로는 쉽지 않다.

 

[a, b]와 [x, y]와 같은지 해싱으로 비교하려면, 결국 S를 적당히 관리하고 있어야 한다.

-> 해싱값 관리만 segtree등으로 잘 한다면, [a, b]의 값은 O(lgN)으로 구할 수 있다.

Union find를 관리해야하는데, query type = 1일 때 [L, R]의 모든 x에 대해 (x, L + R - x)를 merge해볼 수는 없다.

근데 난 도저히 생각해도 S[x]와 S[L + R - x]가 다른 x를 어떻게 찾아야 할지 모르겠더라.

이러한 x들이 서로 붙어있는 것도 아니고, 어떤 규칙을 이루고 있지도 않다.

 

[L, R]이란 입력이 들어왔다면, 대충 [L, mid] == [mid, R]이 되도록 만들어주면 된다.

-> 이게 이미 성립하는지는, 앞에서의 해싱을 이용하면 되는데, 세그트리를 쓰면 O(lgN)이다.

이것은 쪼개면 [L, mid1] == [mid3, R] & [mid1, mid] == [mid, mid3] (단, L < mid1 < mid < mid3  < R)

-> 위에서 [L, mid] == [mid, R]이 성립하지 않는다면, 다음 단계를 진행하면 된다.

굉장히 재귀가 많이 돌아갈 것 같지만, 실상은 merge 1번당 재귀는 최대 lgN번만 발생한다.

총 Merge의 횟수는 당연히 N - 1이므로, O(NlgN^2)으로 처리된다.

Merge하는 과정 자체도 S2L이 관여하므로 O(NlgN^2)이 필요하다.