ABC340 E - Mancala2
Competitive Programming C++
2024-02-11
공식 에디토리얼
문제 링크
https://atcoder.jp/contests/abc340/tasks/abc340_e
원문 링크
https://atcoder.jp/contests/abc340/editorial/9251
공을 분배하는 조작을 \(N\)회씩 묶는 것으로 다음과 같은 조작이 됩니다.
- 상자 \(B_i\)의 공을 모두 꺼내서 손에 든다.
- 손에 든 공의 개수를 \(X\)라 할 때, 모든 상자에 \(\lfloor \frac{X}{N} \rfloor\)개씩 공을 넣는다.
- 아직 손에 남아있는 공의 개수를 \(X\)라고 할 때, 상자 \(B_i + 1\)부터 상자 \(B_i + X\)까지 1개씩 공을 넣는다.
(\(B_i + X \geq N\)일 때, [상자 \(B_i + 1\)부터 상자 \(B_i + X\)까지]는 [상자 \(B_i + 1\)부터 상자 \(N - 1\)까지] 및 [상자 \(0\)부터 상자 \(B_i + X - N\)까지]을 의미한다.)
각 상자에 든 공의 개수를 나타내는 배열에 대해 이 처리들은 점 쿼리와 구간 쿼리이므로, 느리게 갱신되는 세그먼트 트리 등의 자료구조를 이용해 \(O(\log N)\)에 처리가 가능하며, 전체 \(O((M + N) \log N)\)에 문제의 답을 낼 수 있습니다.
다른 풀이
원문 링크
https://atcoder.jp/contests/abc340/editorial/9267
이 문제는 수열 \(A\)에 대해 구간 \((A_L, A_{L + 1}, …, A_R)\)에 대한 일종의 업데이트 연산과 점 \(A_x\)에 대한 접근을 관리할 수 있으면 됩니다.
여기서 수열 \(D = (D_0, D_1, …, D_{N - 1})\)을 \(A_i = \sum_{j = 0}^i D_j\)를 만족하는 것으로 두고 \(D\)를 관리하기로 합시다.
그렇게 하면 위의 \(2\)종류의 쿼리는 \(2\)개의 점 \(D_L, D_{R + 1}\)에 각각 \(+k, -k\)를 하는 것과, \(\mathrm{prefix\ sum} \sum_{j = 1}^x D_j\)를 구하는 것으로 바꿀 수 있습니다.
이는 일반적인 세그먼트 트리나 바이너리 인덱스 트리(펜윅 트리) 등으로 관리가 가능합니다.
공식 에디토리얼애서 설명된 것처럼 느리게 갱신된느 세그먼트 트리를 구현했을 때와 비교해서, 시간복잡도 \(O((M + N) \log N)\)이고 공간복잡도 \(O(N)\)인 것은 변함없지만, 상수를 더 줄일 수 있습니다.
아는게 나왔다
이번 ABC E번은 내가 아는 레이지 세그 쓰는게 나왔다.
덕분에 오랜만에 E번을 풀었다.
더 똑똑하게는 다른 해설처럼 일반 세그나 펜윅으로 관리할 수 있었겠지만 생각나는건 레이지 세그 말곤 없었어서…
D까지 15분 정도에 풀긴 했지만 디버깅 하느라 1시간을 써먹었다.
다음엔 더 잘해야지.