DOJ logoDOJ
問題
最近追加された問題保存した問題Workbooks
カテゴリDLCコンテストグループチーム掲示板
ランキング
正解数ランキングストリークランキングDOJ Powerランキング
提出状況
問題募集ログイン新規登録
DOJ logoDOJ

OI形式のサブタスク採点、Eloレーティング、Discord連携を備えたオンラインジャッジです。

問題
問題一覧カテゴリ
コミュニティ
コンテストランキング掲示板お知らせ外部のコンテストを開催するガイド
アカウント
ログイン新規登録ジャッジ状態
ポリシー
利用規約DLCの利用規則プライバシーAPI 文書言語ランタイムコンテストの順位報酬レーティングとパフォーマンス
© 2026 DOJ
All rights reserved
解説

Candies

問題に戻る

解説

pos⁡x\operatorname{pos}_xposx​를 xxx번 아이가 처음 서 있던 위치라고 하자.

어떤 아이가 현재 위치 ppp에 있고 사탕을 ccc개 가지고 있다고 하자. 한 번의 조작에서 맨 왼쪽 아이는 오른쪽으로 222칸 이동하고 사탕을 111개 받는다. 나머지 두 아이는 왼쪽으로 111칸 이동하고 사탕을 111개 받는다. 따라서 모든 아이에 대해 항상 p+c≡pos⁡x(mod3)p+c\equiv \operatorname{pos}_x\pmod 3p+c≡posx​(mod3)이 성립한다.

조작되는 세 아이의 사탕 수는 같다. 따라서 연속한 세 위치에 있는 아이들의 최초 위치를 333으로 나눈 나머지는 서로 다르다. 그러므로 최초 위치가 같은 나머지를 가지는 두 아이의 상대적인 순서는 절대로 바뀌지 않는다.

따라서 처음에 위치 iii와 i+3i+3i+3에 있던 아이는 최종 상태에서도 같은 순서를 유지해야 한다. 최종 상태에서는 번호가 증가하는 순서이므로 모든 1≤i≤N−31\le i\le N-31≤i≤N−3에 대해 Pi<P이어야 한다. 하나라도 만족하지 않으면 답은 이다.

이제 이 조건이 성립한다고 하자.

최종적으로 iii번 아이는 위치 iii에 있어야 한다. 이 아이의 최초 위치가 pos⁡i\operatorname{pos}_iposi​이고 마지막 사탕 수가 HiH_iHi라면, 앞의 불변량으로부터 을 얻는다.

현재 각 위치에 있는 아이의 사탕 수만 배열로 보자. 사탕 수가 모두 hhh인 연속한 세 아이를 조작하면 위치별 사탕 수는 h,h,hh,h,hh,h,h에서 h+1,h+1,h+1h+1,h+1,h+1h+1,h+1,h+로 변한다. 따라서 한 번의 조작을 막대그래프 위에 길이 짜리 수평 블록 하나를 올리는 것으로 생각할 수 있다.

최종 사탕 수가 H1,H2,…,HNH_1,H_2,\ldots,H_NH1​,H2​,…,HN​이라고 하자. 임의의 양의 정수 에 대해 인 위치들만 보면, 각 극대 연속 구간의 길이는 반드시 의 배수여야 한다. 한 층은 길이 인 블록들로만 만들어지기 때문이다.

반대로 이 조건을 만족하면 실제로 만들 수 있다. 낮은 층부터 차례대로 보면서, 높이 kkk 이상인 각 연속 구간을 왼쪽부터 세 칸씩 나누어 조작하면 된다. 해당 층을 만들기 직전에는 선택한 세 위치의 사탕 수가 모두 k−1k-1k−1이므로 조작은 항상 가능하다.

따라서 이제 각 iii에 대해 Hi≡pos⁡i−i(mod3)H_i\equiv \operatorname{pos}_i-i\pmod3Hi​≡posi​−i을 만족시키면서, 모든 높이에서 연속 구간의 길이가 의 배수가 되도록 을 정하면 된다. 조작 한 번은 전체 사탕 수를 정확히 증가시키므로 필요한 조작 횟수는 이다.

HiH_iHi​를 왼쪽부터 결정하자. 각 높이 kkk에 대해 SkS_kSk​를 현재까지 높이 kk에서 이어지고 있는 마지막 연속 구간의 길이를 으로 나눈 나머지라고 하자.

Sk≠0S_k\ne0Sk​=0이면 높이 kkk의 마지막 구간이 아직 완성되지 않았다는 뜻이다. 따라서 다음 위치 역시 높이 kkk 이상이어야 한다. M을 인 가장 큰 라고 하면 다음 높이는 반드시 이상이다. 그런 가 없다면 으로 둔다.

한편 HiH_iHi​는 Hi≡pos⁡i−i(mod3)H_i\equiv \operatorname{pos}_i-i\pmod3Hi​≡pos을 만족해야 한다. 따라서 이상인 정수 중 이 합동식을 만족하는 가장 작은 값을 로 선택한다.

이 선택은 항상 최적이다. MMM보다 작은 값을 선택하는 것은 아직 완성되지 않은 어떤 층의 구간을 그대로 끝내므로 불가능하다. 반대로 선택한 값보다 같은 나머지를 가지는 더 큰 값을 고르려면 적어도 333을 더해야 한다. 이렇게 새로 추가되는 세 층은 기존의 미완성 구간을 완성하는 데 아무 도움도 주지 않고, 새로운 미완성 구간만 만든다. 따라서 더 높은 값을 선택할 이유가 없다.

HiH_iHi​를 정한 뒤에는 높이 111부터 HiH_iHi​까지의 마지막 구간 길이가 모두 11씩 증가하므로 에 각각 을 더하고 으로 나눈 나머지를 취한다.

모든 위치를 처리한 뒤 Sk≠0S_k\ne0Sk​=0인 높이가 하나라도 남아 있다면 마지막 연속 구간의 길이가 333의 배수가 아닌 층이 존재하므로 불가능하다. 모두 000이라면 지금까지 선택한 높이들이 최적이다.

필요한 연산은 S1,…,SHS_1,\ldots,S_HS1​,…,SH​에 111을 더하는 prefix 갱신과, Sk≠0S_k\ne0인 가장 큰 를 찾는 것이다. Lazy Propagation을 사용하는 세그먼트 트리로 처리할 수 있다.

각 노드에는 해당 구간에 등장하는 SkS_kSk​의 값들을 333비트 마스크로 저장한다. bit jjj는 그 구간에 Sk=jS_k=jS인 위치가 존재한다는 뜻이다. 구간 전체에 을 더하고 으로 나눈 나머지를 취하면 상태 가 각각 으로 바뀌므로 비트 마스크를 한 칸 순환시키면 된다.

Sk≠0S_k\ne0Sk​=0인 가장 큰 kkk를 찾을 때는 오른쪽 자식부터 확인하면서 상태 111 또는 22가 존재하는 쪽으로 내려가면 된다.

새로운 HiH_iHi​는 현재의 MMM보다 최대 222만 크므로 모든 높이는 2N2N2N 이하만 관리하면 충분하다.

시간 복잡도는 O(Nlog⁡N)O(N\log N)O(NlogN)이고, 메모리 복잡도는 O(N)O(N)O(N)이다.

Solution written by GPT5.6

i+3P_i<P_{i+3}
Pi​<Pi+3​
−1-1−1
​
Hi≡pos⁡i−i(mod3)H_i\equiv \operatorname{pos}_i-i\pmod 3Hi​≡posi​−i(mod3)
1
333
kk
k
Hi≥kH_i\ge kHi​≥k
333
333
(mod3)
333
H1,H2,…,HNH_1,H_2,\ldots,H_NH1​,H2​,…,HN​
333
(H1+H2+⋯+HN)/3(H_1+H_2+\cdots+H_N)/3(H1​+H2​+⋯+HN​)/3
k
333
M
M
Sk≠0S_k\ne0Sk​=0
kkk
MMM
kkk
M=0M=0M=0
i​
−
i
(mod3)
MMM
HiH_iHi​
1
S1,S2,…,SHiS_1,S_2,\ldots,S_{H_i}S1​,S2​,…,SHi​​
111
333
Sk​=
0
kkk
k
​
=
j
111
333
0,1,20,1,20,1,2
1,2,01,2,01,2,0
2