2018-04-23

MacPorts で Python3系をインストール

for Mac

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 のチュートリアルで十分と教えていただいたので眺めてみたいと思います。
Python で ABC の A を解けるくらいになりたい(目標)

2018-04-21

いろいろな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本など

2018-03-04

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

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)$ 時間となります。

コード

提出コード：Submission #1970985 - AtCoder Beginner Contest 015

2018-01-21

Max値取得｜動的計画法( DP )

動的計画法

動的計画法 ( DP )の学習として解きました。
例題のねらい：動的計画法におけるメモ配列とDPテーブルの違いを確認する。

問題： $N$ 要素の int 型配列 $A$ が与えられる． $A$ の最大値を DP で求めよ

問題制約は特になかったので、適当に。( $1 \leq N \leq 10^6$ くらい？)

1. メモ化再帰編

解の再帰的定義

　 $N$ 個の値の中から最大値を返す関数 $\mathrm rec(n)$ を定義します。

$\begin{equation} 　\mathrm rec(1) = A_0\\ 　\mathrm rec(n)= \max\{\mathrm rec( n - 1 ),\: A_{n-1}\}　( 1 < n)\\ \end{equation}$

正当性の証明

$N = 1$ のとき
1 以下の要素は 1 つしかない為、最大値は $A_0$ となる。
$N > 1$ のとき
配列 $A_{n-1}$ までの最大値が求まると仮定すると、 $A_{n-1}$ までの最大値と $A_n$ を比較すれば、 $A_n$ までの最大値が求まり、よって任意の自然数 $N$ について $\mathrm rec(N)$ は、配列 $A$ から最大値を求める再帰関数として成立する。

計算量

main 関数は std::vector::resize に $O(N)$ 、再帰関数の呼び出しに $O(1)$ 時間。
rec 関数は、訪問済判定の if 文、訪問済だった場合、memo した値を返すのにそれぞれ $O(1)$ 時間。
基底ケース部分は、 if 文、res を返すのにそれぞれ $O(1)$ 時間。再帰ケース部分は std::max *1 を使って大小比較 1 回につき $O(1)$ 時間かかり、それを再帰関数で $N$ 回繰り返すので $O(N)$ 時間。プログラム全体では $O(N)$ 時間。

コード

vector<int> memo( 100000 + 1, -1 );
int N, res;
vector<int> A;
int rec( int i )
{
    int &res = memo[ i ];
    if( res != -1 )
    {
        return res;
    }
    //基底ケース
    if( i == 1 )
    {
        return res = A[ 0 ];
    }
    //再帰ケース
    return res = max( rec( i - 1 ), A[ i - 1 ] );
}
int main()
{
    cin >> N;
    A.resize( N );
    for( auto &x : A )
    {
        cin >> x;
    }
    cout << rec( N ) << endl;
    return 0;
}

実行コード：[Wandbox]三へ( へ՞ਊ ՞)へﾊｯﾊｯ

2. Loop DP 編

　次にメモ化再帰編を元に Loop DP 版を書きました。

計算量

DP 部分は std::max を使っての大小比較 1 回につき $O(1)$ 時間を loop で $N - 1$ 回繰り返すので、 $O(N)$ 時間。
プログラム全体では $O(N)$ 時間となる。

int main()
{
    int N;
    cin >> N;
    vector<int> A( N );
    for( auto &x : A )
    {
        cin >> x;
    }
    vector<int> dp( 100000 + 1 );
    dp[ 1 ] = A[ 0 ];
    for( int i = 2; i <= N; i++ )
    {
        dp[ i ] = max( dp[ i - 1 ], A[ i - 1 ] );
    }
    cout << dp[ N ] << endl;
    return 0;
}

実行コード：[Wandbox]三へ( へ՞ਊ ՞)へﾊｯﾊｯ

3. 学習まとめ

メモ化再帰も loop DP も計算結果を保存して次の計算に使うという本質的な所は同じで、単に実装方法が異なるだけということが例題から良く判りました(おわり)

*1:max - C++ Reference

2017-12-31

2017年進捗大反省会

日記

昨年同様、今年1年の振り返り記事を残します。
独り反省会なので反省をポジティブにしていきます。

C++ について

C++を勉強しだして2年が経ちました。
まだまだ知識が浅く、基礎的な事も解らなかったり、知識が定着していなかったりするので、
猫C++ をもう一度軽くやり直したりしていました。
全体としては、今年は言語自体の勉強はあまり深くしなかったです。

学習方法として変わってきた事としては、学習 1 年目の頃は誰かが噛み砕いて書いているような Blog とかを好んで見ていたのですが、最近では解らない事があると C++ reference や C++ ポケットリファレンス(本)を良く見るようになりました。
~~少しは C++ に慣れてきた...(？)~~

競プロについて

アルゴリズム

今年はアルゴリズムの勉強を主にしていました。
初めはTLE本で問題を解きながら進めていたのですが、いつの間にか離脱...。
本に沿って勉強していると、解らないまま進んでしまえるので良くない気がして、途中から本で勉強を進めるのはやめました。*1
TLE本, 蟻本やチーター本は自分には難しく、全然勉強が進まなくなりました。

それからは、アルゴリズム理論の本を読んだり、自分に最適化された(易しい)資料を読む事で少しずつまた勉強を進める事ができました。
↑画像の本2冊は知識が何もない自分にも解りやすかった2冊で、学習の助けとなりました。
何事も一つひとつ自分の中で納得しないと進めない面倒なタイプなので*2、実装前に「動的計画法とは」みたいな勉強から始める方が自分には合っている気がしました。

本に沿って勉強するのをやめたので、主に yukicoder の問題を使って学習していました。
(同じ問題を何度も何度も解き直しをしていたので、yukicoder管理人のyukiさんには不審に思われていたかも知れない...。)

DFSも書けるようになってきたので、最近はずーーっとDP(knapsack, 数え上げ)の勉強を主にしています。

AC数

今年は考察ばかりに時間を割いていたので、AC数は少なく終わりました。
主に解いていた AtCoder と yukicoder 合わせて 140 くらいでしょうか...。
でも来年はもっと少ない予感しかない。

コンテスト

今年はコンテストもあまり参加しなくなってしまった。
理由は色々あったのですが、解決済みなので来年はもう少し参加したいですね。
あと運良く ABC で初めて全完出来たんですよ。

わーい！初めてABCで全完できたー！
— cww (@chiwawa_star) 2017年9月2日

しかしこれは罠でこの後プロからこのケースで D 落ちますみたいな指摘を受け凹む(現実は厳しい)(でもそういう指摘はうれしい)
来年も地道に ABC 頑張りたいな(希望)

LaTeXについて

今年は $LaTeX$ と出会いました。
始まりは Blog の数式部分が読みづらいよというご指摘を頂いたことでした。
指摘されるまで全然意識していなかったのですが、確かに他の人の Blog を見るとちゃんと数式部分は LaTeX で書かれていました。
別に強く勧められた訳ではなく、なんとなく MacTeX を DL して使ってみたら凄く直感的で感動しました。マークアップで文書作成出来るって凄い...！楽しい！！みたいな感想しかなかった。
自分は Adobe 生まれ Adobe 育ちなので、これまで文書作成は Illustrator だったのですが(レポート類も)、こんなに便利なものが世の中にあるのか...みたいな衝撃でした。
$LaTeX$ は最高。

2018年の課題

アルゴリズムの勉強

2018年はもうこれしかないと思っていて、逆に他の事する時間もなさそう。
全振りしてしまっていいかは謎ですが...。
アルゴリズムの勉強法はまだ自分の中でしっくり来ていなくて、どう勉強を進めたら良いのかも模索中なのですが、自分の場合、習得を急いでいる訳ではないので楽しく勉強したいなと思っています。

とにかく動的計画法をマスターしないと！
本を良く読み理解して勉強する！解らない事は解るまで調べる！

考察する

DP の問題もそうなんですが、典型的な問題が解けてもちょっと応用っぽくなると解けなかったりするので、深く考察するようにしたいです。

Effective に C++ を書く

C++ もまだまだ初心者以下なのでちゃんと勉強する。(Effective C++ と Effective STL を買った)
効率的なコードを書けるようになりたいです。

解いた問題の記事を書く

復習という意味で、簡単な問題でも出来ればしっかり書きたいです。
今年は結構書いたんですが、殆どが下書き状態で終わったので...。
Blog を書きながら考察してたりして、実装に入ってしまうと放置になってしまうの良くないので最後まで書きたいですね。
記事を書くと「計算量違うよ！」とか「もっと良い方法あるよ！」等、わりとお声がけいただけるので、本当に有り難いです。(お気付きの点があれば＠ください！)

まとめ

1年間何してたんだろう...(成長なし)
来年は DP を頑張る！それだけ！

余談

実は夏頃に転職しました。
少しだけキャリアチェンジもしました。(チェンジと言う程でもないけれど)
新しい職場の開発環境(git)にもやっと慣れて...もいないのですが、炎上案件に放り込まれ、毎日楽しいです(真顔)

*1: 1つの単元が理解できて解けるようになったらまた本で学習を進めます。

*2:そのわりには適当です。

① 普通に普通の 埋めDP

定義

のとき

のとき

のとき

漸化式

コード

② -INF で埋めるDP

定義

のとき

のとき

のとき

のとき

漸化式

コード

まとめ

普通の DP と INF 埋め DP の違う点

題意

考察

DPテーブルの定義

漸化式の定義

計算量

コード

1. メモ化再帰編

解の再帰的定義

正当性の証明

計算量

コード

2. Loop DP 編

計算量

3. 学習まとめ

C++ について

競プロについて

アルゴリズム

AC数

コンテスト

LaTeXについて

2018年の課題

まとめ

余談

① 普通に普通の $0$ 埋めDP

$i = 0， j \geq 0$ のとき

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

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

$i = 0，j = 0$ のとき

$i = 0，j > 0$ のとき

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

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