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

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

データ構造と値の取得

最終更新:2019年05月31日 00:17

vivid_turtle

- view
メンバー限定 登録/ログイン
クエリ系、DP加速系でありがちな数値をデータ構造でO(N)からO(log n)、O(sqrt(n))にして解く系の問題のテクニックを纏める。

基本的なおはなし


C++のSTLにあるデータ構造で、競プロのオーダー落としによく使われてるのが、std::map, std::set, std::multiset, std::priority_queueである。これらの中身は基本的に(僕が覚えてる限り)平衡二分木である。この性質としては

1. 値の削除、挿入がO(log n)で行える。
2. 値の検索がO(log n)で行える。

である。この性質を使ってうまくオーダーを落とすと幸せになれる。特にatcoder 500 ~ 700くらい。

しかし、ここで注意すべき点としては、それ以外の操作は対数時間で行えないことである。
それを示す例をだす。

ABC 127 - F(600)


https://atcoder.jp/contests/abc127/tasks/abc127_f

この問題は、詳細は個別ページを見ればわかるが、つまるところはクエリで値を挿入し、その中央値を調べたいということである。これを上のデータ構造で愚直にイテレータを回すとO(n)かかる。
なぜならば、二分木は値の検索、挿入、削除は対数時間で行える理由としてはたかだか数個の値しか操作しないことにある。前から数えてk個目というものは、順番を確定するために何度も探索しなおさないといけないので全く効率的ではない。(本来ならばO(n log n)かかる気がするけど、STLの実装でイテレータはO(n)で済ませてる気がする)

これを改善する方法として、1つの値の挿入につき中央値周辺の数値はたかだか定数個しか変動しないことに着目すると、1つは半分より小さいデータのみ持つ二分木、もう1つは半分より大きいデータのみ持つ二分木を持てばよい。これならば、値の検索のO(log n)を定数解のみ行うのでオーダーを落とせる。

この問題に限らず、クエリによるデータ挿入時に、観測地点における変化する値の個数が定数的ならば、この考え方は使える。
「データ構造と値の取得」をウィキ内検索
LINE
シェア
Tweet
早稲田大学チームvivid_turtle 知見共有@ ウィキ
記事メニュー

メニュー

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



リンク

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




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

更新履歴

取得中です。


ここを編集
最近更新されたページ
  • 1504日前

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

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

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

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

    ARC096-D
  • 2122日前

    ARC092-D
  • 2122日前

    個別問題知見
  • 2126日前

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

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

    数え上げのDPのさまざま(知らなかったこと)
もっと見る
最近更新されたページ
  • 1504日前

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

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

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

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

    ARC096-D
  • 2122日前

    ARC092-D
  • 2122日前

    個別問題知見
  • 2126日前

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

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

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

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

  1. MadTown GTA (Beta) まとめウィキ
  2. AviUtl2のWiki
  3. R.E.P.O. 日本語解説Wiki
  4. 機動戦士ガンダム EXTREME VS.2 INFINITEBOOST wiki
  5. シュガードール情報まとめウィキ
  6. ソードランページ @ 非公式wiki
  7. ドラゴンボール Sparking! ZERO 攻略Wiki
  8. シミュグラ2Wiki(Simulation Of Grand2)GTARP
  9. 星飼いの詩@ ウィキ
  10. Dark War Survival攻略
もっと見る
人気Wikiランキング

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

  1. アニヲタWiki(仮)
  2. ストグラ まとめ @ウィキ
  3. ゲームカタログ@Wiki ~名作からクソゲーまで~
  4. 初音ミク Wiki
  5. 検索してはいけない言葉 @ ウィキ
  6. 機動戦士ガンダム バトルオペレーション2攻略Wiki 3rd Season
  7. 発車メロディーwiki
  8. Grand Theft Auto V(グランドセフトオート5)GTA5 & GTAオンライン 情報・攻略wiki
  9. オレカバトル アプリ版 @ ウィキ
  10. SDガンダム ジージェネレーションジェネシス 攻略Wiki
もっと見る
全体ページランキング

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

  1. 過去の行動&発言まとめ - 鹿乃つの氏 周辺注意喚起@ウィキ
  2. マイティーストライクフリーダムガンダム - 機動戦士ガンダム EXTREME VS.2 INFINITEBOOST wiki
  3. 魚拓まとめ - 鹿乃つの氏 周辺注意喚起@ウィキ
  4. 参加者一覧 - ストグラ まとめ @ウィキ
  5. 1103環境(遊戯王) - アニヲタWiki(仮)
  6. 前作からの変更点 - 機動戦士ガンダム EXTREME VS.2 INFINITEBOOST wiki
  7. 魔獣トゲイラ - バトルロイヤルR+α ファンフィクション(二次創作など)総合wiki
  8. コレクター・ユイ - アニヲタWiki(仮)
  9. サーヴァント/一覧/クラス別 - Fate/Grand Order @wiki 【FGO】
  10. 画像倉庫 - 鹿乃つの氏 周辺注意喚起@ウィキ
もっと見る

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

2019 AtWiki, Inc.