atwiki-logo
  • 新規作成
    • 新規ページ作成
    • 新規ページ作成(その他)
      • このページをコピーして新規ページ作成
      • このウィキ内の別ページをコピーして新規ページ作成
      • このページの子ページを作成
    • 新規ウィキ作成
  • 編集
    • ページ編集
    • ページ編集(簡易版)
    • ページ名変更
    • メニュー非表示でページ編集
    • ページの閲覧/編集権限変更
    • ページの編集モード変更
    • このページにファイルをアップロード
    • メニューを編集
    • 右メニューを編集
  • バージョン管理
    • 最新版変更点(差分)
    • 編集履歴(バックアップ)
    • アップロードファイル履歴
    • ページ操作履歴
  • ページ一覧
    • ページ一覧
    • このウィキのタグ一覧
    • このウィキのタグ(更新順)
    • このページの全コメント一覧
    • このウィキの全コメント一覧
    • おまかせページ移動
  • RSS
    • このウィキの更新情報RSS
    • このウィキ新着ページRSS
  • ヘルプ
    • ご利用ガイド
    • Wiki初心者向けガイド(基本操作)
    • このウィキの管理者に連絡
    • 運営会社に連絡(不具合、障害など)
ページ検索 メニュー
早稲田大学チームvivid_turtle 知見共有@ ウィキ
  • ウィキ募集バナー
  • 目安箱バナー
  • 操作ガイド
  • 新規作成
  • 編集する
  • 全ページ一覧
  • 登録/ログイン
ページ一覧
早稲田大学チームvivid_turtle 知見共有@ ウィキ
  • ウィキ募集バナー
  • 目安箱バナー
  • 操作ガイド
  • 新規作成
  • 編集する
  • 全ページ一覧
  • 登録/ログイン
ページ一覧
早稲田大学チームvivid_turtle 知見共有@ ウィキ
ページ検索 メニュー
  • 新規作成
  • 編集する
  • 登録/ログイン
  • 管理メニュー
管理メニュー
  • 新規作成
    • 新規ページ作成
    • 新規ページ作成(その他)
      • このページをコピーして新規ページ作成
      • このウィキ内の別ページをコピーして新規ページ作成
      • このページの子ページを作成
    • 新規ウィキ作成
  • 編集
    • ページ編集
    • ページ編集(簡易版)
    • ページ名変更
    • メニュー非表示でページ編集
    • ページの閲覧/編集権限変更
    • ページの編集モード変更
    • このページにファイルをアップロード
    • メニューを編集
    • 右メニューを編集
  • バージョン管理
    • 最新版変更点(差分)
    • 編集履歴(バックアップ)
    • アップロードファイル履歴
    • ページ操作履歴
  • ページ一覧
    • このウィキの全ページ一覧
    • このウィキのタグ一覧
    • このウィキのタグ一覧(更新順)
    • このページの全コメント一覧
    • このウィキの全コメント一覧
    • おまかせページ移動
  • RSS
    • このwikiの更新情報RSS
    • このwikiの新着ページRSS
  • ヘルプ
    • ご利用ガイド
    • Wiki初心者向けガイド(基本操作)
    • このウィキの管理者に連絡
    • 運営会社に連絡する(不具合、障害など)
  • atwiki
  • 早稲田大学チームvivid_turtle 知見共有@ ウィキ
  • 2次元座標と二部グラフ

早稲田大学チームvivid_turtle 知見共有@ ウィキ

2次元座標と二部グラフ

最終更新:2019年09月15日 00:31

vivid_turtle

- view
だれでも歓迎! 編集
二次元座標を二部グラフとみなすのは典型テクニックとして知られていて、蟻本にも中級編第三章に乗ってる。
以下がその考え方の概要である。

概要

このようにx軸とy軸の位置ごとに、二部グラフにする。
例は(x, y) = (1, 2)とすると、その点の位置を辺として両側の頂点とつなげる
 
x軸       y軸
x=0 〇     〇  y=0
 
x=1 〇---   〇  y=2
        |----
x=2 〇    |-〇  y=2
 
 
 

二部グラフとみなすことで、二部グラフの最大マッチングなどに帰着しやすい。そうでなくとも、二部グラフの完全グラフなどの性質を思いつきやすい。

例 ABC131 F(600) Must Be Rectangular!


https://atcoder.jp/contests/abc131/tasks/abc131_f

この問題では、先ほどの考え方を使うと、x軸側の頂点2つ、y軸側の頂点二つ間それぞれに辺を引かれた状態、つまり(x1, y1), (x2, y1), (x1, y2), (x2, y2)に点が打たれてる状態にしたい。この状態をXとする。
これをもとに考察を進めると、上記で定義したグラフで、x軸側とy軸側でつながってるひとかたまりは、いい感じに辺(つまり2次元平面上での点)を追加すると、全部のx軸側とy軸側の点の組み合わせにおいて、Xの状態を達成できるとわかる。これは二部グラフの完全マッチングそのものである。
つまり、この問題は上記の考え方を入口に、ひとかたまりずつ、二部グラフの完全マッチング数を求めて、それの和を求めてから最初にすでにあるN個の点を引けばいいとわかる。

ちなみにひとかたまりを考察するときに使う典型として、「Union Find木」があり、今回もこれを使うとスッキリ実装できる。けんちょん先生参照すべし。

タグ:

+ タグ編集
  • タグ:
タグの更新に失敗しました
エラーが発生しました。ページを更新してください。
ページを更新
「2次元座標と二部グラフ」をウィキ内検索
LINE
シェア
Tweet
早稲田大学チームvivid_turtle 知見共有@ ウィキ
記事メニュー

メニュー

  • トップページ
  • プラグイン紹介
  • メニュー
  • 右メニュー
  • アルゴリズム別知見
  • 個別問題知見



リンク

  • @wiki
  • @wikiご利用ガイド




ここを編集
記事メニュー2

更新履歴

取得中です。


ここを編集
人気記事ランキング
  1. 個別問題知見
  2. グリッド上での数え上げ
  3. AGC014-B
  4. 後ろから見ると上手くいくパターン
  5. クエリ処理でのデータ構造特有の手法
  6. 文字列と動的計画法
もっと見る
最近更新されたページ
  • 1593日前

    bitsetでの定数倍改善
  • 2207日前

    しゃくとりの大原則
  • 2207日前

    アルゴリズム別知見
  • 2210日前

    グリッド上の構築
  • 2211日前

    ARC096-D
  • 2211日前

    ARC092-D
  • 2211日前

    個別問題知見
  • 2215日前

    ダブリングの使い所さん
  • 2221日前

    文字列と動的計画法
  • 2221日前

    数え上げのDPのさまざま(知らなかったこと)
もっと見る
人気記事ランキング
  1. 個別問題知見
  2. グリッド上での数え上げ
  3. AGC014-B
  4. 後ろから見ると上手くいくパターン
  5. クエリ処理でのデータ構造特有の手法
  6. 文字列と動的計画法
もっと見る
最近更新されたページ
  • 1593日前

    bitsetでの定数倍改善
  • 2207日前

    しゃくとりの大原則
  • 2207日前

    アルゴリズム別知見
  • 2210日前

    グリッド上の構築
  • 2211日前

    ARC096-D
  • 2211日前

    ARC092-D
  • 2211日前

    個別問題知見
  • 2215日前

    ダブリングの使い所さん
  • 2221日前

    文字列と動的計画法
  • 2221日前

    数え上げのDPのさまざま(知らなかったこと)
もっと見る
ウィキ募集バナー
急上昇Wikiランキング

急上昇中のWikiランキングです。今注目を集めている話題をチェックしてみよう!

  1. デジタルモンスター まとめ@ ウィキ
  2. 神様コレクション@wiki
  3. ストグラFV まとめ@非公式wiki
  4. MADTOWNGTAまとめwiki
  5. Last Z: Survival Shooter @ ウィキ
  6. ディズニー データベース
  7. 戦国無双4シリーズ  総合攻略 @ Wiki
  8. テイルズオブ用語辞典
  9. SQ用語辞典
  10. GUNDAM WAR Wiki
もっと見る
人気Wikiランキング

atwikiでよく見られているWikiのランキングです。新しい情報を発見してみよう!

  1. アニヲタWiki(仮)
  2. ゲームカタログ@Wiki ~名作からクソゲーまで~
  3. MADTOWNGTAまとめwiki
  4. 初音ミク Wiki
  5. ストグラ まとめ @ウィキ
  6. 検索してはいけない言葉 @ ウィキ
  7. 機動戦士ガンダム バトルオペレーション2攻略Wiki 3rd Season
  8. 発車メロディーwiki
  9. MadTown GTA (Beta) まとめウィキ
  10. 機動戦士ガンダム EXTREME VS.2 INFINITEBOOST wiki
もっと見る
新規Wikiランキング

最近作成されたWikiのアクセスランキングです。見るだけでなく加筆してみよう!

  1. MadTown GTA (Beta) まとめウィキ
  2. MADTOWNGTAまとめwiki
  3. まどドラ攻略wiki
  4. ちいぽけ攻略
  5. シュガードール情報まとめウィキ
  6. 戦国ダイナスティ攻略Wiki@ウィキ
  7. Last Z: Survival Shooter @ ウィキ
  8. Shoboid RPまとめwiki
  9. ソニックレーシング クロスワールド 攻略@ ウィキ
  10. SurrounDead 攻略 (非公式wiki)
もっと見る
全体ページランキング

最近アクセスの多かったページランキングです。話題のページを見に行こう!

  1. 参加者一覧 - MADTOWNGTAまとめwiki
  2. 白狐 - MADTOWNGTAまとめwiki
  3. 参加者一覧 - MadTown GTA (Beta) まとめウィキ
  4. angler - MADTOWNGTAまとめwiki
  5. XVI - MADTOWNGTAまとめwiki
  6. 魔獣トゲイラ - バトルロイヤルR+α ファンフィクション(二次創作など)総合wiki
  7. ソーシャルゲームに関する都市伝説 - アニヲタWiki(仮)
  8. 参加者一覧 - ストグラ まとめ @ウィキ
  9. 鬼レンチャン(レベル順) - 鬼レンチャンWiki
  10. ミャクミャク - アニヲタWiki(仮)
もっと見る

  • このWikiのTOPへ
  • 全ページ一覧
  • アットウィキTOP
  • 利用規約
  • プライバシーポリシー

2019 AtWiki, Inc.