ABC337 F - Usual Color Ball Problems

Competitive Programming C++

2024-01-22

공식 에디토리얼

문제 링크
https://atcoder.jp/contests/abc337/tasks/abc337_f

원문 링크
https://atcoder.jp/contests/abc337/editorial/9141

편의를 위해 주어진 수열을 2개 연결한 수열

\[C’ = (C_1’, C_2’, …, C_{2N}’) := (C_1, C_2, …, C_N, C_1, C_2, …, C_N)\]

을 생각해봅시다. 이 문제는 \(C’\)의 구간 \([l, l + N - 1]\)에 대해 조작을 할 때 상자에 들어가는 공의 총 개수를 각각의 \(l = 1, 2, …, N\)에 대해 구하는 문제로 볼 수 있습니다.
수열 \(C’\)의 구간 \([l, r]\)에 포함되는 색이 \(c\)인 공의 개수를 \(f(c, l, r)\)d이라고 나타내고, 원래 수열 \(C\) 전체에서의 색이 \(c\)인 공의 개수 \(f(c, 1, N)\)을 \(g(c)\)라고 나타냅시다.

먼저, 어떤 \(1\)개의 고정된 구간 \([l, l + N - 1]\)에 대한 문제의 답을 구하는 것부터 생각해봅시다. 구간 \([l, l + N - 1]\)에 대해 조작을 진행한 결과, 최종적으로 색이 \(c\)인 공이 차지하는 상자가 \(b(c, l)\)개 일 때, 최종적으로 상자에 들어있는 색이 \(c\)인 공의 총 개수는 \(\min{b(c, l) \times K, g(c)}\)개이며, 구하고자 하는 답 \(\mathrm{ans}_l\)은

\[\mathrm{ans_l} = \sum^N_{c = 1} \min\{b(c, l) \times K, g(c)\}\]

입니다. 각각의 색 \(c\)마다 \(b(c, l)\)을 알 수 있으면 \(\mathrm{ans}_l\)을 구할 수 있으므로, 다음으로 이 값에 대해 생각해봅시다.

빈 상자에 넣어질(결과로써 해당 색이 차지하는 상자의 개수가 \(1\) 늘어나는) 가능성이 있는 공은, 그 색의 공들 중에서 \(1, K + 1, 2K + 1, 3K + 1, …\)번째에 처리되는 공입니다. 여기서 각 색마다 \(1, K + 1, 2K + 1, 3K + 1, …\)번째에 처리되는 공을 찬스볼이라고 부르기로 합시다.

찬스볼(색과 관계 없이)이 \(1\)개 처리될 때마다 상자의 수는 \(1\)개씩 늘어날 것이므로, \(b(c, l)\)은 앞에서부터 \(M\)개째까지 처리되는 찬스볼들 중 포함되는 색이 \(c\)인 찬스볼의 개수와 같습니다. 그러면 딱 \(M\)번째로 처리되는 찬스볼의 위치는 어디일까요?

위치\(l\)부터 조작을 시작할 때, 구간 \([l, r]\)까지 존재하는 색이 \(c\)인 찬스볼의 개수는 \(\lceil f(c, l, r) / K \rceil\)개이므로, 구간 \([l, r]\)까지 있는 찬스볼(색과 관계 없이)의 개수는

\[S(l, r) = \sum^N_{c = 1} \Bigl\lceil {\frac{f(c, l, r)}{K}} \Bigr\rceil\]

개 입니다. 따라서, 앞에서부터 \(M\)개째의 찬스볼의 위치는 \(S(l, r) \geq M\)을 만족하는 가장 작은 \(r\)로부터 구할 수 있습니다. 이것을 \(r_l\)라 두면, \(b(c, l) = \lceil f(c, l, r_l) / K \rceil\)이므로, 구하는 답 \(\mathrm{ans}_l\)은

\[\mathrm{ans_l} = \sum^N_{c = 1} \min \Big\{\Bigl\lceil \frac{f(c, l, r)}{K} \Bigr\rceil \times K, g(c)\Big\}\]

입니다(식 \((1)\)).(단, \(S(l, r) \geq M\)을 만족하는 가장 작은 \(r\)이 \(r \geq l + N - 1\)의 범위 내에 존재하지 않을 때는 편의상 \(r_l := l + N - 1\)이라 생각합시다.) 즉, \(\mathrm{ans}_l\)을 구하기 위해서는 \(l\)에 대해 \(r_l\)을 구해서 \((1)\)의 식을 계산하면 됩니다. 하지만 모든 \(l = 1, 2, …, N\)에 대해 일일히 그것을 계산하자니, 제한 시간이 절망적입니다.

여기서, 위의 과정으로부터 \(r_1 \leq r_2 \leq … \leq r_N\)이 되는 것에 주목하여, \(l = 1, 2, …, N\)의 순서대로 답을 구해가면, \(l\)을 늘리면서 각 \(r_l\)을 일종의 투 포인터 알고리즘의 원리를 이용해 효율적으로 구할 수 있습니다. 또한, 투 포인터 알고리즘을 사용하는 과정에서 현재 보고 있는 구간 \([l’, r’]\) 내의 \((1)\)에 대응하는 값을 가지고 있으면서, \(l’\)나 \(r’\)를 \(1\)씩 증감시킬 때마다 이것을 갱신함으로써 각 \(\mathrm{ans}_l\)을 전체 \(O(N)\)시간만에 구할 수 있습니다.

매웠다고 한다. 보진 못했지만.

책정된 난이도나 다른 분들의 소감을 들어보면 F번치곤 꽤 어려운 문제였다는듯 하다.

… 정작 난 E에 매몰되어 보지도 못했지만.

근데 해설을 보니 E를 안 잡고 있었더라도 이걸 시간 내에 내가 생각해내진 못했을 듯.

더 열심히 해야지.