DOJ logoDOJ
ログイン新規登録
DOJ logoDOJ
問題募集
DOJ logoDOJ

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

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

All Falls Somewhere

問題に戻る

解説

고정된 서로 다른 두 정점 a,ba,ba,b에 대해 Alice의 점수에서 Bob의 점수를 뺀 값을 생각하자. 최종적으로 정점 aaa에 있는 말 하나는 +1+1+1, 정점 bbb에 있는 말 하나는 −1-1−1, 나머지 말은 000만큼 기여한다.

fa,b(i)f_{a,b}(i)fa,b​(i)를 정점 iii에 있는 말 하나가 최종 점수 차이에 기여하는 값이라고 하자. iii번째 턴에 이 말을 인접한 정점 jjj로 옮겼을 때의 기여량은 다음과 같다.

  • j<ij<ij<i라면 정점 jjj의 턴은 이미 끝났다. j=aj=aj=a이면 +1+1+1, j=bj=b이면 , 나머지는 이다.

iii가 홀수이면 Alice가 가능한 값 중 최댓값을 고르고, iii가 짝수이면 Bob이 최솟값을 고른다. 이를 NNN부터 111까지 역순으로 계산할 수 있다.

이 계산이 말 하나만 따로 움직일 수 있다고 가정하는 것은 아니다. 정점 iii에 말이 ccc개 모여 있다면 어느 이웃을 고르든 해당 선택이 만드는 점수 차이가 ccc배가 된다. 항상 c>0c>0c>0이고, 아직 움직이지 않은 다른 정점의 말이 만드는 값은 이 선택과 무관하다. 따라서 최댓값이나 최솟값을 만드는 이웃은 ccc와 관계없으며, 위 기여량을 모든 말에 선형적으로 적용할 수 있다.

모든 (a,b)(a,b)(a,b)에 대해 위 DP를 직접 수행하면 너무 느리다. 각 기여량은 −1,0,+1-1,0,+1−1,0,+1 중 하나라는 점을 사용하자.

Pa(i)P_a(i)Pa​(i)를 fa,b(i)=+1f_{a,b}(i)=+1fa,b​(i)=인지 나타내는 값이라고 하자. 정점 에서 이웃 를 고른 결과가 인 조건은 일 때 이고, 일 때 가 참인 것이다. 따라서 다음이 성립한다.

  • iii가 홀수이면 이웃 중 하나라도 조건을 만족할 때 Pa(i)P_a(i)Pa​(i)가 참이다.
  • iii가 짝수이면 모든 이웃이 조건을 만족할 때 Pa(i)P_a(i)P가 참이다.

이 점화식에는 bbb가 등장하지 않는다. 그러므로 +1+1+1을 기여하는 말의 개수

Xa=∑i=1N[Pa(i)]X_a=\sum_{i=1}^{N}[P_a(i)]Xa​=i=1∑N​[P

는 aaa에만 의존한다.

마찬가지로 Qb(i)Q_b(i)Qb​(i)를 fa,b(i)=−1f_{a,b}(i)=-1fa,b​(i)=인지 나타내는 값이라고 하자. 이번에는 홀수 정점에서 모든 이웃이 조건을 만족해야 하고, 짝수 정점에서는 이웃 하나만 조건을 만족해도 된다. 이 점화식에는 가 등장하지 않으므로

Yb=∑i=1N[Qb(i)]Y_b=\sum_{i=1}^{N}[Q_b(i)]Yb​=i=1∑N​[Q

는 bbb에만 의존한다.

따라서 순서쌍 (a,b)(a,b)(a,b)에서 최적 플레이 뒤의 점수 차이는 정확히 Xa−YbX_a-Y_bXa​−Yb​이다. 각 목표 정점에 대해 정점을 역순으로 훑으며 와 를 계산한다.

마지막으로 모든 YbY_bYb​를 정렬한다. 각 aaa에 대해 Yb<XaY_b<X_aYb​<X인 원소의 개수를 이분 탐색으로 구하고, 이 중 가 포함되었다면 하나를 뺀다.

전체 시간 복잡도는 O(N(N+M)+Nlog⁡N)O(N(N+M)+N\log N)O(N(N+M)+NlogN)이다. 연결 그래프에서는 M≥N−1M\geq N-1M≥N−이므로 으로 나타낼 수 있다. 공간 복잡도는 이다.

Solution written by GPT6

j
=
b
−1-1−1
000
  • j>ij>ij>i라면 이후 정점 jjj의 턴에 다시 이동하므로 fa,b(j)f_{a,b}(j)fa,b​(j)이다.
  • +
    1
    iii
    jjj
    +1+1+1
    j<ij<ij<i
    j=aj=aj=a
    j>ij>ij>i
    Pa(j)P_a(j)Pa​(j)
    a
    ​
    (
    i
    )
    a​
    (
    i
    )]
    −
    1
    aaa
    b​
    (
    i
    )]
    XX
    X
    YYY
    a​
    b=ab=ab=a
    1
    O(NM)O(NM)O(NM)
    O(N+M)O(N+M)O(N+M)