2023 ICPC Seoul Regional

이 문제를 먼저 풀고 오자. 정해를 꼭 알아보자.

편의상 \(s=1\), \(e=n\)이라고 하자. 쿼리의 답은 \(Ans(s, e, m, 1, r) - Ans(s, e, m, 1, l-1)\)로 구해낼 수 있음을 관찰하자. \(l = 1\)이라면 문제를 어떻게 풀 수 있을까?

본 대회에서는 \(0\)솔이었던 문제이고, 난이도 커브도 셋에서 가장 어려운 문제 중 하나로 의도되었을 법하다. Bubble sort의 성질 중 하나로, 주어진 배열 \(A\)에서 \(k\)번 pass를 진행했을 때의 배열 상태는 다음과 같은 과정으로 구할 수 있음이 알려져 있다:

1. Priority queue (PQ)에 \(A_1\), \(A_2\), \(\cdots\), \(A_{k-1}\)을 insert한다.
2. 이후 \(n-k+1\)번 동안 새로운 원소를 PQ에 넣고, 최소 원소를 하나 제거하는 과정을 반복한다.
3. PQ에 원소가 남아있지 않을 때까지 최소 원소를 제거한다. 이 때 여태까지 PQ에서 제거한 원소들을 순서대로 나열한 것이 곧 배열의 최종 상태이다.

편의상 \(s=1\), \(e=n\)이라고 가정하자. Hint 2에 따르면 \(l=1\)만 고려해도 된다. 이 과정으로 pass를 \(m\)번 진행했을 때 배열의 변화를 naive한 \(O(nm)\)에서 \(O(n \log m)\)로 개선시켰으나, 쿼리를 처리하기에는 아직 부족하다. 기본적으로 위의 관찰은 \(m\)번 pass를 진행한 이후의 상태를 완벽하게 구해내는데, 문제에서 필요한 것은 어떤 구간의 합이므로, 합만 빠르게 계산해낼 방법이 없을지 생각해보는 것이 자연스럽다.

먼저 \(r+m \leq n\)이라고 하면, \(A_r\)은 PQ에 \(A_{r+m}\)까지 insert한 시점에 빠져나오는 원소가 된다. 즉, 이 시점에 최종 상태에서의 \(A_1\), \(\cdots\), \(A_r\)과 PQ에 들어있는 원소를 모으면 초기 배열의 \(A_1\), \(\cdots\), \(A_{r+m}\)를 모은 집합과 같다. 이 때 PQ에 남아 있는 원소는 \(A_1\), \(\cdots\), \(A_{r+m}\)들 중 가장 큰 \(m\)개의 원소라는 것이 주요한 관찰이다. 증명은 귀류법. 제일 큰 \(m\)개의 원소가 PQ에 들어온 이후 빠지려면 어떤 \(m+1\)개 수 중 최소인 시점이 존재해야 하는데, \(A_r\)까지만 확정한 상태이므로 그것이 불가능. 또한 \(r+m > n\)이면, PQ에 남아 있는 원소는 전체 배열 중에서 가장 큰 원소 몇 개이다.

그러므로 이 문제는 다음 쿼리를 빠르게 처리할 수 있다면 해결된다: \((s, e, k)\)에 대해, \(A[s,e]\) 부분수열에서 가장 작은 원소 \(k\)개의 합을 구하라. 시각적으로 상황을 생각해보면, 모든 \(A_i\)를 좌표평면 상에 \((i, ord_i)\) 점으로 표현하는데, 여기서 \(ord_i\)는 \(A_i\)번째 원소가 \(A\)들 중에서 몇 번째로 작은 원소인지 나타내는 값이다. 그러면 \((s, e, k)\) 쿼리는 직사각형 \([s, e] \times [1, y]\) 내에 존재하는 점의 개수가 \(k\)개 이상인 최소의 \(y\)를 찾는 문제로 변한다. 그 때 쿼리의 답은 그 직사각형 내에 속한 점들에 대응되는 \(A\) 배열 원소의 값들의 합이다.

여기서 \(s, e\)도 쿼리로 들어오는 값이므로, 위의 상황을 persistent하게 관리할 수 있다면 좋겠다는 motivation을 얻을 수 있다. 그러므로 구간 합을 관리하는 persistent segment tree를 생각해보자. 잠깐만 \(s=1\)이라고 가정하자. 위의 시각화에서, \(x\)축이 일종의 '시간축'이고, \(y\)축은 구간 합 세그의 index를 나타낸다고 하자. 즉, \(e\)번째 세그에서 구간 \([l, r]\)에 관리되는 값은 \([1, e] \times [l, r]\) 직사각형 내의 점의 개수와, 그 점에 대응되는 \(A\) 원소의 합이다. \(y\)는 기본적으로 binary search로 빠르게 알아낼 수 있는 변수이며, \(e\)번째 세그 위에서 walking 테크닉을 써서 \(O(\log n)\)에 알아낼 수 있다. 동시에 우리가 궁금한 값인 각 점에 대응되는 \(A\) 원소의 합도 이 과정에서 동시에 알아낼 수 있다. 그럼 \(s\not=1\)일 때는? Walking을 \(s-1\)번째 세그와 \(e\)번째 세그 위에서 동시에 진행하면 된다. 이해가 안 간다면 아래 코드를 참고해봐도 좋을 듯하다. 시간복잡도는 \(O(n+q) \log n)\).

버블 정렬의 이러한 분석을 활용하는 문제는 하나가 더 있다. 꽤 자주 나오는 아이디어 같고, 재밌다.

당황하지 말자.

주어진 코드를 해석하면, 처음에 빈 배열이 주어져 있을 때 다음의 쿼리를 \(n\)번 처리하는 것으로 바뀐다. \((idx, val)\): \(val\)을 \(idx\) 위치에 삽입한다. 최종 상태를 출력하면 된다.

이 문제의 철학은 뭘까? 모르겠다. Hint 2에 요약된 문제에 대한 해설만 하겠다. 거꾸로 생각해보자. 마지막 쿼리는 삽입한 이후에 그 원소의 위치가 변할 일이 없으므로, 최종 상태에서 그 원소의 위치를 쿼리만 보고 바로 확정할 수 있다. 이러한 관찰에 힘입어, 쿼리를 거꾸로 처리할 수 없을까? 즉, 몇 개의 원소의 '최종 상태에서의 위치'가 이미 정해져 있을 때, 쿼리 \((p, v)\)를 처리하여 \(v\)의 최종 위치 \(p' \geq p\)를 알아낼 수 있을까? (insertion 과정에서 모든 원소의 index는 정의상 단조증가)

최중 위치가 \(p'\)이라고 가정하자. 이것이 의미하는 바는 두 가지이다. 먼저, \((p, v)\) 이후의 모든 쿼리를 처리하면 \(v\) 앞에 원소가 삽입되는 횟수가 \(p'-p\)번 존재했어야 한다. 두 번째로, \(v\)의 index가 증가하는 횟수는 (거꾸로 봤을 때) 현재 최종 위치를 알고 있는 원소들 중 \(p'\)보다 작은 위치에 놓인 원소의 개수와 동일하다는 것이다. 이 사실은 간단하게 보여진다. \(p'\)보다 작은 위치에 놓이게 될 원소가 \(v\)의 index를 밀지 않았다고 가정하면, \(v\)의 오른쪽에 insert되었다는 뜻이고, 두 원소의 상대적인 위치는 아무리 insert가 더 진행되어도 변하지 않으므로 모순.

그러므로 \(f(p')\)을 \(p'-p\)에서 위치가 결정된 원소들 중 그 위치가 \(p'\) 미만인 것의 개수를 뺀 값으로 정의하자. \(p'\)이 \(1\) 증가할 때 앞의 항은 무조건 \(1\) 증가하나, 뒤쪽 항은 \(0\) 혹은 \(1\)이 증가하므로 \(f\)는 단조증가 함수이다. 위의 논의로부터, 우리는 \(f(p')=0\)인 위치가 올바른 \(p'\)이라는 것을 알고 있다. 따라서 이를 binary search로 찾아주면 된다! \(f(p')=0\)인 \(p'\)이 하나가 아닐 수도 있는데, 이미 최종 위치로 점유된 위치를 또 \(p'\)으로 선택하는 것은 불가능하므로, 이 조건까지 고려하면 항상 하나로 결정된다. 증명은 그냥 \(f\)의 단조성 증명을 잘 생각해보면 알 수 있고, 구현적으로는 그러한 \(p'\) 중 최대인 것을 선택해주면 된다고만 첨언한다.

\(y\)좌표가 가장 큰 점을 포함하는 직사각형이 어떻게 생겼어야 할까?

주어진 Farm을 '영역'이라고 하자. 입력으로 주어지는 점 \(n\)개를 정점으로 하는 그래프 \(G\)를 생각하자. \(i\)와 \(j\)가 간선으로 이어져 있을 필요충분조건은 \(i\)번 점과 \(j\)번 점을 동시에 덮으면서 영역 내에 완전히 포함되는 직사각형이 없는 것이다. 즉 \(G\)에서 간선으로 연결된 두 정점은 무조건 임의의 해에서 서로 다른 직사각형에 덮여 있어야 한다. 따라서 이론적으로 \(G\)의 coloring 문제를 풀 수 있다면 이 문제를 풀 수 있다.

다만 실제로 이는 매우 어려운 문제이고, 다음 과정을 반복하면 올바른 최적 채색 방법을 얻어낼 수 있음을 보이겠다:

1. 점들을 \(y\)좌표가 큰 순으로 본다. 초기에는 아무 직사각형도 그려져 있지 않다.
2. 점의 위치가 \((x, y)\)라고 하자. 이 점이 현재 어떤 직사각형으로 덮여 있다면 무시하고 다음으로 넘어간다. 덮여 있지 않다면, 그 점으로부터 양쪽으로 \(x\)축과 평행한 반직선을 영역 경계와 충돌할 때까지 연장하여 그린다. 그 선분이 \([l, r]\) 범위가 되었다면, 새로운 직사각형 \([l, r] \times [0, y]\)를 영역에 그린다. 이 직사각형은 이미 그려져 있을 수 있는 다른 직사각형보다 우선한다: 다른 영역과 겹친다면 미리 그려진 영역을 무시하고, 그 영역이 축소되는 것으로 생각한다.

이 과정 도중에 새로운 직사각형을 그리게 되는 점들이 순서대로 \(P_1\), \(\cdots\), \(P_t\)로 총 \(t\)개라고 하자. 이 때 임의의 \(1 \leq i < j \leq t\)에 대해 \(P_i\)와 \(P_j\)는 \(G\)에서 무조건 인접해있다. 왜냐하면 \(P_i\)를 볼 때 새로 그려지는 직사각형은 \(P_i\)를 포함하는 최대 폭의 직사각형이기 때문이다. \(P_j\)의 \(y\)좌표는 \(P_i\)의 그것 이하이므로, 이 직사각형에 \(P_j\)가 포함되지 않음과 \(G\)에서 두 점이 인접함이 동치임을 쉽게 확인할 수 있다. 그러므로 \(G\)는 그 subgraph로 \(K_t\)를 포함하고 있으며, 따라서 \(\Delta(G) \geq t\)이다. 또한 이 greedy procedure가 정확히 \(t\)개의 직사각형으로 모든 점을 덮는 해를 제공하게 되므로, 최적해를 찾은 것이다. 그러므로 위의 과정을 set 등의 자료구조로 빠르게 시뮬레이션해주면 ok.

• 위의 '직사각형 그리기' 방법을 생각해보면 \(\overline{G}\)는 interval graph가 되는 듯하다. Coloring problem을 풀기 쉬운 이유가 여기에서 기인하는 것일까?

• 개인적으로 이 문제는 풀이를 먼저 믿음으로 짜고, 포스트를 쓸 때가 되어서야 증명을 찾았다. 이 증명을 찾는데는 이 문제가 살짝의 기여를 했는데... 연관이 있나?

열심히 문자들을 입력받아서 파싱해준다... 말고는 할 말이 없다. 입력 조건을 만족하는 데이터 중, 계산 과정에서 통상적인 \(64\)-bit 변수 범위를 넘어가는 데이터를 만드는 것도 가능한데, 서울 리저널이니만큼 지문의 output section에 써 있는 코멘트를 믿고 믿음으로 짜도록 하자.

그냥 해싱을 써서 문자열 equality 판정을 하는 것이 편하긴 하다. 길이 \(k\)짜리 수열의 relative order 정보는 결국 크기 \(k\)의 permutation이고, 이것도 그 자체로 수열 (문자열)로 해석할 수 있으므로, rolling hash를 적용하면 permutation \(\pi = (\pi_1, \ldots, \pi_k)\)의 hash 값은 \(\sum_{i=1}^{k} \pi_i B^{k-i}\)로 정의하도록 하자.

그러므로 이 문제에서 필요한 작업은, 어떤 수열의 오른쪽 끝에 새로운 수가 추가될 때, 왼쪽 끝의 수를 제거할 때 hash 값의 변화를 관리하는 것이다. 제거는 추가와 비슷하니, 추가만 생각해보자. 수열 \((a_1, \ldots, a_k)\)의 relative order가 \((\pi_1, \ldots, \pi_k)\)에서 \((\pi'_1, \ldots, \pi'_{k+1})\)로 변화하면, hash 값의 변화는 두 개로 연속해서 생각할 수 있다. 기존 hash 값에 \(B\)를 곱한 후, \(\pi'_i = \pi_i + 1\)가 된 \(i\)들에 대해 \(B^{k+1-i}\)를 추가로 hash 값에 더해주는 것이다. 이 작업은 \(i = k+1\)에서만 예외인데, \(\pi'_{k+1}\)은 없다가 새로 생겨나는 값이기 때문이다. 먼저 \(B^{k+1-i}\)들의 합을 어떻게 구할 수 있을까? 이것은 \(a_i\) 값을 index로 사용하는 구간 합 segment tree (혹은 fenwick tree)를 관리함으로서 해결된다. 그 index에 \(B^{k+1-i}\)를 저장해두고, \(\pi'_i\)가 \(\pi_i\)에 비해서 증가하는 \(i\)들은 모두 \(a_i < a_{k+1}\) 조건을 만족함과 동치임을 확인할 수 있으므로, 우리가 필요한 값이 이 세그에서 어떤 구간의 합으로 표현됨을 확인할 수 있다. 또한 \(\pi'_{k+1}\) 값도 필요한데, 이건 위의 세그에서 \(a_i < a_{k+1}\)인 \(i\)의 개수와 같으므로, 각 index에 \(1\)을 저장해뒀다면 정확히 같은 원리로 구할 수 있다.

여기서 \(B^{k+1-i}\)를 저장하는 방법이 살짝 애매할 수 있다. 왜냐하면 수의 추가와 제거를 거치면 \(a_i\)의 수열 내에서의 상대적인 위치는 점점 \(1\)씩 감소하므로, 이 계수가 달라지기 때문이다. 가장 단순한 방법은 구간 곱 update까지 지원하도록 lazy segment tree를 활용하는 것이겠으나, 나는 이걸 짰더니 TLE를 받았다. 아이디어는, 입력으로 주어지는 배열 \(A\)에 대해서 \(A_i\)에 곱해지는 계수가 고정적으로 \(B^{N-i}\)라고 가정하는 것이다. 그러면 내가 위의 방식대로 hash를 구하면, 중간 시점에 필요한 길이 \(K\)짜리 작은 수열의 hash는 어떤 정수 \(t\)에 대해 \(B^{-t}\)를 곱해서 얻어낼 수 있다. 이러면 lazy update가 필요가 없다. 무슨 뜻인지 모르겠다면, 아래 내 코드에서는 L94에서 real_hsh라고 정의한 변수가 이와 관련된 로직을 담당하고 있으니 참고.

Relative order에 대한 문자열 매칭은 꽤 오래된 떡밥이다. 이 문제, 이 문제, SCPC에서도 나온 것으로 기억하고 있고, 21' Seoul에서도 출제된 적이 있다! Cartesian Tree Matching이라고도 부르는 것 같다. 기본적으로 relative order가 같다는 것을 두 수열이 matching된다라고 정의하게 되면, 이는 equivalence class를 만들기 때문에, failure function을 정의해서 KMP를 수행할 수 있듯이 정확히 같은 원리로 이 문제 세팅에서의 매칭도 가능함을 직관적으로 받아들일 수 있다. 또한 이는 aho-corasick의 원리를 적용하여 multiple pattern도 찾아낼 수 있음을 암시한다. 결론은, 실제로 그렇게 짤 수 있다는 것이다. Open contest에서는 실제로 그러한 솔루션이 나왔던 것으로 기억한다. 굳이 더 알아보고 싶지는 않으니 생략.

임의의 최적해에서 Draw를 뽑는 위치를 특정한 위치로 제한할 수 있다. 어디일까?

우선 문제를 \(O(kn^2)\)에 해결하는 방법을 생각해보자.

\(n\)개의 구간이 수직선 상에 그려져 있고, \(K\)개의 위치를 선택하여 최대한 많은 구간이 선택되게 하는 문제이다. 우선적으로 할 관찰은, 선택하는 위치는 전부 구간의 오른쪽 끝들로만 제한해도 ok라는 점이다. 그렇지 않은 최적해를 하나 생각했을 때, 어떤 구간의 오른쪽 끝이 아닌 지점을 선택했다면, 이를 오른쪽으로 쭉 당기자. 어떤 구간의 오른쪽 끝에 닿는 순간 멈춘다고 생각하면, 새로운 구간의 왼쪽 끝으로 진입하게 될지언정, 최소한 겹치는 구간의 개수가 줄어들진 않는다. 이건 꽤 직관적이니 이 정도로 설명을 줄인다.

선택의 가짓수를 유한한 개수로 제한했으므로, DP를 생각해보자. 가장 자명한 dp는 다음과 같다. 구간들의 오른쪽 끝들을 모아서 \(x_1 \leq \ldots \leq x_n\)라고 두자. dp[k][i]를 \(x_i\)를 '마지막으로' 선택한 것을 포함하여 앞에서 총 \(k\)개의 위치를 선택했을 때, 최대로 선택할 수 있는 구간의 개수로 정의하자. 즉 위치 선택을 왼쪽에서 오른쪽으로 해 나가는 dp이다. 이 경우, 다음의 cost[a][b]를 정의하면 dp 전이식도 완성할 수 있다. cost[a][b]를 어떤 구간이 \([l, r]\)일 때, \(x_a < l\)이고 \(r \leq x_b\)를 만족하는 구간의 개수이다. 그러므로 전이식은, $$ dp[k][i] = \max_{k-1 \leq j \leq i-1} (dp[k-1][j] + cost[j][i]). $$

이 dp를 깡으로 계산하려면 \(O(kn^2)\)이 걸린다. 여기서의 핵심 관찰은, \(-cost[][]\)가 monge array라는 것이다 (부호에 주의). 따라서 Divide and Conquer DP optimization의 \(2\)번 항목을 참고하라. Monge array인 것에 대한 증명은, 시각화로 간단하게 해결된다. 구간 \(n\)개를 좌표평면에 점으로 표현하는데, 구간이 \([l, r]\)이면 \((l, r)\)로 표기하는 식이다. 이렇게 되면, cost[a][b]는 \([x_a+1, x_b] \times [x_b, INF]\) 직사각형 영역 내에 존재하는 점의 개수가 된다. Monge array의 정의를 따라 \(4\)개의 직사각형 영역을 그려 보면 손쉽게 증명 가능.

따라서 남은 과정은 cost[][] 배열을 계산하는 과정인데, 위의 시각화를 그대로 가져오자. \(r=n..1\)에 대해, cost[*][r]을 한 번에 전부 계산할 것이다. 점 (구간)을 \(r\)이 감소하는 방향으로 추가한다고 생각하면, 좌표평면에서 \(y\)좌표가 감소하는 방향으로 점을 sweeping하면서 cost[][]를 계산할 수 있음을 알 수 있다. 잘 모르겠다면 코드의 L58-L73 부분을 참고.

거의 비슷하지만 살짝 더 어려운 문제로는 이것이 있다.

모든 수 \(1 \leq x \leq N\)에 대해, 각 수가 \(K\)개의 카드에 포함되어 있는지 여부를 나타낸 길이 \(K\)의 이진 문자열 \(S_x\)를 전부 \(O(K(M+N))\) 시간에 만들 수 있음이 자명하다. 이제 쿼리로 들어오는 문자열을 위의 \(K\)개의 문자열들 중에서 찾아주면 된다. 이것을 쉽게 하기 위해, set이나 map에 넣고 있든, vector에 넣고 정렬해서 binary search를 하든 알아서 하면 된다. 카드가 없는 경우, 중복된 경우에도 답이 NO이다.

어떤 열이 두 행 모두에서 MSIS에 포함되는 것은 아니라고 하자. 이 열은 최적해에 어떻게 영향을 주는가?

핵심적인 관찰은 어떤 열이 두 행 모두에서 MSIS에 포함되지 않을 때, 최소한 이 열에서 둘 중 큰 수는 반드시 최적해에 기여할 수 있게 만들 수 있다. MSIS에 두 행이 모두 포함되는 열들을 모은 다음에, 그렇지 않은 열들을 적절한 위치에 하나씩 끼워넣는 것이다. 이 끼워넣는 작업에서 고려할 행이 하나밖에 없기 때문에 항상 가능하다. 이는 그러한 열에서 얻을 수 있는 점수의 최대치를 항상 얻을 수 있음과 동치이므로, 이들은 다른 열들과 완전히 독립적으로 취급할 수 있다.

두 행이 모두 MSIS에 포함되는 열들만 모으면, LIS를 구하는 상황과 거의 유사함을 알 수 있다. 이 정도까지만 생각해도 dp를 만들기에 충분하다. 한 쪽 행을 기준으로 열들을 정렬해두자. 이렇게 했을 때 열들에 쓰인 수가 \((a_i, b_i)\)이고 \(a_1 \leq \ldots \leq a_n\)이라고 하자.\(dp[i]\)를 정의하는데, 이는 \(i\)번째 열을 MSIS에 두 행이 전부 포함되는 열로 선택했을 때, \(1\)번째부터 \(i\)번째 열들로 구성 가능한 최댓값이다. 그러므로 dp[] 전이식은 꽤 단순하다: $$ dp[i] = \min_{0 \leq j < i, b[j]<b[i]} dp[j] + \sum_{k=j+1}^{i-1} \max(a_k, b_k) + (a_i + b_i). $$

\(dp[n]\)이 곧바로 문제의 답은 아닐 수 있음을 유의하자. 시간복잡도는 \(O(n^2)\)이다.

모든 \(1 \leq i \leq n\)에 대해 \(l_i = m_i\)인 상황에서는 문제를 어떻게 풀 수 있을까?

모든 \(l_i = m_i\)일 때부터 생각해보자. Difference array \(d_i = l_{i+1}-l_i\)를 생각해보자. 한 번 product를 배달하는 과정은, \(d\) 배열에서 연속한 구간을 골라 구간에 포함되는 칸의 값을 임의로 \(0\) 이상의 값을 뺄 수 있는 것과 같다. 단 product가 배달되는 마지막 지점에 대해서는 \(d\) 배열의 값이 반대로 증가하며, 그 지점이 \(n\)번째 칸이라면 이 과정은 생략된다. (특히 그 증가분은 앞의 구간에서 내가 뺀 값의 합이지만, 이건 문제풀이에 중요하진 않다) 중요한 것은, 내가 한 번 product를 배달할 때 \(d\)에 음수 값이 써 있다면 이를 최대 \(1\)개까지만 \(0\) 이상으로 만들 수 있다는 것이다. Product를 전부 올바르게 배달했다면 \(d\) 배열의 값이 전부 \(0\)이 된다는 뜻이므로, 최소한 초기 \(d\) 배열의 음수 개수만큼은 배달이 필요하다. 또한, 정확히 그 횟수만큼만 product를 배달할 수 있다. 방법은 맨 뒤부터, \(l_k \leq \ldots \leq l_{n-1} \leq l_n\)이 되는 최소의 \(k\)를 찾은 다음 \(k\)번째 지점부터 \(n\)번째 지점에 product를 배달하는 과정을 반복한다. 이러면 정확히 초기 \(d\) 배열에서 음수인 지점을 기준으로 그 앞뒤는 한꺼번에 product가 배달되게 된다.

그렇다면 본 문제를 어떻게 풀 수 있을까? 우선, 위의 greedy 과정을 직관적으로 이해해야 한다. \(n\)번째 지점은 받을 수 있는 만큼 product를 받아놓는 게 좋다. Capacity가 증가한다고 해서 product를 배달 못 할 일은 없기 때문이다. 그 다음으로, \(l_{n-1} \leq m_n \leq m_{n-1}\)이라고 가정하자. 이러면 \(n-1\)번째 지점에서도 최대한 많이 받되, \(n\)번째 지점보다는 많이 받지 않을 수 있는 \(m_n\)만큼을 받는 것이 좋다. \(m_{n-1} < m_n\)이라면 \(m_{n-1}\)개를 받아 가능한 한 최대로 받으며, 반대로 \(m_n < l_{n-1}\)이면 어떻게 해도 product를 배달하는 횟수가 한 번 더 필요하므로, 이제 이 뒤쪽은 무시해도 되며, 다시 가능한 최대인 \(m_{n-1}\)을 배달받는 것이 좋다. 즉, 정리하자면 모든 지점이 받을 product의 개수를 거꾸로 결정해나간다. 현재 지점이 받는 product 개수는 바로 앞 지점 이하로 받으면서, 낮춰야 한다면 최대한 덜 낮추고, 어떻게 해도 뒤 지점보다 product를 많이 받아야 한다면 아예 받을 수 있는 최대로 받아 버린다.

이 전략이 최적인 이유는, 어떤 최적해에서 뒤쪽 지점 이하로 받을 수 있는데도 그러지 않고 뒤쪽 지점 초과로 product를 받아버린 경우, 이 '횟수'를 아껴서 더 앞쪽에서 이러한 사태가 발생할 때 이 '아낀 횟수'를 써 버러는 것이 항상 더 좋기 때문이다. 이 '횟수'를 쓰게 되면, 그 즉시 횟수를 사용한 지점에서 받을 수 있는 최대 product를 받을 수 있기 때문. 너무 대충 서술했는데, 애초에 이 셋에서 \(2\)~\(3\)번째로 쉬운 위치의 문제였던 만큼 그냥 이 정도로 마친다. (사실 그리디 문제들은 풀이 쓰기가 너무 어렵다)

\(L=1\)일 때만 문제를 풀 수 있어도 된다.

\(L=1\)이고, 어떤 음이 아닌 정수 \(t\)에 대해 \(R=10^t-1\)라고 하자. 어떻게 문제를 풀 수 있을까?

\(L\)과 \(R\)이 \(10^{20}\)이라는 특이한 제한을 가지고 있으나, 이건 사실 길이 \(20\)짜리 문자열을 준 것과 거의 비슷한 상황이다. 보통 이러한 유형의 dp를 Digit DP라고 부르는 것 같다. 그러므로 꽤나 기계적으로 문제풀이를 진행할 수 있다. \(dp[k][n][lz]\)라는 dp를 정의하자. \([0, n]\) 범위의 정수 중 \(k\)-special인 것의 개수를 의미하되, \(lz\)가 true이면 이 범위 내의 모든 수를 \(n\)의 \(10\)진 길이로 leading zero를 붙여서 연장한 수들로 \(k\)-special 판정을 할 것이며, false라면 일반적인 정수 표현으로 판정을 진행한다. 또한 \(lz\)가 false이면 \(0\)은 임의의 \(k\)에 대해 \(k\)-special에 포함되지 않는 셈칠 것이다.

전이식을 고려하자. 먼저 \(dp[k][n][0]\)을 생각한다. \(n\)이 주어지면, \(n\)의 맨 앞 자리(most significant)를 생각하자. 이 값이 \(x\)일 때, 맨 앞 자리를 \(1 \leq y < x\)로 하는 수는, 그 뒤의 \(len(n)-1\)개의 수로 가능한 값이 \(00 \ldots 0\)부터 \(99 \ldots 9\)가 전부 가능하므로, 남은 자릿수를 올바르게 채우는 방법은 \(dp[k / \gcd(k, y)][10^{len(n)-1}-1][1]\)이다. 맨 앞 자리가 \(x\)와 같으면, 위와 비슷하지만 고려해야 하는 수 범위 제한이 \(n\)의 맨 앞 자리를 제외한 수로 바뀐다. 즉 \(n = \overline{xn'}\)으로 두면, 경우의 수는 \(dp[k / \gcd(k, x)][n'][1]\)이 된다. \(dp[k][n][1]\)도 다를 것은 없다. 위의 표기법을 가져오면, \(y = 0\)일 수도 있다는 것이 차이점이다.

그러므로 모든 parameter들을 key로 갖는 map을 선언하여 메모이제이션을 해 주면 문제를 빠르게 해결할 수 있다. 이러면 상태가 종국에 너무 많아져서 시간 안에 돌지 않는 것이 아닌가 할 수 있는데, 사실 상태가 얼마 안 생긴다. 먼저 \(k\)를 생각하면, 앞으로 발생하는 모든 \(k\)는 입력으로 주어지는 \(k_0\)의 약수뿐이며, 또한 소인수분해를 생각하면 \(2, 3, 5, 7\)의 지수부만 변하는 것이 전부이다. 항상 \(x\), \(y\)는 \(9\) 이하의 음이 아닌 정수이기 때문이다. 또한 \(n\)에 들어가는 입력도 가능한 경우의 수가 얼마 없다. \(y < x\)라면 항상 다음 상태가 \(10^t - 1\) 꼴만 가능하며, \(y=x\) 방향 전이는 입력으로 주어진 \(R\)의 자릿수를 맨 앞에서 몇 개 자른 것밖에 없기 때문이다. 따라서 제법 빠르게 작동할 것으로 예상할 수 있다. 최종 답은, \(dp[k][R][0]-dp[k][L-1][0]\)이다.

문제에서 주어진 목표 문자열을 \(t = t_1 t_2 \ldots t_m\), 시작 문자열을 \(s = s_1 s_2 \ldots s_n\)이라고 하자. 어떤 문자열 \(A\)를 문제에서 정의된 두 가지 copy operation으로 \(B\)를 포함하는 문자열로 만들 수 있다면, \(A\)를 substring (consecutive)으로 갖는 모든 문자열 \(A'\)로 \(B\)를 포함하도록 만들 수 있다. 따라서 다음 dp 정의가 well-defined이다: \(dp[i][j][0/1]\)는 \(s_k \ldots s_i\)에서 \(s_i\)를 최소한 한 번은 활용하여 \(t_1 \ldots t_j\)를 만들 수 있는 최대의 \(k\)로 정의한다. 이 때 \(s[k..i]\)로 \(t[1..j]\)를 포함하는 문자열이 만들어졌을 때, 마지막 글자가 \(s_{i-1}\)이면 세 번째 인자가 \(0\)이고, \(s_i\)이면 \(1\)이다. 또한 초깃값은 \(dp[i][0][*] = i\)로 정의한다.

\(dp[i][j][*]\)의 전이식을 생각해보자. \(s[k..i]\)로 \(t[1..j]\)를 만들었다고 하면, 이들을 어떤 방식으로 copy를 했든지 간에, 모든 \(s_{i-2}\)는 임의의 \(s_i\)보다 왼쪽에 나타난다. Copy가 인접한 문자들 간에만 일어나기 때문에, 모든 \(s_{i-2}\)는 오른쪽에서 최소한 하나의 \(s_{i-1}\)이 위치하고, 반대로 \(s_i\)는 최소한 하나의 \(s_{i-1}\)이 왼쪽에 위치하게 되기 때문이다. 따라서 \(s_i\)도 \(t[1..j]\) 중 어딘가에 대응시켜야 한다는 조건까지 고려하면, \(t_j\)에 대응시킬 문자는 \(s_{i-1}\)나 \(s_i\)뿐이며, 이것이 dp의 세 번째 인자가 binary value로 설정된 이유이다. Copy 이후 \(s_i\)로 문자열이 끝난다고 하면, 가능성이 \(3\)가지이다.

1. \(s_i\)가 전혀 복사되지 않음. 이 경우 \(s_i = t_j\)이여야만 하며, 그러므로 \(dp[i][j][0]\)은 이 케이스를 고려하면 안 된다. 남은 subproblem은 \(dp[i-1][j-1][1]\)이 된다. \(s_{i-2}\)와 \(s_i\)가 인접할 일은 없으므로 마지막 인자가 \(1\)만 가능하다.
2. \(s_i\)가 한 글자 복사로만 복사됨. 복사한 이후 복사한 글자를 사용하지 않으면 위 케이스와 다를 것이 없으므로, 역시나 \(dp[i][j][0]\)은 이러한 케이스도 고려하면 안 되며, 남은 subproblem은 \(dp[i][j-1][1]\)이 된다. \(s_i = t_j\) 조건도 잊지 말 것.
3. \(s_i\)가 \(s_{i-1}\)와 함께 복사된 적이 있음. \(s_i\)를 한 번은 활용해야 하므로 복사된 \(s_{i-1}\)을 \(t_j\)와 매칭시킬 때 사용해야 하며, 그러므로 \(s_{i-1} = t_j\)여야 한다. \(dp[i][j][0]\)의 경우 남는 subproblem은 \(dp[i][j-1][*]\). Subproblem에서는 \(s_i\)로 끝나건 \(s_{i-1}\)로 끝나건 다 ok임을 유의하자. \(dp[i][j][1]\)의 경우는? \(s_i\)를 복사해서 유의미한 이득을 보려면 복사된 문자를 사용해야 하므로, \(s_i = t_j\)를 서로 매칭시킨 경우이다. 이 경우에도, subproblem은 무슨 문자로 끝나든 다 ok. 따라서 남는 subproblem은 \(dp[i][j-1][*]\). 또한 \(3\)번 케이스는 사소하지만 중요한 조건이 하나 더 필요하다. 복사를 했다는 것은, \(s_{i-1}\)를 활용했다는 뜻이다. 따라서 \(dp[i][j][*] \leq i-1\).

최종적으로 답을 구하려면, \(dp[i][m][*]\) 중 유효한 값이 하나라도 있는 경우, 그 \(dp\) 값 중 큰 값을 \(M_i\)라고 하면, \(s[M_i, i]\)는 일종의 minimal한 valid substring이다. 이러한 minimal valid substring들을 전부 구해주면, 임의의 \(1 \leq r \leq n\)에 대해, \(s[k_r..r]\)이 valid한 \(k_r\)을 전부 얻어줄 수 있다. 잘 이해가 안 간다면, 코드의 L29-L30 참조. 또한 이 코드는 toggling으로 메모리를 줄였고, dp 배열도 cache hit를 고려하여 순서를 정했다. 본 대회에서는 별 영향이 없었겠으나, BOJ에서는 이를 고려하는 게 유의미한 영향을 준다.

구현이 매우 짧지만 생각하기 나름 까다롭다는 점에서, 멋진 문제라고 생각한다. Greedy 풀이도 있다고 들었다. 시간복잡도가 더 작은지는 모르겠다. 위의 풀이에서 언급했듯이, 시작 문자열에서 '인접한 문자가 같지 않다'는 조건을 쓰지 않았으니, 이 조건을 활용한 풀이가 있을 것임을 추정할 수 있고, dp 풀이를 생각해보면 뭔가 그리디 비슷한 게 될 법하다는 인상을 받기에는 충분한 것 같다.

그리고 이 문제는 데이터가 유독 약한 것 같다. 일단 나는 셀프 저격을 하는데도 성공했고, 이 풀이는 그걸 고친 풀이이다. 또 틀린 건 아니라면 좋겠으며... 혹시 본인의 AC가 의심된다면 질문 게시판에 가서 최대한 셀프 테스트를 해 보자.

어떤 최적해에서, walk 방향이 도중에 바뀔 수 있는가?

아무 위치에서나 출발해서 한 쪽 방향으로 \(n-1\)번 swap을 하자. 어떤 일이 일어나는가?

여기서는 해싱을 사용한 풀이를 설명한다. 해싱은 두 수열이 같은지 판단하기 위해서만 사용한다. 최적해에서는 방향을 바꾸는 것이 존재할 수 없음을 쉽게 관찰할 수 있다. 따라서 최적해는 항상 어떤 지점에서 출발하여 한 쪽 방향으로 계속 이동하는 것이다. 또한 임의의 위치에서 시작하여 한 쪽 방향으로 \(n-1\)번 walk를 하면, 전체 수열이 초기 수열과 비교했을 때 시계 또는 반시계 방향으로 한 칸 shift된 것과 같아짐을 확인할 수 있다. 당연히 \(n(n-1)\)번 walk를 하면 상태가 원상복구된다.

그러므로 up to rotation으로 상태가 같은 것을 제외하고 나면, 우리가 유효하게 고려해야 하는 \((\)walk 시작점, walk 횟수\()\)의 가능성은 얼마 없다. 시작점도 \(n\)개이고, walk 횟수는 \(1\)부터 \(n-2\)까지이기 때문이다. 또한 각각은 한 원소를 원-수열에서 빼낸 다음, 임의의 위치에 집어넣는 행동과 대응되므로, rolling hash를 사용한다면 이러한 모든 상태들마다의 hash 값도 prefix sum 등으로 \(O(1)\)에 전부 구해볼 수 있다! 전체 풀이를 다시 정리해보자. Up to rotation으로 두 수열이 상태가 같은지 알아보고 싶으니, 반대로 최종 상태의 가능한 회전 \(n\)가지의 hash 값을 전부 계산해뒀으면, 초기 상태에서 원소 하나를 들어서 다른 위치에 삽입한 수열의 hash 값이 그 \(n\)가지 중에 존재한다면 올바른 walk를 발견한 것이 된다. 따라서 총 \(n^2\)가지의 시행마다 \(n\)개의 hash 값 후보를 봐야 하므로, 시간복잡도는 \(O(n^2 \log n)\). 참고로, 최종 상태가 회전에 대해 대칭성을 가지고 있다면, \(n\)종류의 회전 중 서로 다른 값이 \(n\)개 나오는 것은 아닐 수 있다. 따라서 내가 선택한 회전의 방향성을 고려하여, 어떤 hash 값을 얻는 최소 회전만을 최적해의 후보로 사용해야 한다.

여기까지는 기본적으로 난이도가 어렵지 않은데, 다만 최소한 BOJ에서는 시간 제한 안에 도는 코드를 짜기 좀 힘들 것이다. 한 가지 관찰을 더 하면, walk의 방향을 시계/반시계 방향 모두 고려할 필요 없이 한 쪽만 고려해도 된다. 왜냐하면 walk swap을 \(n(n-1)\)번 하면 다시 수열이 원상복귀되기 때문에, 시계 방향으로의 \(k\)번 walk swap은 반시계 방향으로 \(n(n-1)-k\)번 walk swap한 것과 같다. 따라서 한쪽 방향만 고려할 때, valid한 walk를 찾을 때마다 반대쪽이 더 짧은 walk인지 확인해주도록 하자. 아래 코드가 이를 구현한 것이다.

아래 첨부한 코드는 꽤나 시간이 빡빡하게 도는데, rolling hash에서 할 수 있는 최적화가 하나 더 존재한다. \(MOD\)를 \(2^{61}-1\) (소수이다)로 사용하면, \(2\)의 거듭제곱에 아주 가깝다는 성질 때문에 나머지 연산을 비트 연산과 덧셈 여러 번 정도로 바꾸는 방법이 있다. (물론 \(MOD\)가 상수라면 컴파일러가 기본적인 최적화를 해주기는 할 텐데, __int128 type에서도 잘 되는지는 모르겠다. godbolt에 돌려보니 상당히 바이너리가 길어서 최적화를 끼얹은 것인지는 파악하지 못 했다.

\(O(n^2)\)에 풀리는 다른 풀이도 있다고 들었다. 이건 정확히 모르는데, 대략 이론적으로 가능할 것 같다는 감은 있다. \(n-1\)번 walk swap을 하면 전체 수열이 한 칸 회전한 것과 같은 효과를 내므로, 올바른 walk가 총 \((n-1)t + r\)번 walk swap을 시행했다고 하자. 모든 \(t=[0, n-1]\)에 대해, 각 \(t\)마다 \(O(n)\) 시간에 가능한 walk를 전부 탐색하는 풀이이다. \(t\)를 고정하고 나면 최종 상태를 반대 방향으로 \(t\)번 회전시킨 상태를 생각했을 때, 이것은 초기 수열에서 하나의 수를 빼낸 다음 다른 위치에 삽입하는 행동으로 만들어지는 상태여야 한다. 그러므로, 두 수열을 비교해서 처음으로 다른 문자가 등장하는 순간은, 내가 원소를 뺀 위치 / 원소를 삽입한 위치 둘 중 하나와 연관이 생기게 된다. 즉 수열의 모든 원소가 같은 게 아니고서야, 웬만해서는 가능한 \(r\)의 후보가 (정확히는 '중요한' \(r\)이) \(O(1)\) 수준일 것으로 추정할 수 있다. 이러한 직관 아래, 케이스를 잘 나눠서 생각하면 각각이 꽤 쉽게 풀릴 것으로 생각한다.

본 대회에서의 환경은 BOJ보다 빠른 환경이었다는 것이 정설인 것 같고, 실제로 해싱 풀이를 짜서 맞은 팀이 있었다. \(O(n^2)\) 풀이가 있는 만큼 해싱이 정해가 아닐 가능성도 있을 것 같은데 (해싱이 대회의 공식적인 솔루션이어도 되는가에 대해서 생각해볼 수도 있으나... 나는 이 주제에 대해 별 생각이 없다), \(O(n^2)\) 풀이를 내면 굳이 \(n = 10^4\)로 제한을 거는 서울 리저널의 특성을 고려했을 때 (물론 보통 상수가 매우 작을 것임을 쉽게 추정 가능하긴 하다) '해싱을 빠르게 구현할 수 있으면 맞게 하자'가 제일 합리적인 추정 아닐까?