ABC 338 E — Chords

考察

各chordの端点をA_i<B_iに揃え、円を1と2Nの間で切る。二本が交差するのは端点がA_i<A_j<B_i<B_jのように交互に現れる場合であり、交差がなければ開いたchord区間は互いにdisjointか完全にnestedになる。

採用する候補: 端点を順に走査し、open中のchordをstackで照合する

非交差ならnested区間の閉じ順は必ずLIFOであり、一度の線形走査で交差を検出できる。

棄却する候補: 全chord pairの端点順を比較する

pair数がO(N^2)でN=2×10^5に対応できない。

左端を見たchordをpushし、右端iを見た時にstack topがiでなければ、iの内側で開始した別chordがまだ閉じておらずA_i<A_j<B_i<B_jとなる。逆にtopが常に一致すれば全区間は正しくnestedし交差しない。

各chordで端点をmin/maxにし、位置1,…,2Nにchord IDと左/右種別を記録する。左端ならIDをpush、右端ならpopしたIDと比較し、不一致ならYesを即出力する。最後まで一致すればNo。

典型の発動条件

円環のcut展開

発動条件: 円周上の端点の交互配置を線形順序で判定したい。

端点間の切れ目で円を開き、各chordを区間の開閉eventとして扱う。

括弧列としてのstack判定

発動条件: 区間族が交差せずnested/disjointであるかを調べたい。

chord IDを括弧種類とみなし、closeが直近openと一致するか確認する。

問題固有の要素

全端点がdistinctなので、非交差chord配置の端点列はID付きの正しい括弧列と同値になる。

別の問題へ持ち帰る視点: 区間の部分重なり検出は、laminar族なら開閉eventがLIFOになることを使える。

正当性

二chordが交差する必要十分は円周端点順が交互になること。開いた区間がnested/disjointなら右端は最新左端のchordを閉じるのでstackが一致する。右端でtop不一致なら先に開いたchordの内側で別chordが開いたまま外へ続く交互順を具体的に得る。従って一度でも不一致が交差、最後まで一致なら非交差。

実装上の注意

  • 各pairをA_i<B_iへswapしてからeventを置く。right event時にstackが空になる入力は端点distinctな正規pairでは起きないが安全に分岐できる。

復習の核

  • disjoint、完全nested、端点が交互の二本、外側chordを跨いで複数交差する例でstack列を確認する。

計算量と制約

時間

O(N)。全2N端点のstack走査。

空間

O(N)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 2\leq N \leq 2\times 10^5; 1\leq A_i,B_i \leq 2N; A_1,\dots,A_N,B_1,\dots,B_N are all distinct; All input values are integers

出典

分類・前提・執筆情報

掲載状態: 収録済み

Chords の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 円環順序・chord交差

主題
  • 円環順序・chord交差: 円周をcutして端点を線形化し、交互配置またはlaminar括弧構造からchord交差を判定・数え上げできる。
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: 円環順序・chord交差

      執筆: abc-explanation-author1.1.1 / revision 1

      学習の位置

      体系上の位置: 円環順序・chord交差

      • 円周をcutして端点を線形化し、交互配置またはlaminar括弧構造からchord交差を判定・数え上げできる。

      先に読む単元:

      学習記録

      状況更新: 更新記録なし

      復習設定更新: 更新記録なし

      端末内の保存状態を確認しています。

      要復習一覧 / 学習記録のバックアップ / 解説に戻る

      同じ単元の問題