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

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

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

Frogs

問題に戻る

解説

B=XNB=X_NB=XN​이라 두자. i<Ni<Ni<N에 대해 Gi=gcd⁡(∣Xi+1−B∣,…,∣XN−B∣)G_i=\gcd(|X_{i+1}-B|,\ldots,|X_N-B|)Gi​=gcd(∣Xi+1​−B∣,…,∣XN라 정의하고, 편의상 GN=0G_N=0GN​=0이라 둔다. 좌표가 모두 다르므로 GN−1=0G_{N-1}=0GN−1​=0이고, i≤N−2i\le N-2i≤N−2이면 Gi>0G_i>0Gi​>0이다.

iii번 개구리가 도달할 수 있는 좌표의 집합을 SiS_iSi​라 하면 다음과 같다. SN={B}S_N=\{B\}SN​=이다. 이면 이다. 이면 는 또는 인 모든 정수 의 집합이다. 더 나아가, 서로 다른 좌표 를 하나씩 고른 모든 배치는 실제로 만들 수 있다.

도달 가능 집합의 증명

모든 좌표에서 BBB를 빼서 NNN번 개구리를 000에 놓자. iii보다 번호가 큰 개구리들의 좌표의 최대공약수는 처음에 GiG_iGi​이고 항상 유지된다. 실제로 한 좌표를 에서 로 바꾸어도 이다. 따라서 모든 점프의 중심은 의 배수이고, 번 개구리의 좌표는 를 법으로 부호만 바뀔 수 있다. 이는 위 조건의 필요성을 보인다.

도달 가능 집합들은 강한 포함 관계를 가진다. i<ji<ji<j이면 Si∩Sj=∅S_i\cap S_j=\varnothingSi​∩Sj​이거나 이다.

층상 구조의 증명

i<ji<ji<j이면 Gi∣GjG_i\mid G_jGi​∣Gj​이고, 도 의 배수이다. 두 집합이 한 좌표에서 만난다고 하자. 의 두 나머지 와 를 로 줄이면 의 두 나머지 와 가 된다. 또한 이므로 의 모든 좌표가 에 속한다. 인 유한 집합과 도 같은 논리로 처리된다.

이제 N,N−1,…,1N,N-1,\ldots,1N,N−1,…,1 순서로 개구리를 처리한다. 각 개구리를 자신의 도달 가능 집합에서 이미 사용된 좌표를 제외하고 ∣x∣|x|∣x∣가 가장 작은 좌표에 놓는 그리디가 최적이다.

그리디의 최적성 증명

번호가 큰 개구리들에 대해 그리디와 같은 좌표를 사용하는 최적 배치를 하나 잡자. 현재 iii번 개구리에 대해 그리디가 고른 좌표를 xxx, 최적 배치가 고른 좌표를 yyy라 하자. yyy도 번호가 큰 개구리들이 사용하지 않은 후보이므로 ∣x∣≤∣y∣|x|\le|y|∣x∣≤이다.

남은 것은 각 SiS_iSi​에서 절댓값이 가장 작은 빈 좌표를 찾는 일이다. Gi>0G_i>0Gi​>0일 때 m=2Gim=2G_i라 하자. 나머지 을 으로 정규화하면 그 나머지류의 좌표는 양의 방향의 와 음의 방향의 이다. 단, 인 경우 음의 방향은 에서 시작한다.

​
−
B∣)
{
B
}
Gi=0G_i=0Gi​=0
Si={Xi,2B−Xi}S_i=\{X_i,2B-X_i\}Si​={Xi​,2B−Xi​}
Gi>0G_i>0Gi​>0
SiS_iSi​
x≡Xi(mod2Gi)x\equiv X_i\pmod {2G_i}x≡Xi​(mod2Gi​)
x≡2B−Xi(mod2Gi)x\equiv2B-X_i\pmod {2G_i}x≡2B−Xi​(mod2Gi​)
xxx
Yi∈SiY_i\in S_iYi​∈Si​
uuu
2v−u2v-u2v−u
gcd⁡(u,v,…)=gcd⁡(2v−u,v,…)\gcd(u,v,\ldots)=\gcd(2v-u,v,\ldots)gcd(u,v,…)=gcd(2v−u,v,…)
GiG_iGi​
iii
2Gi2G_i2Gi​

역을 보이자. 번호가 큰 개구리들을 유한 집합 CCC에 고정하고 한 개구리만 움직인다고 하자. 0∈C0\in C0∈C이고 d=gcd⁡{∣c∣:c∈C}d=\gcd\{|c|:c\in C\}d=gcd{∣c∣:c∈C}라 하자. ccc를 중심으로 한 반사를 Rc(y)=2c−yR_c(y)=2c-yRc​(y)=2c−y라 쓰면 RcR0R_cR_0Rc​R0​은 2c2c2c만큼의 평행이동이다. 베주 항등식으로 2d2d2d만큼의 평행이동을 만들 수 있고, R0R_0R0​으로 부호를 바꿀 수 있으므로 장애물을 무시한 궤도는 정확히 앞에서 구한 나머지류들이다.

착지점은 비어 있어야 하므로 CCC를 피할 수 있음도 확인해야 한다. 궤도가 CCC와 만나지 않으면 자명하다. 만나면 그 궤도는 하나의 등차수열이 된다. L=min⁡CL=\min CL=minC, U=max⁡CU=\max CU=maxC라 하자. CCC 밖의 어떤 궤도 점도 RL,RUR_L,R_URL​,RU​를 이용해 UUU보다 오른쪽으로 옮길 수 있고, 두 반사를 번갈아 적용하면 임의로 멀리 보낼 수 있다. 2d2d2d만큼 이동시키는 고정된 유한 반사열을 충분히 멀리서 적용하면 모든 중간 좌표가 CCC 밖에 있다. 따라서 같은 궤도의 임의의 두 빈 좌표 사이를 이동할 수 있다.

마지막으로 개구리 수에 대해 귀납한다. 2,…,N2,\ldots,N2,…,N번 개구리를 목표로 옮기는 유한한 과정에서 등장하는 좌표는 유한 개뿐이다. N≥3N\ge3N≥3이면 S1S_1S1​은 무한하므로, 그 좌표들을 모두 피하는 곳에 111번 개구리를 주차할 수 있다. 나머지 개구리를 옮긴 뒤 111번 개구리를 목표로 옮긴다. N=1,2N=1,2N=1,2는 직접 확인할 수 있다. 이로써 서로 다른 대표 좌표를 고른 모든 배치가 실제로 도달 가능하다.

=
∅
Sj⊆SiS_j\subseteq S_iSj​⊆Si​
Xj−BX_j-BXj​−B
GiG_iGi​
SjS_jSj​
Xj−BX_j-BXj​−B
−(Xj−B)-(X_j-B)−(Xj​−B)
2Gi2G_i2Gi​
SiS_iSi​
Xi−BX_i-BXi​−B
−(Xi−B)-(X_i-B)−(Xi​−B)
2Gi∣2Gj2G_i\mid2G_j2Gi​∣2Gj​
SjS_jSj​
SiS_iSi​
Gj=0G_j=0Gj​=0
SNS_NSN​
∣y∣

xxx가 최적 배치에서 비어 있다면 iii번 개구리를 xxx로 옮겨도 최댓값은 증가하지 않는다. 아니면 어떤 k<ik<ik<i번 개구리가 xxx를 사용한다. x∈Si∩Skx\in S_i\cap S_kx∈Si​∩Sk​이고 k<ik<ik<i이므로 층상 구조에 의해 Si⊆SkS_i\subseteq S_kSi​⊆Sk​이다. 따라서 y∈Sky\in S_ky∈Sk​이고, iii번과 kkk번 개구리의 좌표 x,yx,yx,y를 맞바꿀 수 있다. 사용되는 좌표의 집합과 최댓값은 그대로이다. 이 교환을 반복하면 어떤 최적 배치가 그리디 전체와 일치한다.

m
=
2Gi​
rrr
0≤r<m0\le r<m0≤r<m
r,r+m,r+2m,…r,r+m,r+2m,\ldotsr,r+m,r+2m,…
r−m,r−2m,…r-m,r-2m,\ldotsr−m,r−2m,…
r=0r=0r=0
−m,−2m,…-m,-2m,\ldots−m,−2m,…

현재 법 mmm의 각 나머지마다 두 방향에서 아직 확인하지 않은 첫 좌표를 저장한다. 전체 사용 좌표는 해시 집합에 저장하고, 포인터가 사용된 좌표를 가리키는 동안 한 칸씩 진행한다. SiS_iSi​를 이루는 두 나머지에서 얻은 최대 네 후보 중 가장 좋은 것을 고르면 된다. Gi=0G_i=0Gi​=0이면 XiX_iXi​와 2B−Xi2B-X_i2B−Xi​만 비교한다.

iii를 감소시키며 Gi=gcd⁡(Gi+1,∣Xi+1−B∣)G_i=\gcd(G_{i+1},|X_{i+1}-B|)Gi​=gcd(Gi+1​,∣Xi+1​−B∣)를 갱신한다. 법이 바뀌면 나머지별 포인터만 초기화하고 사용 좌표 집합은 유지한다. 양수인 GiG_iGi​가 바뀔 때마다 이전 값의 진약수가 되므로 절반 이하로 감소한다. 따라서 서로 다른 법은 O(log⁡109)O(\log 10^9)O(log109)개뿐이다. 하나의 법이 유지되는 동안 각 사용 좌표는 포인터에 의해 최대 한 번 건너뛰어지므로 전체 기대 시간 복잡도는 O(Nlog⁡109)O(N\log 10^9)O(Nlog109), 메모리 복잡도는 O(N)O(N)O(N)이다.

Solution written by GPT5.6