0916 Problem Solving

urd05의 추천으로 4문제 셋을 돌았습니다. 점수는 50/100/85/0입니다.

 

JOISC 2016/2017 Day 1 : Sparklers

 

50점 (서브테스크 1, 2) : 기본적으로 파라메트릭 서치를 박고 시작하는건 굉장히 자명해 보인다. 자명한 관찰을 하나 할 수 있다. 

현재 l~r까지를 소비했을 때, 다음 소비하는 것은 l-1 혹은 r+1이 될 것이다.

이를 바탕으로 DP를 정의하자. L[s][e], R[s][e]를 정의하자. 이는 s~e 구간의 모든 것을 소비했을 때 가능한 최소 위치, 최대 위치이다. DP 전이는 굉장히 간단하다. L[0][N-1], R[0][N-1]이 존재한다면 가능, 아니면 불가능이다.

시간복잡도는 O(N^2log(1e9/T))이다.

 

100점 :

 

L번째 사람부터 R번째 사람까지 하나의 구간으로써 묶이기 위해선, 모이는 시간 <= 수명 이어야 한다. 이를 수식화하면, 속도를 v, 위치를 a라 하면 (Ar - Al) / 2v <= (r-l) T가 되어야 하고, 이를 정리하면 Ar - 2rvT <= Al - 2lvt가 된다. Bi = Ai - 2ivt라 하자. [K, K]에서 시작해 저 조건을 만족하는 구간만을 지나서 [1, N]에 도달해야 한다. i = 1 ~ K 중 Bi가 최대인 i를 L1, i = K ~ N 중 Bi가 최소인 i를 R1이라 하자. 

관찰 : 만약 조건을 만족하는 경로가 존재한다면, 무조건 [L1, R1]을 거치는 경로가 존재한다. 

pf). 만약 존재한다면 L1 혹은 R1에 어느 순간 도달하게 될 텐데, 각각 최댓값, 최솟값이므로 [L1, i] -> [L1, R1], [j, R1] -> [L1, R1] 확장이 자유롭기 때문이다. 이후로도 최댓값, 최솟값 성질에 의해 확장이 자유로우므로, 쉽게 경로를 수정해줄 수 있다.

즉 다음과 같은 경로가 존재하는지 찾으면 된다 : [K, K] -> [L1, R1] -> [1, N].

또한 그리디하게 생각하면, 영역을 확장시키는 과정에서 [l, r] -> [l', r]까지 갔다고 하자. 왼쪽의 value를 a_l부터 a_l'까지의 최댓값, 오른쪽으로 밀었을 때는 최솟값으로 생각할 수 있다. 이유를 생각해보면, 이런 식으로 간주했을 때 왼쪽과 오른족의 value는 각각 단조증가, 단조감소하므로 이미 밀어버렸다고 판정한 점들은 언제든지 밀어버릴 수 있고, 이런 식으로 판정했을 때 양쪽 둘다 밀어버릴 수 없는 경우가 생기면 크기상 어떠한 방법으로도 확장 불가능하기 때문이다. 이를 선형에 해결할 수 있고, 따라서 시간복잡도는 O(Nlog(1e9/T))이다.

 

JOISC 2020/2021 Day 3 : Meeting 2

 

100점 :

간단한 관찰을 하나 하자. 답이 될 수 있는 점은 다음과 같다.

1. 자신의 위치에 점이 없을 경우, 자신의 모든 서브트리 내부의 점 개수가 동일하다.

2. 있을 경우, 자신의 모든 서브트리 내부의 점 개수가 모두 같거나 하나를 제외하고 모두 같고 그 하나는 나머지들의 개수 -1 이어야 한다.

위 관찰을 통해 다음 결과가 얻어진다.

1. j가 홀수라면 무조건 답은 1이다. 

2. j가 짝수인 경우, 담이 될 수 있는 점은 경로로써 표현되고, 그 경로의 끝 점의 서브트리 내부의 점 개수는 각각 j / 2일 때 최대이다.

우린 저 '경로'에 대해서 생각해보자. PS 장인 나x휘씨의 블로그에 따르면 그래프의 모든 경로에 대해 생각해볼 땐 센트로이드 분할이 좋다고 했으니, 센트를 쓰자. 센트로이드의 서브트리에 대해 dfs를 한 뒤 벡터에 저장하자. V[d] = 서브트리 사이즈가 d일 때 최대 깊이이다. V의 size는 최대 N/2이고 서브트리를 다 합쳐도 N이므로 size에 대해선 걱정할 필요가 없다. 대략적인 식은 ans[min(x, y)] = max( ~, 1 + V[i][x] + V[j][y]) (i != j) 꼴이 나올 것이다. 경로의 끝이 다른 서브트리에 있는 경우에 대해선, 벡터를 하나 더 만들어서 suffix max를 관리하여 스위핑해주면 된다. 경로의 끝이 센트로이드에 있는 경우에 대해선 서브트리 사이즈를 잘 관리해서 구해주면 된다.(그리 어렵지 않다.) 또한 ans[i] >= ans[i+1]이므로, 모두 구해준 뒤 한번 스위핑을 통해 propagation해준다. 이후 j가 짝수면 ans[j/2], 홀수면 1을 출력하면 된다.

 

 

JOISC 2013/2014 Day 2 : Collecting Stamps

 

85점 (서브테스크 1, 2) :

상행 -> 하행, 하행 -> 상행으로 움직이는 층을 정했다고 하자. 이는 일대일 매칭되어야 한다. 관찰을 하나 하자.

상행->하행으로 움직이는 층을 크기순으로 i1 <= i2 <= .. <= ik라고 하자. 하행 -> 상행은 j1 <= j2 <= .. <= jk라 하자. 

그리디하게 생각해보면, 최적인 매칭은 i_n과 j_n을 매칭하는 것이다. 이유를 생각해보면, 저렇게 매칭하지 않은 경우를 생각해보면 어떤 구간이 다른 구간에 포함되도록 하는 형태가 나오는데 이를 변형해도 cost의 변화는 없기 때문이다. 이 관찰을 바탕으로 DP를 정의하자. DP[i][j] : 현재 최대 도달 층이 i고, 최고 상행->하행 움직임이 i층에서 이루어졌고, 하행->상행 움직임은 j층에서 이루어졌다. 다음과 같은 식이 나온다.

D2[i][j] = min k = 0 ~ j, DP[i][k]라 할 때, 

DP[i][j] = min i2 = 1 ~ i-1, (i2 <= j일 때 D2[i2][i2-1]+T*(i-i2)+2*T*(i-j)+L[i2+1][j-1]+R->L(j)+L->R(i)+C[j+1][i-1],

i2 > j일 때 D2[i2][j-1]+T(i-i2)+2*T*(i-j)+R->L(j)+L->R(i)+C[i2+1][i-1])

또한 전에 j에서 움직였거나, i에서 움직이는 것도 고려해줘야 한다. 이를 그대로 짜면 O(N^3)으로 85점을 긁을 수 있다.(실제론 이 서브테스크 데이터가 굉장히 약해 케이스를 몇개 고려 안해도 긁어진다. 문제 세팅 이렇게 하면 안 된다.)

 

100점 :

앞에서 j에 의존하는 부분을 분리해서 prefix min 등을 이용해 잘 관리해주면 O(N^2)에 구할 수 있다.

 

 

JOISC 2020/2021 Day 3 Bodyguard :

 

추가예정입니다.