2019-01-04

2018年進捗大反省会

日記

年が明けてしまったけれど、2018年振り返り進捗大反省記事を書きます。

競プロ

2018年は問題数にしたら 100 問ちょっとしか解けなかった。(理由は後述)
過去最小値な気もするけど、2018年前半は DP 問題を主に勉強してました。
2019年は ABC - C, D 埋めをしたいですね。

言語

C++ 以外にも色々な言語を少しずつ触ってみました。

Python で ABC A 問題を解いてみた
Java で ABC A 問題を解いてみた
Java で初めて競プロ以外のコードを書いてみた(!!!)
Swift を最近始めてみた(アプリの勉強)

エディタ

VSCode で C++ 書けるように環境を作った
- Online Judge のサンプルを VSCode 上で自動取得・実行できるようになって嬉しい
- 参考：競技プログラミングのための補助ツールを作った
Java を書くために IntelliJ IDEA も使った(Java は補完がないとつらいね)
Swift を書く為、また Xcode を使うことになった(昔 C++ を Xcode で書いてた時があった)
とはいえ、WandBox は最高

仕事

一昨年夏に転職したけれど、夏に退職してしまった。(ちょうど1年くらい)
開発環境が最高だったけれど、パワハラが横行していて思ったような仕事ができず本質的ではない気がしてきて辞めた。(私が直接的にパワハラを受けた訳ではない)

しかし、ここでの一年は色々な事を経験させて貰えたり、学習したりで大変満足している。
( git フローも覚えたよ！)
残業をたくさんして家での勉強時間が減ってしまったのは唯一残念だった。
家で競プロする時間がないのが思いの外ストレスで、辞める理由の1つに入るくらいだった。

新しい職場は、前よりさらに刺激的です。
使用ツールがガラッと変わったので、一から色々覚え直ししているのですけど、
最高のメンターにより、毎日が学びで楽しいです。
定時で帰れることも多く、ドラッグストアが開いている時間に帰れるのがうれしい。

スプラトゥーン2

仕事を辞めてから2ヶ月半くらい毎日スプラトゥーン2をして遊んでいた。
こんなに継続的にゲームをしたのは人生初だった。
ゲーム禁止家庭で育ったので、ゲームが絶望的に下手...でも下手なりに楽しめるため楽しい。
プレイ時間もそろそろ1'500時間に届きそう(でも下手)

競プロ界隈の人といつもわいわい遊んでる。
みんな遊んでくれてありがとう。
わいわい遊びたい人いたら、Twitterでお声がけください！

2019年の目標

仕事を軌道にのせる(まずこれ)
英語頑張らないと
競プロする時間つくる
Swift 勉強
iPhone, Android の仕様覚えないと
スプラ S 帯いきたい

仕事とプライベート(趣味)がバランス良く両立できないと精神衛生上ダメなんだなあと学んだので、
今年は趣味に費やす時間も確保したいです。
C++ 書けない日があるのは楽しくない人生です。(おわり)

2018-10-13

std::next_permutation｜C++｜順列

C++ STL

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]三へ( へ՞ਊ ՞)へﾊｯﾊｯ

出力

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

*1:next_permutation - cpprefjp C++日本語リファレンス

2018-05-07

No.676 C0nvertPr0b1em｜yukicoder｜std::replace_if

yukicoder STL

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( 検索開始位置, 検索終了位置, 置換条件, 置換する値 )

同じような STL で std::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|)$ となる。

参考

*1:replace_if - cpprefjp C++日本語リファレンス

*2:replace - cpprefjp C++日本語リファレンス

*3: ラムダ式 - cpprefjp C++日本語リファレンス

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

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

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

2018年進捗大反省会

競プロ

言語

エディタ

仕事

スプラトゥーン2

2019年の目標

std::next_permutation｜C++｜順列

全列挙例

出力

No.676 C0nvertPr0b1em｜yukicoder｜std::replace_if

題意

考察

コード

計算量

参考

MacPorts で Python3系をインストール

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

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

定義

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

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

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

漸化式

コード

② -INF で埋めるDP

定義

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

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

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

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

漸化式

コード

まとめ

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

競プロ

言語

エディタ

仕事

スプラトゥーン2

2019年の目標

全列挙例

出力

題意

考察

コード

計算量

参考

① 普通に普通の 埋めDP

定義

のとき

のとき

のとき

漸化式

コード

② -INF で埋めるDP

定義

のとき

のとき

のとき

のとき

漸化式

コード

まとめ

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

① 普通に普通の $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}$ のとき