2021 ICPC Pacific Northwest Region Division 1 풀이.

 

 

 

2022년 3월 26일 즈음 팀연습으로 풀어보았던 셋이다.

일주일이 지난 지금 시점 한 문제 빼고 모든 문제를 업솔빙해서, 풀이를 올려보고자 한다.

 

개인적으로 에듀케이셔널 한 느낌이 강한 측면이 있었다.

구현/지문이 더럽지 않아서 너무 좋았다.

 

dp가 많이 나오는 듯한 경향은 우리나라랑 잘 맞는듯 하기도 하다.

연습셋 하기 전에 처음이니까 쉬운셋 하자고 해서 골랐고, 연습 때는 C D E I 4문제를 못 풀고 9솔로 마무리 했었다.

 

연습셋 후기는 귀찮아서 다음에 잘 봤을때 쓰겠다 ㅋㅋ.

 

 

 

A. Circle Bounce 

 

이 문제는 마음에 쏙 드는 문제였는데, 풀면서 얻어간 것이 좀 있었다.

 

우선 확률을 기약분수로 나타내는 문제에 대해서, modulo를 취하면 곱하기를 해도 일정하게 유지된다는 성질이 있는데, 이를 제대로 확인해볼 기회기도 했고, 그쪽 개념이 약했는데 풀면서 확실하게 이해하게 됐다.

 

문제를 요약하면, 공을 일정한 입사각으로 날렸을 때, n+1번째로 튕기는 위치의 x좌표를 분수로 표현해서, modulo 취해서 출력해주면 된다.

 

이 문제는 기본적인 중/고등학교 수학지식이 필요하다.

 

1.발사하기 전의 점, 발사하고 원에 도착한 점, 그리고 원의 중심 3점을 잡은 삼각형은 항상 합동이다.

 

몇 번 튕겼는지와는 상관없이 항상 같은 모양의 삼각형 만을 움직인다는 점을 쉽게 보일수 있다.

원의 반지름은 일정하므로, 이등변 삼각형이고, 각도가 일정하므로 sas합동이다.

 

2. cos x, sin x의 정의를 가져오자.

 

사실 cos x,sin x의 정의는 길이가 1이고 중심이 원점인 단위원에서, x축으로부터 각도가 정확히 x인 지점의 x좌표, y좌표를 각각 의미한다.

 

1,2번을 합치면 어떤 것을 얻을 수 있나면, 한번 움직일 때마다 각이 pi-2x만큼 움직이기 때문에, 결국 구하고자 하는 값은 cos(2nx-(n-1)pi)임을 알 수 있다. cos함수의 주기성에 따라 |cos(2nx)|값을 구해놓고, 부호만 판별해주면 된다는 것을 알 수 있다.

 

여기까지는 쉽게(?) 관찰할 수 있다. 여기까지 난이도는 느끼는게 좀 다를 수 있겠다.

여기서 cos(2nx)를 구하는걸 해야하는데 이게 n<=10^12기 때문에, 행렬 거듭제곱을 사용했다.

sin과 cos의 덧셈공식과 modulo처리와 inverse처리를 잘 해주면 문제를 해결할 수 있다.

 

 

 

 

 

 

B. Shortest Missing Subsequences

 

이 문제는 2가지를 구해야 한다.

1.주어진 문자열의 부분 수열로 얻을 수 없는 문자열의 최소 길이는 얼마인가?

2.문자열이 주어질 때마다, 주어진 문자열의 부분수열로 얻을 수 있는지를 판정하라.

 

1번은 그리디로 접근하면 된다.

앞에서부터 봐주면서, 사용가능한 문자를 모두 사용할때까지 뒤로 움직여 준다. 

이렇게 해주는 이유는, 우리는 만들 수 없는 부분 수열 문자열의 첫번째 글자를 선택할 건데 최대한 선택을 뒤로 미루는 것이 좋기 때문에,  모든 문자열을 다 사용할 때까지 뒤로 미루어주면 된다.

 

이런식으로 몇번 밀리는지를 판단하면 구할 수 있다.

 

2번 문제는 나는 이분탐색을 사용했다.

a~z까지 문자열의 위치를 각각 저장하고, 아까 위에서와 동일한 논리로, 현재 위치보다는 뒤면서 가장 빨리 발견되는 위치를 계속해서 찾아주면 된다.

 

쿼리로 들어오는 문자열의 최대길이가 10^6이므로 O(nlogn)에 문제가 해결된다.

 

 

 

 

 

 

 

C. XOR Island 

ㅠㅠ

문제가 정말 어렵다. 어렵다? 어렵게 생각하면 어렵다. 

이 문제의 키 포인트는 문제를 관통하는 동치조건을 생각해내는 것이다.

이게 정말 어렵고 게임이론적인 부분도 들어간다고 나는 생각한다.

 

현재 상태에서 손을 든 사람이 없는 것을 보고, 내 모자를 예측할 수 있는가?

이게 어려운게 예측의 예측의 예측을 해야한다.

즉 저 사람이 손을 안들었는데, 저 사람이 이번턴에 손을 안들었다는 것은 내가 포함되어 있다는 소린가?

이런 식의 예측을 끊임없이 해야 하기 때문이다.

 

결론적으로 말하면, 특정 수의 집합을 고른다.

예를들어 {1 2 3} 을 고른다면, 문제에서 주어진 수들 중에 1 2 3을 없앤다.

그리고 나머지 것들 중에 a^b^c=0인 서로 다른 세 원소가 존재하지 않는 경우 중에서, 집합의 최소 크기를 구하자. 

 

이 결론까지 도달하는 과정이 생략되었는데, 나도 정확하게 설명할 자신이 없다 ㅠㅠ.

 

어쨌든 저렇게 됐다고 할 떄, 문제를 이제 풀어보자.

최소 집합을 구하는 것은 bit dp를 이용하면 2^n *n 으로 풀 수 있다.

그런데, 문제는 n이 25이다. 약간 애매한데, 여기서 최적화를 조금하면, n<=23~24로 줄일수 있기는 하다.

그런데 tle가 계속 계속 나서~ 최적화하다가 포기하고 새로운 방식을 생각해봤는데, 

애초에 잘 생각해보면, a^b^c=0이 되는 쌍의 개수가 적을 수 밖에 없다.

assert해보니까 생각보다 많이 작다. 그 개수를 x라고 하면,

O(2^n * x)정도에 풀 수 있다.

 

 

 

 

 

 

 

D. Archery Accuracy

 

 

어렵다. 진짜 어렵게 풀었다.

이 문제는 수학적인 성향이 강한 문제라고 생각이 든다.

 

이제 각 선수가 점수를 얻을 확률이 중요한다. 점수를 얻으면 1점, 얻지 못하면 -1점을 얻게 된다.

그리고 각 순서마다 threshold가 존재해서, 점수의 절댓값이 그 제한에 도달해야 한다.

ex)제한이 10이면 -10이나 10점이 될때까지 그 선수가 계속해서 쏜다.

 

n<=17을 보고 bit dp를 떠올리기 까지는 쉬울 것이다.

게다가 bit dp로 하면 거의 다왔다는 착각이 드는데, 현재 켜져 있는 bit 수에 따라서, 몇 번째 순서인지 까지 정해지기 때문에 문제를 해결하기 아주 좋은 꼴이 되기 떄문이다.

 

그런데 문제가 생긴다. 

우선 조금 쉬운 문제는 dp를 어떻게 정의할 것인가 인데, 우리가 결론적으로 구하고자 하는 것은, 마지막에 양수로 끝나있을 확률을 최대화 하는 것이다.

 

게다가, 놀랍게도 각 순서마다 상태는 양수이거나 음수이거나 둘중 하나이다. 

우리는 그래서 dp[a]: a라는 bit상태에서의 양수에 멈춰있을 최대확률 로 저장할 것이다.

(이 제한이라는 것들의 절댓값이 증가함이 보장되므로 위와 같은 dp가 성립한다.)

 

자 이제 문제를 단순화 해보자.

 

현재 상태가 a이다. ex)101100과 같은 비트.

그리고 다음 제한이 b라고 하자. 

그렇다면 -b나 +b에 갈때까지 선수가 활을 계속 쏠 것이다.

 

f라는 함수를 정의하자.

f(x): 현재 위치가 x일때 +b로 끝날 확률 

 

그렇다면 다음과 같은 식들이 성립한다.

f(-b)=0

f(b)=1

(-b<i<b)f(i)=p*f{i+1)+(1-p)*f(i-1) (p는 현재 선수가 맞출 확률)

 

이제 이 식을 풀기만 하면 되는데 문제는 그래프가 dag가 아니다;;

그래서 어떻게 풀지를 잠깐 생각을 해보면, 시간 7초, s<=100이라는 제한이 눈에 들어오면서, 머릿속에 가우스 소거법이 떠오른다.

 

모든 p,그리고 n쌍에 대해 가우스 소거법을 시행하면 O(s^3*n*2)정도의 시간복잡도에 모두 구해놓을 수 있다.

그렇다면 이 값을 이용해서 dp값들을 갱신해주면 bit dp로 문제를 해결할 수 있다.

 

넘무 어렵다.

 

 

 

 

 

 

 

 

 

E. Problem Set Construction

이 문제도 확률 문제인데, D번은 좀 더 가우스 소거법에 가까웠다면, 이건 그래도 그냥 dp+확률에 가깝다.

이게 100배정도 쉬운듯 하다.

 

가장 첫 번째 단서는 s가 distinct하다는 점이다.

따라서 우선 s로 정렬한다.

그런 다음에 여기서 dp를 돌린다는 생각을 하는데, 

dp[51][51][2501]정도로 O(tn^2)정도의 시간복잡도로 해결해주면 된다.

 

dp[x][y][z]:x번째 까지 봤을때, y명 선택했을 때, 현재 시각의 총합이 z인 확률

dp 식의 전이가 꽤 쉽지가 않은데, 확률에 대해 잘 이해해주고 풀어주면 된다.

 

 

 

 

 

 

 

 

F. Rise and Fall 

 

이것도 1bin이랑 dongas가 개같이 멸망한 거 보면 0솔방지 치고 그렇게 쉽지는 않았던 거 같다.

그냥 그리디로 앞에서부터 봐서 풀어주면 된다.

 

 

 

 

 

 

G. Hopscotch 500 

cost가 제곱이 아니면 매우~웰 노운 스위핑 문제가 된다.

그런데 제곱이다.

제곱이면 항상 생각해봐야 하는게 cht로 풀 수 있을까?

라는 생각을 해보면 좋을듯 하다.

 

그래서 n^2logn정도 solution을 생각했는데, 

그냥 cht를 버리고 스위핑을 잘 해주면 dp로 o(n^3)으로 구해줄 수 있다.

dp를 푸는 방법은, 가로 세로 두 부분으로 각각 스위핑을 잘 해준후 dp식을 계속 갱신해주면 된다.

티어 대비 쉬운듯 하다.

구현난이도가 조금 반영된 듯 하다.

 

 

 

H. Reversibly Cyclic Strings

 

kmp태그가 있던데;; 뚫리는지는 잘 모르겠다.

n<=1000인데 개인적으로 5000정도가 좋지 않았을까 쉽다.

 

애드혹으로 풀리는 문제이다. 전체 문자열이 가능한지만 살펴보면 된다.

나는 개인적으로 이게 맞나..? 의문이 든채로 풀었다.

 

 

 

 

I. Reversibly Cyclic Strings

I번은 connection profile dp가 정해인거 같다.

backtracking으로 뚫려서 플레2인거 같은데,

풀기 싫어서 풀지 않았다. 나중에 dp공부를 하게 되면 풀 수도 있다.

 

 

 

 

 

 

 

 

J. Fail Them All!

 

이거 진짜 재밌는 문제였다.

아니 예전에도 그랬는데, n이 작은 2-sat문제를 자꾸 back tracking으로 내가 뚫으려고 했다;;

근데 뭔가 2-sat이 될거 같아서(한 1시간 후에 깨달았다)

열심히 고민해봤는데, 도저히 사전순이 작은 걸 구하는 방법이 생각이 안났다.

 

스타 대결이라는 문제를 풀어봤는가?

https://www.acmicpc.net/problem/1031

이 문제도, 사전순으로 제일 빠른 해를 구해야 한다.

어떻게 하는가?

그리디하게 해보고 플로우로 쿼리 날린다.

이런식으로 계속 찾아가는 것이다.

이게 왜 되냐면 플로우 자체가 n이 작기 때문에 쉽게 성립하는 것이다.

 

그런데, 이 J번 문제도 n이 100으로 작다.

그래서 매번 현재의 앞 글자를 F로 고정하고 쿼리를 날려주자.

그렇다면 시간복잡도가 O(n^4)정도에 해결이 가능하다.

 

이때 맨 앞 글자를 고정하는 방법은 어떻게 하나?

x-> y 

~x->y

이렇게 하면 y로 고정이 된다.

이 방법을 활용해서 매번 2sat 쿼리를 날리자.

 

 

 

 

 

 

 

 

 

K. Tournament Seeding

큰 쪽/ 작은 쪽 2부분으로 나누고 투 포인터로 그리디하게 선택해주면 되는 문제이다.

문제 이해가 꽤 어렵다.

 

 

 

 

L. Dorm Room Divide

 

아니;

이 문제는 왜 이분탐색으로 하면 틀리는지 모르겠다.

실수 이분탐색을 내가 잘 못하고 있는건가?

쨌든 ccw와 내분점을 잘 잡으면 된다.

 

 

 

 

 

M. Tree Hopping 

생각하기 싫어서 lca그냥 복붙했다.

거리가 3이하이므로 완전탐색으로 된다고 한다.

 

 

 

 

 

C,D는 진짜 좋은 문제 같다.

어렵기도 하다.

좋은 셋인거 같다.