bit全探索で動的計画法を実装する JavaScript

2019-06-10
%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0atcoder%E5%8B%95%E7%9A%84%E8%A8%88%E7%94%BB%E6%B3%95dp%E3%83%93%E3%83%83%E3%83%88%E6%BC%94%E7%AE%97javascript
    

目次

概要

AtCoderとかをやっていると、 動的計画法(DP)、部分和といった問題とかに遭遇したりしますが、1から実装しようとすると面倒だったりします。 (というよりも、再帰処理で書くのが苦手だったりするからです...) こんな時に、ビット演算を用いてパターンをひとまず網羅してから実装することがあります。 ここではJSを例に紹介します。

サンプル1

シフト演算で実装する コード

function main(n) {
    for (let bit = 0; bit < (1 << n); bit++) {
        let row = []
        for (let i = 0; i < n; i++) {
            if (bit & (1 << i)) {
                row.push(i)
            }
        }
        console.log(row)
    }
}
main(4);

このコードの結果は次のようになります。 結果

0
1
0,1
2
0,2
1,2
0,1,2
3
0,3
1,3
0,1,3
2,3
0,2,3
1,2,3
0,1,2,3

部分和の問題を解いてみます。

// [問題]
// 問: [3, 7, 8, 12, 13, 18] の部分和が 27 になる部分集合を求めよ。
// 答: 存在する。[7, 8, 12]

function fetchBitPattern(n, f) {
    for (let bit = 0; bit < (1 << n); bit++) {
        let row = []
        for (let i = 0; i < n; i++) {
            if (bit & (1 << i)) {
                row.push(i)
            }
        }
        f(row)
    }
}

function main() {
    const Q = [3, 7, 8, 12, 13, 18]
    const A = 27
    fetchBitPattern(Q.length, (bit) => {
        let s = 0
        let tmp = []
        for (let i = 0; i < bit.length; i++) {
            s += Q[bit[i]]
            tmp.push(Q[bit[i]])
        }
        if (s === A) {
            console.log(tmp)
        }
    })
}

main()
[7,8,12]

と表示されます。

サンプル2

toStringメソッドで実装する。

function main(n) {
    for (let i = 0; i < Math.pow(2, n); i++) {
        let row = []
        let t = i.toString(2)
        for (let j = t.length; j < n; j++) {
            t = '0' + t
        }
        t = t.split('').map(Number)
        for (let j = 0; j < t.length; j++) {
            if (t[j] === 1) {
                row.push(j)
            }
        }
        console.log(row)
    }
}
main(4)

このコードの結果は次のようになります。

3
2
2,3
1
1,3
1,2
1,2,3
0
0,3
0,2
0,2,3
0,1
0,1,3
0,1,2
0,1,2,3

同じく部分和問題を解いてみます。

// [問題]
// 問: [3, 7, 8, 12, 13, 18] の部分和が 27 になる部分集合を求めよ。
// 答: 存在する。[7, 8, 12]

function fetchBitPattern(n, f) {
    for (let i = 0; i < Math.pow(2, n); i++) {
        let row = []
        let t = i.toString(2)
        for (let j = t.length; j < n; j++) {
            t = '0' + t
        }
        t = t.split('').map(Number)
        for (let j = 0; j < t.length; j++) {
            if (t[j] === 1) {
                row.push(j)
            }
        }
        f(row)
    }
}

function main() {
    const Q = [3, 7, 8, 12, 13, 18]
    const A = 27
    fetchBitPattern(Q.length, (bit) => {
        let s = 0
        let tmp = []
        for (let i = 0; i < bit.length; i++) {
            s += Q[bit[i]]
            tmp.push(Q[bit[i]])
        }
        if (s === A) {
            console.log(tmp)
        }
    })
}

main();
[7,8,12]

と表示されます。

見ての通り、どちらのサンプルもをゴリゴリとループで片付けているので必ずしも効率的ではないと思います。

参考

https://qiita.com/drken/items/7c6ff2aa4d8fce1c9361

https://ja.stackoverflow.com/questions/49702/%E3%83%93%E3%83%83%E3%83%88dp%E3%81%AE%E6%80%9D%E8%80%83%E5%9B%9E%E8%B7%AF%E3%81%AB%E3%81%A4%E3%81%84%E3%81%A6

    
s-yoshiki
s-yoshiki
githubtwitterqiita
Web作ってますが、インタラクティブなプログラミングも好きです。
JavaScript / Vue / node.js / PHP / AWS / OpenCV

関連記事

AWS Amplify に Next.js (SSG) で作ったアプリをデプロイする
はじめに 操作 Next.js (React) アプリの作成、Gitへのプッシュ AWS Amplifyでプロジェクト作成 参考にしたサイト この記事では、React / Next.js アプリケーションを作成し、AWS Amplify…

Typescriptに入門した
初期作業 とりあえずHello World 初期作業 typescript環境を作っていきます。 とりあえずHello World まず、次のサンプルコードを作成します。 typescriptファイルをビルドします。

Vue/Nuxt.js 触ってた人が Next.js に入門する
はじめに 実施環境 学習ガイド Create a Next.js App Navigate Between Pages ページの作成 リンク Assets, Metadata, and CSS Assets メタデータ CSS…

10進数から2進数 2進数から10進数への変換 JavaScript
10進数から2進数 2進数から10進数 テスト 10進数から2進数、2進数から10進数への変換を行うJavaScriptのコードの紹介。 JSの場合、10進数から2進数への変換はメソッド。2進数から1…

JavaScriptの配列ショートハンド (AtCoder用)

JavaScriptでワーシャルフロイド法を実装
AtCoder ABC012 D問題 D - バスと避けられない運命 解説 実装 AtCoder ABC012 の D問題でワーシャルフロイド法が利用できる問題が出てきたので、 JavaScriptで実装しました。 AtCoder ABC012 D問題 D…

JavaScriptによる2分探索(バイナリサーチ) のサンプルコード
2分探索について ソース 参考 JavaScriptで2分探索(バイナリサーチ)を実装してみました。…

Firebase + Nuxt で認証付きページを作るときに参考にしたいところ
Webアプリケーションのセッション管理にJWT導入を検討する際の考え方 Service Worker によるセッション管理 ユーザー セッションの管理 Nuxt.jsとFirebaseでSPA×SSR×PWA×サーバーレスを実現する CookieとセッションとJWT SSR…

JavaScriptで幅優先探索 (bfs) を実装する
bfsソースコード 前提 bfs関数 テストコード JavaScriptで幅優先探索 (bfs) を実装し簡単な最短経路の探索問題を解いてみました。 AtCoderの問題を参考にしています bfsソースコード 前提 bfs 関数の定義について 引数 table…

JavaScriptでbig-integerでできること
定数 メソッド abs add, plus and bitLength compare compareTo compareAmb divide, over divmod equals, eq greater, gt greaterOrEquals, geq…

最新の投稿

UNIXドメインソケット通信 vs INETドメインソケット通信 php-fpmで動作させる場合の違いについて
結論 ソケット通信について ソケットについて ソケット通信の種類 UNIXドメインソケット通信を行う場合のメリット 参考にしたサイト php-fpm の設定方法で調べた際にIPとポートで設定するパターンとUNIX…

AWS Amplify に Next.js (SSG) で作ったアプリをデプロイする
はじめに 操作 Next.js (React) アプリの作成、Gitへのプッシュ AWS Amplifyでプロジェクト作成 参考にしたサイト この記事では、React / Next.js アプリケーションを作成し、AWS Amplify…

Typescriptに入門した
初期作業 とりあえずHello World 初期作業 typescript環境を作っていきます。 とりあえずHello World まず、次のサンプルコードを作成します。 typescriptファイルをビルドします。

Vue/Nuxt.js 触ってた人が Next.js に入門する
はじめに 実施環境 学習ガイド Create a Next.js App Navigate Between Pages ページの作成 リンク Assets, Metadata, and CSS Assets メタデータ CSS…

PHP-Parser で PHP5からPHP7で動くコードに自動修正するツールが作る夢をみた
ツールが備える機能条件 PHP-Parser について PHP-Parser の簡単なサンプル ASTオブジェクトの置換・変更 PHP5からPHP7への変更内容を実装する ex1 includeパスを変更する ex2 例外クラスを Exception…

PHP5からPHP7への移行ツールを作るための解析・自動修正ツールを調べる
PHP5からPHP7への下位互換のない機能 使えそうなツールの洗い出し PHPStan phan php7cc php7mar php-to-7-aid Rector php-ast PHP-Parser まとめ 追記 (2021/01/0…

CentOS8にDNFでPerl5.30のインストール
Modularityについて Perl5.30インストール dnf module でハマったところ その他 Perl5.26の場合 Perl5.24の場合 CentOS8 or CentOS Streamに Perl5.30をDNF…

homebrew-core is a shallow clone. 対処法
homebrew で homebrew-core is a shallow clone.と 表示されたエラー 対処法 homebrew で homebrew-core is a shallow clone.と homebrewでupdate…

centos-streamのDockerコンテナイメージを作成した
背景 centos-stream コンテナのビルド & インストール 参考にしたところ centos-streamのDockerコンテナイメージを作成しました。 背景 CentOS8からCentOS Stream…

CentOS8でEPELとPowerToolsリポジトリの有効化
EPELとPowerToolsについて EPEL PowerTools EPELとPowerToolsの有効化 Powertoolsの有効化 epel-releaseのインストール 参考にしたサイト CentOS8でEPELとPowerTools…

Tags

Dates

© 2021   404 motivation not found