C++競プロ学習日記(仮)

( 学習記録であり解説Blogではないです )

std::next_permutation|C++|順列

std::next_permutation という関数を覚えたのでメモ

std::next_permutation は、[first, last) の範囲を次の順列に変換する関数です。*1
これを使うと配列内の要素の順列を簡単に列挙することができます。
全ての順列を取得する場合は、関数に最初に与える範囲が昇順にソート済みになっている必要があります。

全列挙例
#include <bits/stdc++.h>
using namespace std;
int main()
{
    vector<int> v{ 1, 2, 3 }; //要素は昇順にソートしておく
    
    for( int i = 0; i < 6; ++i )
    {
        for( auto &x : v )
        {
            cout << x << " ";
        }
        cout << endl;
        next_permutation( begin( v ), end( v ) ); //次の順列が生成される
    }
    return 0;
}

実行コード:[Wandbox]三へ( へ՞ਊ ՞)へ ハッハッ

出力
1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 1 2 
3 2 1 

std::next_permutation については下記サイトで解りやすく説明されています。
参考:順列生成 next_permutation, prev_permutation 入門


No.676 C0nvertPr0b1em|yukicoder|std::replace_if

C++ の algorithm ヘッダにある std::replace_if を初めて使って解いたのでメモ。

解いた問題:No.676 C0nvertPr0b1em - yukicoder ★1


題意

  • 英文字列 S が与えられる。
  • S に含まれる英字  I,l を 数字の  1 に、 O,o を 数字の  0 に置き換えたものを出力する。
  •  |S| \leq 10^3


考察

特定の英字を探し、一致したら数字に置き換えるという易しい問題です。
loop で一文字ずつ見ていっても解けますが、今回は std::replace_if を使って解きました。

std::replace_if は、「条件を満たす要素を指定された値に置き換える。*1 」という機能を提供するSTLです。

std::replace_if( 検索開始位置, 検索終了位置, 置換条件, 置換する値 )

同じような STLstd::replace *2 がありますが、std::replace の場合、「指定された値と一致する要素を指定された値に置き換える」ことしか出来ません。( e.g. 文字列に含まれた全ての A を 1 に置換する...など )
ですので、今回の問題のように置換したい条件がある場合は、std::replace_if を使うと第三引数( 置換条件 )にラムダ式 *3 を使えて便利です。

第三引数に使うラムダ

// 文字が I, または l のとき true を返す
[]( const char &c ){ return c == 'I' || c == 'l'; }

// 文字が O, または o のとき true を返す
[]( const char &c ){ return c == 'O' || c == 'o'; }

注意点として、今回は英字を数字に置換するので、置換する数字の方を第四引数で指定するとき同じ char 型で渡す必要があります。

第四引数は置換する要素と同じ型にする

replace_if( ALL( S ), []( const char &c ){ return c == 'I' || c == 'l'; }, '1' );
replace_if( ALL( S ), []( const char &c ){ return c == 'O' || c == 'o'; }, '0' );

 


コード

#include <bits/stdc++.h>
using namespace std;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
int main()
{
    string S;
    cin >> S;
    replace_if( begin( S ), end( S ), []( const char &c ){ return c == 'I' || c == 'l'; }, '1' );
    replace_if( begin( S ), end( S ), []( const char &c ){ return c == 'O' || c == 'o'; }, '0' );
    cout << S << endl;
    return 0;
}

提出:https://yukicoder.me/problems/no/676
別解:https://yukicoder.me/submissions/255892 ( loop解 )
 


計算量

std::replace_if の計算量は 「正確に last - first 回の述語の適用を行う。」となっている。
この問題の場合、文字数分の比較(条件判定)が発生するので、std::replace_if 1 回の走査につき  O(|S|).
全体では  O(|S|) となる。


参考

MacPorts で Python3系をインストール

Mac で少しだけ Python を実行できる環境を整えたので自分用メモ。



gcc を入れる時に使った MacPorts が既にインストールされているので、それを利用します。
まずはターミナルで python --version を実行すると、version 2.7.10 と表示されました。
Mac には Default で Python 2 系が入っているようですが、これから Python を新しく学習するには 3 系が良いようなので 3 系をインストールしていきます。

python --version
Python 2.7.10

↓ まずは、MacPorts をアップデート。

sudo port selfupdate

↓ 次に、Ports のリストを最新にする。

sudo port sync

Python パッケージを検索すると、色々大量に出てきますが、今回は python36 @3.6.5 (lang) をインストールします。

port search python*

python36 をインストール。

sudo port install python36

python で python3.6.5 が実行されるように設定する。
正しく設定されると Selecting 'python36' for 'python' succeeded. 'python36' is now active. と表示される。

sudo port select --set python python36
Selecting 'python36' for 'python' succeeded. 'python36' is now active.

↓ 最後に Python 3.6.5 が正しくインストールされたか python --version してみるとちゃんと Python 3.6.5 になっている事が確認できる。

python --version
Python 3.6.5

次に Python のパッケージ管理システムをインストールする。(使い方はまだ解らないけど)
以下を 1 行ずつ実行する。

sudo port install py36-pip
sudo port select --set pip pip36



これで一旦終わり。
Python が実行できるかコードを書いてみる。
vim ではろーわーるど書きます。
書いたら、ファイル名を適当に test.py とかにして任意の場所に保存します。

print ("Hello World")

test.py を任意のフォルダに入れた場合、そこのディレクトリに cd で移動してから、以下を実行する。

python test.py

はろーわーるど成功!

Hello World



特につまずく事なく Python3.6.5 をインストールできました。
ライブラリ系など他に必要なものがあれば、ゆくゆく整えて行きたいです。

Python の本を何か買おうと思ったのですけど、3.6.5 Documentationチュートリアルで十分と教えていただいたので眺めてみたいと思います。
PythonABC の A を解けるくらいになりたい(目標)

いろいろなDP|動的計画法|ナップザック

DP 配列を- INF で埋めた DP が解らなかったのでナップザック問題を使って比較してみました。

使う問題はこれナップザック問題 | 動的計画法 | Aizu Online Judge


① 普通に普通の  0 埋めDP

まずは普通に本 *1 で学習したナップザックで解きます。

定義

dp[ i 個の荷物を考慮して ][ 重さが j 以下のとき ] := 達成可能な価値の和の最大値

 i = 0, j \geq 0 のとき

 0 個の荷物を考慮したとき、ナップザックには何も入っていないので重さ  0 ,価値の和も  0 となる。
重さ  0 ,価値  0 の状態は任意の  j に対して「重さ  j 以下」の条件を満たすため、任意の  j に対して dp[ 0 ][ j ] := 0 となる。

 i > 0, j \geq w_{i-1} のとき

 i - 1 番目の荷物の重さ  w_{i-1}j 以下の場合、ナップザックに  i - 1 番目の荷物を詰め込むことができると考え、 i - 1 番目の荷物をナップザックに入れる場合入れない場合を比較し、より価値の和が大きい方を最大値として更新していきます。

入れる場合
 i 番目の荷物を除外し、 i - 1 番目までの荷物のみで、重さ  j - w_{i-1} 以下のときの価値の最大値が得られるとすると、そこに  i 番目の荷物の重さ  w_{i-1} を加えると重さ  j 以下のときの価値の最大値の候補が得られる。

入れない場合
 i 番目の荷物を除外し、 i - 1 番目までの荷物のみで、重さ  j - w_{i-1} 以下のときの価値の最大値が得られるとすると、そこに  i 番目の荷物を加えない場合の価値の最大値は、 i 番目の荷物を除外した価値の和の最大値と同じになる。

 i > 0, j < w_{i-1} のとき

 i - 1 番目の荷物の重さ  w_{i-1} j を超える場合、「重さ  j 以下のとき」という条件を満たさないので、上記の入れない場合と同様に  i 番目の荷物を除外した価値の和の最大値と同じになる。

以上の計算が終わると dp[ N ][ W ] で定義のとおり価値の和の最大値が求まります。

漸化式

\begin{equation}
dp(0,j) = 0\\
dp(i, j)= \left \{
    \begin{array}{l}
        \mathrm {\rm max}\{dp( i - 1, j ), dp( i - 1, j - w_{i-1} ) + v_{i-1} \}&( j \geq w_{i-1} )\\
        dp( i - 1, j )&( j < w_{i-1} )\\
    \end{array}
\right.
\end{equation}
 

コード
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0; i<(n); i++)
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
int main()
{
    int N, W;
    cin >> N >> W;
    vector<int> v( N ), w( N );
    REP( i, N )
    {
        cin >> v[ i ] >> w[ i ];
    }
    vector<vector<int>> dp( N + 1, vector<int>( 100001 ) );
    for( int i = 1; i <= N; ++i )
    {
        for( int j = 0; j <= W; ++j )
        {
            if( j >= w[ i - 1 ] )
            {
                dp[ i ][ j ] = max( dp[ i - 1 ][ j ], dp[ i - 1 ][ j - w[ i - 1 ] ] + v[ i - 1 ] );
            }
            else
            {
                dp[ i ][ j ] = dp[ i - 1 ][ j ];
            }
        }
    }
    cout << dp[ N ][ W ] << endl;
    return 0;
}

 


② -INF で埋めるDP

次に、DP配列を予め -INF で埋めるDPを考えます。

定義
  • dp[ i 個の荷物を考慮して ][ 重さが j の時 ] := 達成可能な価値の和の最大値
  • 達成可能か否かを区別できるように、DP 配列を予め解に成り得ない値で埋めておく。
    価値の和の最大値となるような値が存在しない場合は解として成り得ない値になっていてほしいので、この問題の場合、制約を見ると、 N \leq 100, v_i \leq 1,000 なので、 価値の最大値 1,000 100 回足しても非負の整数にならない  -10^5 より小さな値で初期化します。
 i = 0,j = 0 のとき

①のケースと同様に, 0 個の荷物で実現可能な唯一の状態は重さ  0 価値  0 である。
従って、dp[ 0 ][ 0 ] := 0 となる。

 i = 0,j > 0 のとき

 j > 0 なる  j については, 0 個の荷物では正の重さを実現できないため、実行不可能な状態である。
よって、重さとして有り得ない値(かつ、特別扱いせずに計算を進めても有り得ない値のままでいてくれる)-INF で初期化する。

 i > 0,j \geq w_{i-1} のとき

 i - 1 番目の荷物の重さ  w_{i-1}j 以下の場合、ナップザックに荷物を詰め込むことができると考え、 i - 1 番目の荷物をナップザックに入れる場合入れない場合を比較し、より価値の和が大きい方を最大値として更新していきます。

入れる場合
 i 番目の荷物を除外し、 i - 1 番目までの荷物のみで、重さ  j - w_{i-1} のときの価値の最大値が得られるとすると、そこに  i 番目の荷物の重さ  w_{i-1} を加えると重さ  j のときの価値の最大値が得られる。

入れない場合
 i 番目の荷物を除外し、 i - 1 番目までの荷物のみで、重さ  j - w_{i-1} のときの価値の最大値が得られるとすると、そこに  i 番目の荷物を加えない場合の価値の最大値は、 i 番目の荷物を除外した価値の和の最大値と同じになる。

 i > 0, j < w_{i-1} のとき

 i - 1 番目の荷物の重さ  w_{i-1} j を超える場合、「重さ  j のとき」という条件を満たさないので、上記の入れない場合と同様に  i 番目の荷物を除外した価値の和の最大値と同じになる。

以上の計算が終わると、 N 個全ての荷物を考慮した各重さ j のときの価値の和の最大値が dp[ N ][ j ] で得られますので、dp[ N ][ j ] の行の MAX を取ると答えが求まります。

漸化式

\begin{equation}
dp(0, j)= \left \{
    \begin{array}{l}
        0&( j = 0 )\\
        -\infty&( j > 0 )\\
    \end{array}
\right.
\end{equation}

\begin{equation}
dp(i, j)= \left \{
    \begin{array}{l}
        \mathrm {\rm max}\{dp( i - 1, j ), dp( i - 1, j - w_{i-1} ) + v_{i-1} \}&( j \geq w_{i-1} )\\
        dp( i - 1, j )&( j < w_{i-1} )\\
    \end{array}
\right.
\end{equation}

コード
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0; i<(n); i++)
#define ALL(n) begin(n),end(n)
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
const int INF = 10000000;
int main()
{
    int N, W;
    cin >> N >> W;
    vector<int> v( N ), w( N );
    REP( i, N )
    {
        cin >> v[ i ] >> w[ i ];
    }
    vector<vector<int>> dp( N + 1, vector<int>( 10001, -INF ) );
    dp[ 0 ][ 0 ] = 0;
    for( int i = 1; i <= N; ++i )
    {
        for( int j = 0; j <= W; ++j )
        {
            if( j >= w[ i - 1 ] )
            {
                dp[ i ][ j ] = max( dp[ i - 1 ][ j ], dp[ i - 1 ][ j - w[ i - 1 ] ] + v[ i - 1 ] );
            }
            else
            {
                dp[ i ][ j ] = dp[ i - 1 ][ j ];
            }
        }
    }
    cout << *max_element( ALL( dp.back() ) ) << endl;
    return 0;
}

コード:https://wandbox.org/permlink/RK5gfohRlQwd7cKE



まとめ

普通の DP と INF 埋め DP の違う点
  • ①の DP が  j 以下の価値の最大値を求めるのに対し、② の -INF で埋める DP は 重さがちょうど  j の時の価値の和の最大値を求めるという違いがある事が判った。
  • また、それにより計算後の解の得方にも違いがある事が判った。



*1:TLE本など

ABC015 D - 高橋くんの苦悩|AtCoder

D - 高橋くんの苦悩 を解きました。

題意

この問題は良くある knapsack 問題に置き換えて考えられる為、本当の題意は省略します。
与えられる変数と値は以下のように置き換えて考えます。

  • W… knapsack の容量
  • N … 与えられる荷物の数
  • K … knapsack に詰めれる荷物の個数
  • A_i… 各荷物の重さ
  • B_i… 各荷物の価値
  •  N 個の荷物とその荷物の重さ A_i と荷物の価値 B_i が与えられる。
  • knapsack の容量 W と knapsack に入る荷物の個数  K が与えられるので、これらを超えないように荷物を選んだ時の価値の最大値を出力する。

考察

全探索で考えると、 N 個の中から  K 個選んで knapsack に荷物を入れる・入れないを全て試すと  O( 2^N) 時間のアルゴリズムになります。制約を見てみると 1 \leq N \leq 50 なので全探索ではとても間に合わない為、DPで考えていきます。

まず、問題を読むと今まで解いてきた易しい、かつ、典型的な knapsack と 1 点違う箇所がありました。
それは、knapsack の容量制限に加えて、荷物の個数制限がある点です。
荷物の個数を管理する引数が増えるだけなので、loop DP で書く場合は 3 次元 DP で解けば良さそうでした。

DPテーブルの定義

 dp[ i ][ j ][ k ] :=  i 番目以下の荷物から j 個以下選び、重さ k W を超えないように荷物を選んだ時の価値の最大値

漸化式の定義

\begin{equation}
\mathrm f(0,0,k) = 0\\
\mathrm {\rm f}(i, j, k)= \left \{
    \begin{array}{l}
        \mathrm {\rm max}\{ {\rm dp}( i - 1, j, k ), \:{\rm dp}( i - 1, j - 1, k ), \:{\rm dp}( i - 1, j - 1, k - A_{i-1} ) + B_{i-1} \}&( j \geq A_{i-1} )\\
        \mathrm {\rm max}\{ {\rm dp}( i - 1, j, k ), \:{\rm dp}( i - 1, j - 1, k ) \}&(otherwise)\\
    \end{array}
\right.
\end{equation}

計算量

DP 部分は、std::max での比較に O(1) 時間かかり、それを 3 重 loop で N・K・W 回繰り返すので、 O(NKW) 時間。プログラム全体では O(NKW) 時間となります。