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

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

転倒数への帰着

最終更新:2019年06月26日 14:30

vivid_turtle

- view
メンバー限定 登録/ログイン
数列における転倒数を a_i > a_j (i < j)である(i, j)の組の数と定義する。例えば{2, 1, 4, 3}ならば(i, j) = (1, 2), (3, 4)で2である。

転倒数性質と求め方


バブルソートの交換回数は、転倒数と同じである。実際、バブルソートの隣り合った数字の交換を1回行うことで、ほかのペアに影響を与えず、互いに交換したペアだけ転倒数の条件を満たさなくなることからわかる。
これは蟻本でより詳しく解説されてる。

実際の転倒数を求めるとき、大体数列の要素は10^5の定数倍までである。なぜならば、データ構造を利用して高速で求められるからである。
愚直に計算するとO(n^2)となるが、

cntという配列を用意し、数字Aが現われてたらcnt[A]++する。
そしてAに対応する転倒数を求める際に、cnt[A+1]~cnt[n_max]の和を求めそれを転倒数として加算する。
これを数列の前から順に行う。

ARC101D - Medians of Medians(700)-転倒数への帰着


中央値と二分探索ARC101Dの続き。

この問題のように、大きいか小さいかの二通りの状態しか必要がない、区間への計算場合は
大きい->+1 小さい->-1と置換して、累積和をとれば、和が0以上の区間を調べればよい(この問題)。
このとき、和が0以上ということは、

{区間の終わり - 区間の初め > 0 つまり
区間の終わり > 区間の初め
}
となる。これは転倒数のアルゴリズムの簡単な応用でとけるのでオーダーは落とせた。
「転倒数への帰着」をウィキ内検索
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. angler - MADTOWNGTAまとめwiki
  3. 参加者一覧 - MadTown GTA (Beta) まとめウィキ
  4. 白狐 - MADTOWNGTAまとめwiki
  5. XVI - MADTOWNGTAまとめwiki
  6. 鬼レンチャン(レベル順) - 鬼レンチャンWiki
  7. Black Rose - MADTOWNGTAまとめwiki
  8. ギャング - MADTOWNGTAまとめwiki
  9. 魔獣トゲイラ - バトルロイヤルR+α ファンフィクション(二次創作など)総合wiki
  10. 参加者一覧 - ストグラ まとめ @ウィキ
もっと見る

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

2019 AtWiki, Inc.