JOI 2022 리뷰

 다행히도 의지를 잃지 않고 두번째 셋을 쳤다. 첫 셋보다는 비교적 열정적으로 돈 것 같긴 하다. 뭐 근데 완전히 풀집중한건 아니고 그냥 적당한 고민속도로 문제를 푼거라서 다음에는 "더 열정적으로" 칠 필요성을 느꼈다. 아무튼, 셋 리뷰나 하겠다.

 

1. intercastellar (?)

 어렵지 않다. 대충 2로 나뉠 수 있을만큼 나누고 투포인터로 처리하면 된다. 쿼리가 정렬되어있지 않았다면 구현량이 조금 늘어서 귀찮았을 것 같은데 다행히도 정렬되어있어 굉장히 짧게 코드를 짤 수 있다. 얻은 점수는 100점

 

2. self study

 전형적인 유형의 파라메트릭 서치. 처음에 a>b인 모든 것들에서 a만을 써서 최대한 해보고, 이제 남은 것들을 b만을 써서 덮어낼 수 있는지 확인하는 문제를 로그번 풀면 해결된다. 얻은 점수는 100점

 

3. Let's win the election

 본격적으로 어려워진다. 일단 내가 얻은 점수는 77점이고, 각 섭태들을 긁기 위해 사용한 관찰이 약간씩 달라 각각을 전부 서술하겠다.

 

섭태 1,2: 섭태 1의 경우엔 a가 작은것부터 합치면 된다. 섭태 2의 경우엔 지지자의 수를 전부 확인하면서, b가 가장 작은 것들을 x개 고르고 나머지 k-x개는 a가 작은 것들중 아직 선택 안한 것들을 고르는 것이 최대 이득이라는 그리디가 성립한다.

 

섭태 3,4,5,6이엇나?암튼풀태 제외 전부: 위의 관찰은 중요한 사실을 알려주는데, 만약 우리가 지지자를 섭외할 장소, 표만 얻을 장소를 특정지으면 순서는 그리디하게 자동결정할 수 있다는 사실이다. 즉, 지지자를 최대한 먼저, 그리고 비용이 적게 드는 것을 먼저라는 순서를 지키면 된다. 그럼 이를 통해 dp의 전략을 수립할 수 있는데, 첫 번째로 배열 전체를 b를 기준으로 정렬한다. 그 다음, x를 선택하고자 하는 지지자의 수라고 하겠다(답을 구할때는 모든 x를 시도해본다.). 그렇다면, 어떤 주에 대해 당신이 선택할 수 있는 것은 다음과 같다:

1. 해당 주를 무시한다.

2. 해당 주의 표만을 얻는다. 이때, a[i]/(x+1)만큼의 시간이 든다.

3. 해당 주의 지지자를 얻는다. 이때, b[i]/(현재까지 모은 지지자의 수+1)만큼의 시간이 든다.

 

즉, dp 상태를 정의하기 위해서는 탐색하고 있는 주, 현재까지 모은 지지자, 현재까지 표만 모은 주의 수 이렇게 세 요소만이 존재하면 충분하다는 사실을 알 수 있다. 당연히 시간복잡도는 각 x마다 세제곱이고, 모든 x에 대해 이를 확인하면 전체 시간복잡도는 O(n^4)정도가 된다.

섭태 6에 대해 의문을 가질 수도 있지만(그 k=n인거), 잘 생각해보면 이 경우 현재까지 표만 모은 주의 수가 지지자의 수오 탐색중인 주에 종속되는 변수이기 때문에, 제거하고 하나의 x에 대해 제곱정도의 시간복잡도에 계산 가능하다.

 

풀태: 정해의 솔루션과, 이를 응용한 나의 솔루션이 있다. 일단 정해의 아이디어를 설명하자면, 지지자를 전부 모으지 않았다면 이전에 등장했던 모든 주들의 표를 얻었어야 한다는 관찰을 사용한다. 즉, dp값이 의미를 가지는 경우는 dp[i][j][k]가 i번 주에 대해, j명의 지지자, k개의 표에 대한 최소 시간이라 할 때, j=k이거나, j=x가 성립해야 함을 의미한다. 해당 조건을 만족하는 dp 테이블의 개수는 많아야 제곱이고, 즉 하나의 x에 대해 제곱이면 확인하는데에 충분하다는 것이다. 따라서 세제곱에 풀 수 있다.

 

...그러나 나는 특유의 끔찍한 구현으로 시간초과가 났다. 그래서 나는 하나의 믿음에 근거한 최적화를 진행하였는데, 이는 x에 따른 최소 시간의 그래프가 바이토닉, 즉 삼분탐색 가능하다는 추론이다. 이걸 증명하진 않았지만, 추후에 알게된 사실로는 헝가리안 알고리즘? 암튼 뭔가 코포의 어떤 글에서 누텔라분도 특정한 과정을 통해? 비슷한 추론을 해서 문제를 풀었다는 말을 들었다. 암튼 저렇게 되면 삼분탐색을 하면 되니까 제곱로그가 되어, 문제가 풀린다. 근데 왜이리 느리지 모르겠네

 

4. Railway Trip 2

 재밌는 문제였다. 100점을 받았다. 바로 정해를 설명하겠다.

 

 우선, 핵심적으로 처리해야 하는 풀이의 내용은 다음과 같다: [l,r]의 모든 정점에서 출발하여, 2^k회만에 갈 수 있는 구간은 어디인가?

 

만약 이 연산을 처리할 수 있다면, 이분탐색을 통해서 각 쿼리를 매우 빠르게 처리할 수 있다는 사실을 알 수 있다.

 

그렇다면, 해당 연산을 어떻게 처리하는가? 2^k를 보고 눈치챌 수 있겠지만, 희소 배열을 사용한다. 우선 각 정점들에 대해 해당 정점에서 단 한번 이동해서 갈 수 있는 모든 점들이 포함된 구간을 알아낸다(무조건 이것이 구간임을 증명 가능하다.). 그 다음에 그 왼쪽 최솟값과 오른쪽 최댓값들을 세그먼트 트리에 박고, 어떤 정점에서 갈 수 있는 구간 내에 있는 모든 정점들에 대한 왼쪽 최소와 오른쪽 최대를 세그를 통해 구해서, 다음 스텝에 집어넣는다. 즉, 세그를 로그개 만든다는 뜻이다. 이렇게 하면 어떤 구간이 주어졌을 때 해당 구간에서 2^k회만에 어디까지 갈 수 있는지를 알아낼 수 있다.

 

 다만 비효율적 희소배열을 통한 이분탐색을 사용하면 시간복잡도에 O(q*log^3n)이 들어가게 되기 때문에 시간복잡도가 약간 위험해진다. 잘 최적화하면 O(q*log^2n loglogn)정도에 돌아가도록 할 수 있는데, 나는 그냥 그 중간과정 하나만 구현해서 상수만 낮추는 용도로 썼다.

 

5. Sandcastle 2

 이건 음...뭔가 위험해보이기도 하고 의지가 떨어져서 고민도 거의 안했는데 에디토리얼을 보니까 충분히 풀어볼만한 문제였던 것 같아서 약간 아쉽다. 아무튼, Radewoosh님이 코드포스에 올린 풀이를 토대로 작성한다. 나도 해당 풀이를 토대로 업솔빙했다.

 

 일단 값-좌표압축을 통해 모든 값들을 1부터 nm까지로 바꾸고, 높이가 깊이보다 작도록 바꾼다. 풀이에 있어서 가장 핵심적인 관찰은 다음과 같다:

 

 Claim) 어떤 부분직사각형의 각 원소들에 대해, diff[i][j]=a[i][j]-(부분직사각형 내에서 인접한 원소들중 a[i][j]보다 작으면서, 가장 큰 값(없으면 0))+(a보다 큰 원소가 없으면 1, 아니면 0)*(nm+1-a[i][j])라고 정의하자. 부분직사각형의 모든 diff를 전부 합쳐서 nm+1임과, 부분직사각형이 문제조건을 만족함은 필요충분조건이다.

 

 증명은 귀찮아서 생략하는데, 대충 더블카운팅과 관련된 무언가를 생각하면 해결할 수 있음을 알 수 있다. 아무튼, 이 성질을 기반으로 문제를 해결할 수 있는데, 우선 모든 가능한 끝행들의 조합을 살펴보는 경우를 생각하자. 즉, 어떤 끝행을 고정한 뒤, 그곳에서부터 시작하여 위로 시작행이 천천히 올라가는 구조이다. 물론 뒤에서 언급하는 열들은 행들에 의해 잘린 상태이다. 각 열들마다 해당 열이 왼쪽 끝인 경우의 diff의 합, 오른쪽 끝인 경우의 diff의 합, 둘 다인 경우의 diff의 합, 어느것도 아닌 경우의 diff의 합을 계산해둔다. 이제 문제는, 특정한 구간을 잘 잡아서, 해당 구간에서 정의되는 특정한 값이 nm+1인 구간의 개수를 세는 것이 된다. 이는 분할정복을 통해 해결할 수 있다. 그렇다면 이제 시간복잡도를 분석할 수 있는데, O(n^2mlogm)이 된다(분할정복을 n^2번정도 수행하기 때문). 이게 돌 수 있는 이유는, n이 sqrt(n*m)보다 작기 때문이다. 아닌가? 암튼 그냥 루트적으로 생각해보면 안될수가 없다.

 

리뷰: 역시 joi 문제는 좋은 것 같다. 유익하다고 생각한다. 그리고 조금 더 부분점수 긁기를 많이 시도해봐야겠다.