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

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

bitsetでの定数倍改善

最終更新:2021年06月04日 10:24

匿名ユーザー

- view
だれでも歓迎! 編集
動的計画法での鉄則として蟻本にも書かれてるものだが、

bool値のDPは同じ計算量より多くの情報を保持できるので、オーダーが落ちやすい!

しかし世の中にはいくつかこれ以上オーダーが落ちないものもある。落ちやすいは100%落ちるというわけではない。それらを解く際に有効なテクニックの一つとして、真偽値の定数倍高速化ではC++のbitsetを用いるというのがある。

bitsetの使い方


内部的にはlong long をいくつかつなげた形で取られている。よって、1桁1桁に対していくつか左にずらすなどの操作は内部的にはlong long 間の演算となり、およそ1/64倍の定数倍高速化となる。

bitsetを利用した定数倍高速化テクニック


例

長さN(1 <= N <= 2000)の数列(1 <= A_i <= 2000)の部分列のうち、X(1 <= X <= 2000 * 2000)になるものが存在するか?

次のように動的計画法で解くと考えつくだろう。

bool dp[i][j] := i項目まで見て、選んだ数字の和がjになれるかどうか

普通に計算すると、O(N^2max(A))かかり、TLEとなる。
しかし、真偽値の更新のためbitsetを利用すると、次のようにきれいに書ける。

#include<bitset>
 
......
 
//更新式は
// dp[i + 1][j] |= dp[i][j]
// dp[i + 1][j + A[i]] |= dp[i][j]
//更新式から、iのDPの次元は配列自身の使いまわしで問題ないとわかる。
 
std::bitset<2010 * 2010> dp;//<>にサイズを指定して宣言する。
//dp[0] = 1;//メリットの一つでもある、配列と同じ感覚で扱えるというのがある。
//初期化ではゼロうめされてる。
 
for(int i = 0; i < N; i++){
    dp = dp | (dp << A[i]);
    //添え字のdp[a]のaは、aが作れるか否かなので、現時点での0~MAXまでの作れるか否かがわかる。
    //結局のところ、すべての現時点で作れてるものに対して、A[i]を足したら作れるものを考えるので
    //現時点のdp配列をA[i]個だけシフトそのまま流用すればよい。
 
    //作りたい数         |0 |1 |2 |3 |4 |5 ...
    //現時点での状況     |1 |0 |0 |1 |0 |1 ...
    //A[i]==2のとき
    //                   |0 |0 |1 |0 |0 |1 ...
    //が元の状況でA[i]==2を採用した時の作れるか否かの情報
    //一度作れればtrueとなるので、
    //もともとのdpのbit値に、A[i]分だけシフトしたbit配列との論理和を足せば更新ができる。
 
}
 
cout << (dp[X] ? "OK", "NG") << endl;
 
 

タグ:

+ タグ編集
  • タグ:
タグの更新に失敗しました
エラーが発生しました。ページを更新してください。
ページを更新
「bitsetでの定数倍改善」をウィキ内検索
LINE
シェア
Tweet
早稲田大学チームvivid_turtle 知見共有@ ウィキ
記事メニュー

メニュー

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



リンク

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




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

更新履歴

取得中です。


ここを編集
人気記事ランキング
  1. 部分列に関する数え上げ
  2. 無限を有限に落とすには(数学編)
  3. プラグイン
もっと見る
最近更新されたページ
  • 1510日前

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

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

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

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

    ARC096-D
  • 2128日前

    ARC092-D
  • 2128日前

    個別問題知見
  • 2132日前

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

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

    数え上げのDPのさまざま(知らなかったこと)
もっと見る
人気記事ランキング
  1. 部分列に関する数え上げ
  2. 無限を有限に落とすには(数学編)
  3. プラグイン
もっと見る
最近更新されたページ
  • 1510日前

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

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

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

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

    ARC096-D
  • 2128日前

    ARC092-D
  • 2128日前

    個別問題知見
  • 2132日前

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

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

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

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

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

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

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

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

  1. 参加者一覧 - ストグラ まとめ @ウィキ
  2. Trickster - ストグラ まとめ @ウィキ
  3. 暦家 - ストグラ まとめ @ウィキ
  4. 魔獣トゲイラ - バトルロイヤルR+α ファンフィクション(二次創作など)総合wiki
  5. hantasma - ストグラ まとめ @ウィキ
  6. ギャング - ストグラ まとめ @ウィキ
  7. スーパーマン(2025年の映画) - アニヲタWiki(仮)
  8. RqteL - ストグラ まとめ @ウィキ
  9. 機体一覧 - 機動戦士ガンダム EXTREME VS.2 INFINITEBOOST wiki
  10. 過去の行動&発言まとめ - 鹿乃つの氏 周辺注意喚起@ウィキ
もっと見る

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

2019 AtWiki, Inc.