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

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

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

Starry Sky Parade

問題に戻る

解説

마지막에 추가된 별은 기존 모든 별과 연결되었거나 어느 별과도 연결되지 않았다. 따라서 현재 남아 있는 정점이 SSS개라면 차수가 S−1S-1S−1인 정점 또는 차수가 000인 정점을 하나 제거할 수 있다. 이를 정점 하나만 남을 때까지 반복하면 정점이 추가된 순서와 각 정점이 추가될 때 사용한 방법을 역순으로 복원할 수 있다.

이 제거 과정을 빠르게 구현해 보자. 처음 그래프에서의 정점 vvv의 차수를 DvD_vDv​라 하고, 지금까지 제거한 연결 정점의 개수를 CCC라 하자. 제거된 연결 정점은 현재 남아 있는 모든 정점과 인접했고, 제거된 고립 정점은 현재 남아 있는 어떤 정점과도 인접하지 않았다. 따라서 아직 남은 정점 vvv의 현재 차수는 항상

Dv−CD_v-CDv​−C

이다.

현재 정점이 SSS개 남았다면 다음 정점을 제거할 수 있다.

  • Dv=CD_v=CDv​=C인 정점은 현재 차수가 000인 고립 정점이다.
  • Dv=C+S−1D_v=C+S-1Dv인 정점은 현재 차수가 인 연결 정점이다.

초기 차수별로 정점을 버킷에 넣으면 매 단계에서 필요한 정점을 O(1)O(1)O(1)에 꺼낼 수 있다. 입력이 조건을 만족하므로 둘 중 하나는 항상 존재한다. 간선을 읽어 초기 차수를 계산하는 시간을 포함하여 복원에는 O(N+M)O(N+M)O(N+M)이 걸린다.

이제 제거 기록을 거꾸로 따라가며 밝기를 정한다. 처음 정점의 밝기는

⌈N2⌉\left\lceil\frac N2\right\rceil⌈2N​⌉

로 둔다. 지금까지 정한 밝기의 최솟값을 LLL, 최댓값을 RRR이라고 하자.

  • 고립 정점을 추가한다면 밝기를 N−RN-RN−R로 정한다. 기존 모든 밝기와의 합이 NNN 이하이므로 새 간선이 생기지 않는다.
  • 연결 정점을 추가한다면 밝기를 N−L+1N-L+1N−L+1로 정한다. 기존 모든 밝기와의 합이 NNN보다 크므로 모든 기존 정점과 연결된다.

마지막으로 모든 밝기가 111 이상 NNN 이하임을 보이자. 매 단계에서

L+R∈{N,N+1}L+R\in\{N,N+1\}L+R∈{N,N+1}

가 유지된다. 또한 정점을 하나 추가할 때마다 R−LR-LR−L은 최대 111 증가하므로, 전체 과정에서 R−L≤N−1R-L\leq N-1R−L≤N−1이다. 두 성질을 합치면 L≥1L\geq1, 을 얻는다.

시간 복잡도는 O(N+M)O(N+M)O(N+M)이고 공간 복잡도도 O(N+M)O(N+M)O(N+M)이다.

Solution written by GPT6

​
=
C+
S−
1
S−1S-1S−1
L≥1
R≤NR\leq NR≤N