動的計画法入門

この記事は「競プロ!!」 競技プログラミング Advent Calendar 2017の25日目の記事です。

はじめに

動的計画法(DP : DynamicProgramming)は競プロでよく出てくるアルゴリズムのうちの一つです。しかしながら、割と難しいので分かりにくい部分でもあります。JOIの予選でもDPができなかったために、通過できなかった人も多いと思います。そこで、今回はできるだけ初心者（僕も含め）にも分かりやすいように、基本からまとめておこうと思います。

はじめの一歩

はじめの問題として、あまりにも有名なのがナップザック問題だと思います。解ける人は飛ばしてもらった方がいいかもしれません。
今回はAOJのサイトの問題を解こうと思います。Knapsack Problem

まず、始めに全探索をしてみましょう。

int dp(int n, int m){ //n個目までの品物を選び、合計の重さがm
	if(n == N) return 0;
	if(m >= W) return -100000;
	else return std::max(dp(n + 1, m + w[n]) + v[n], dp(n + 1, m));
}

各問題を選択するかしないかの二択なので、O(N²)となり現実的ではありません。（オーダの計算に関しては他のサイトを参考にしてください。）しかし、ここで少し考えると同じ引数が与えられ、同じ結果が出ることがありえます。なので、その結果を変数に保存して置けばかなり早くなることがわかります。

int memo[100][10000]; //-1で初期化をしておいてください。

int dp(int n, int m){
	if(memo[100][10000] != -1) return memo[n][m];
	if(n == N) return 0;
	if(m >= W) return -100000;
	else return memo[n][m] = std::max(dp(n + 1, m + w[n]) + v[n], dp(n + 1, m));
}

これをメモ化再起といい、動的計画法と呼べるものになりましたが、一般的には動的計画法と言うと、以下のようなものになります。

int dp[100][10000] = {}; //dp[i][j] = i番目を選び、合計でjの重さになった時の価値の合計の最大値。

for(int i = 1; i < N; ++i){
	for(int j = 0; j < W; ++j){
		dp[i][j] = dp[i - 1][j];
		if(j + w[i - 1] < W) dp[i][j + w[i - 1]] = std::max(dp[i][j + w[i - 1]], dp[i][j] + v[i - 1]);
	}
}

int ans = 0;
for(int i = 0; i < W; ++i){
	ans = std::max(ans, dp[N - 1][j]);
}

こんな感じです。表をイメージしてもらうと分かりやすいと思います。

いろいろな問題

ナップザック問題はDPの問題の中でも一番基本的なな問題です。他にも何個か問題があるので、参考までに載せておきます。

• ナップザック問題 II
• 最長部分増加数列
• レーベンシュタイン距離
• おせんべい
• 水ようかん

まとめ

これはあくまで動的計画法の基本なので、もっともっと動的計画法には難しい問題があります。もしかしたら、そのうち、応用編みたいなのも作るかもしれません。

PowerlineとVim、zsh、tmuxの環境を最速で構築する on Ubuntu 16.04

この記事はVim Advent Calender 2017の23日目の記事です。（夜までに書き終わってるといいな）

前書き

実は最近、Ubuntuで競プロとかやることが増えてきたのですが（僕はこっちにも記事を出す予定です。「競プロ!!」 競技プログラミング Advent Calendar 2017）Ubuntuなんて、仮想環境の上に組み立ててやるぐらいしかやらないので、なんども再インストールしたりするのですが、その度にPowerlineのセットアップにすごい時間を使うので、いい加減、手順をまとめておこうと思います。ちなみにJOI（情報オリンピック）本選に出場する人は本選でUbuntuを使わされると思うので、見ておくといいかもしれません。（本選で新たにパッケージをインストールすることはできないので、Vimになれるぐらいにしかならないけど）

完成予想図

環境

MacBook Air Early 2015

• macOS High Sierra
• Core i5 1.5Ghz
• Memory 8GB
• Ubuntu 16.04（Parallels 12 for Mac上）

容量が足りない。（128GB）

tmux

入ってないことはないとは思いますが、入れてください。

$ sudo apt-get install tmux

zsh

zshですが、個人的にはoh-my-zshがお勧めです。
まず、zshに切り替えます。

$ which zsh
/usr/bin/zsh
$ chsh
Password:
Changing the login shell for hoge
Enter the new value, or press ENTER for the default
        Login Shell [/bin/bash]: /usr/bin/zsh

それから、oh-my-zshをインストールします。

$ sudo sh -c "$(wget https://raw.githubusercontent.com/robbyrussell/oh-my-zsh/master/tools/install.sh -O -)"

あと、oh-my-zshはテーマを変えることができます。個人的にはavitがお勧めです。

ZSH_THEME="avit"

Vim

普通、標準で入っていますが、一応。

$ sudo apt-get install vim

あと重要なのが、自分のVimに入っているpythonのバージョンを調べることです。

$ vim --version | grep python
+cryptv          +linebreak       -python          +vreplace
+cscope          +lispindent      +python3         +wildignore

標準だと、python3が入っているはずです。(Ubuntu 16.04)

Powerlineのインストール

ついに、Powerlineのインストールをするのですが、その前に上で調べてもらったpythonがpython3だった場合はpip3をインストールしましょう。（Vimのpythonのバージョンの関係でPowerlineが呼び出せない）

$ sudo apt-get install python3-pip

その後、Powerlineをインストールします。

$ pip3 install --user powerline-status

それから、Powerlineの設定ファイルの場所を調べておきます。通常は以下の位置にあるはずです。

$ cd .local/lib/python3.5/site-packages/powerline/bindings/

パスは自分のpythonのバージョンに変えてください。

tmuxの設定

.tmux.confに書き込みます。

run-shell "powerline-daemon -q"
source ".local/lib/python3.5/site-packages/powerline/bindings/tmux/powerline.conf"

パスは自分のpythonのバージョンに変えてください。
（ちなみに、この設定だとホームディレクトリからtmuxを起動しないと、エラーが出ます。それを回避するには、パスを絶対パスにしてください。）

Vimの設定

追加するだけ、自分のpythonのバージョンに合わせてください。あと、laststatusを2にして、常に最終行が表示されるようにすること。

" Powerline settings
set laststatus=2
set showtabline=2
set t_Co=256
python3 from powerline.vim import setup as powerline_setup
python3 powerline_setup()
python3 del powerline_setup

最後に

以上がUbuntuでPowerlineとtmux + Vim + zshでの最速での環境構築だと思います。バージョンの違いとかで、公式ドキュメントにも載ってない罠がところどころにあるので、気をつけてください。

POJ3669 Meteor Shower 解説

POJ3669 Meteor Shower

http://poj.org/problem?id=3669

問題文

ベッシーは始め座標(0, 0)にいます。M個の隕石が(x, y)にT秒の時に落ちてきます。隕石が落ちた場所とその隣接する四方のマスには移動できません。ベッシーが安全な場所に移動する時、最短経路を行った場合、何秒かかるかを計算しなさい。

解法

ただのBFSですが、少しバグらせるポイントがあります。（実際少しバグらせた）座標がマイナスになることはありませんが、プラス方向には無限に続きます。

Waseda PCP Virtual Contest 2017/10/28 解説

このページは2017/10/28に開催されたWaseda PCP Virtual Contest for JOIの解説です。

問1 Change-おつり
'07-'08 予選1問目

一見めんどくさそうに見えますが、非常に簡単な問題です。おつりを500円から順に割っていくだけです。

問2 Christmas Party-クリスマスパーティ
'14-'15 予選2問目

もうすぐ来るけど、僕らは憂鬱になるだけの行事、クリスマス。
この問題は読解力があれば解けそう。ターゲットを配列に保存しておいて、足し算しましょう。気をつけて欲しいのは配列のインデックスについてです。配列は0から始まります。

問3 Card Game-カードゲーム
'07-'08 予選3問目

完全な実装ゲームです。3問目は例年めんどくさいですが、これもかなりめんどくさいです。割とここで詰まっている人が予想よりもずっと多かったので、驚きました。
解法ですが、特にアルゴリズムがあるわけでもなく、ゴリ押しです。僕はイテレータでごりごり押しました。

問4 JOI Flag-JOI旗
'10-'11 予選6問目

流石に難易度が鬼畜でした、これを作った人はきっと人間ではないのでしょう。さらにコンテストでやる場合、時間制限があるので最適化をかけないと通らないという鬼畜ぶり。本当にすみません。
まず、この問題は「良いJOI旗」を何通り数えられるかを考えるのではなく、「悪いJOI旗」を何通り数えられるのかを考えます。つまりは余事象です。しかし、これだけではオーダーに全く間に合いません。
さらに、直前のN個のますで"JO"が何処にあるか、さらに一つ前のますが'J'かどうか(次が'O'の時に"JO"であることがわかるため)をbitで保存します。
しかし、これだと、20 * 20 * 2^20 * 2個の配列が必要になって、MLEになってしまいます。そこで、直前のマスの情報のみ分かれば十分であることがわかるので、二つの情報を更新していけばいいことが分かります。なので、配列の数は2 * 2^20 * 2個ですみます。（それでも、僕の環境ではグローバル環境に宣言しないとエラーになりましたが）

正直言って、僕も初見で解くどころか、解説を見てやっと納得というところです。自分が解けない問題は人に出さないようにしましょう。本当にすみませんでした。

問5 Cheese-チーズ
'10-'11 予選5問目

結構昔に解いて、気に入ってた問題なので使いました。僕としては、4問目を飛ばして、5問目に取り組んで欲しかったです。
問題が少し複雑なので、日本語力が要求される気がしますが、冷静に読めば、要はSから番号順に工場を回っていけばいいことに気づきます。アルゴリズムは想定解法としてはBFS(幅優先探索)です。BFSを複数回できるか以外は基本なので、特に難しいことはありません。

問6 Foehn Phenomenon-フェーン現象
'16-'17 本選1問目

僕が本選で詰まってしまった問題です。実は、冷静に解けばすぐに解けるような問題になっています。
一つ前の標高との差を保存してしまえば、気温の増減は計算でき、地殻が変動しても変える値は二つで済むので、それを元に答えを計算します。しかし、観測する場所が地殻変動する場合は気温が変わらないことを気をつけましょう。
分かればとても解きやすい問題です。

C++で競技プログラミング入門

この記事はC++er Advent Calender 2016 9日目（別のタブで開かれます）の記事です。

まず初めに

まずはお詫び
実はこっそり、Advent Calenderの日付を書き換えました。というのも、登録するときは日曜日だから時間あるだろうと思ったのですが、僕は学生なので期末試験と被ってしまって書く時間が取れませんでした。

すみません。

ただ、明後日(2016/12/11 Sun)の情報オリンピックの予選には間に合わせたかったので、今書いています。情報オリンピック向けの話も最後の方でします。

このサイトは初心者による、初心者のための、初心者のサイトです。内容については保証できませんし、ツッコミどころ満載なのかもしれませんが悪しからず。

しかし、対象としてはC++の基本構文と関数ぐらいがわかっている程度の人向けです。

また、このサイトではC++を使っていきますが、他の言語であってもある程度はわかると思います。

実ははてなブログをまともに書くのこれが初めてだったりもします。

競技プログラミングとは

特定の問題が与えられて、それに対して最適なアルゴリズム、より少ないメモリ、より少ない時間で解けるプログラムを書くことを目指します。
世界中で行われていて、例えば、TopCoderというようなとても大規模なサイトもあり、そのサイトの中でレッドコーダーなんていう愉快な魔法使い（上位数%の天才）たちがいたり。僕はあんまりTopCoderには参加しませんが。

競プロなんて呼ばれたりすることも。

初めの一問

こんな問題があります。

Ants

長さLcmの棒があり、その上に蟻がn匹いて、その蟻たちは端からx0, x1, x2...xncmの場所にいます。蟻たちは初め左右のどちらを向いているかはわからず、1cm/secの速さで棒の上を移動します。蟻たちはぶつかるともと来た方向に戻ります。蟻たちが棒のはじまでくると蟻たちは棒から落ちます。

全ての蟻たちが落ちるまでにかかる時間を求めなさい。（秒）

制約: 1 <= L <= 10^6, 1 <= n <= 10^6, 0 <= xi <= L

見たことある人は見たことある問題ですね。

少し見ると難しそうな問題ですが解法自体は非常に簡単なものです。頭がよければノーヒントでも解けるかも。

ヒント: 蟻がぶつかるともと来た方向に戻るってことは...





ここからは正解になります。考えたい人はページを下げないように。






一見すると全探索したくもなりますが、計算量的に無理です。（計算量に関してはここでは割愛させてもらいます。このページがわかりやすいです。）

まずは、ヒントの意味ですがこれは蟻がぶつかった時にもと来た方向に戻るのではなく、そのまますれ違ったと捉えればいいということです。蟻に区別はありません。

つまり、解法としては蟻の場所から端までの距離だけを考えればいいことになります。

#include <iostream>
#include <algorithm>

#define MAX 1000000

int main(){
    int N, L, n, x[MAX];
    std::cin >> N;
    
    while(N--){
        std::cin >> L >> n;
        for(int i = 0; i < n; ++i){
            std::cin >> x[i];
        }
        
        int max = 0, min = 0;
        for(int i = 0; i < n; ++i){
            max = std::max(max, std::max(L - x[i], x[i]));
            min = std::max(min, std::min(L - x[i], x[i]));
        }
        std::cout << min << " " << max << std::endl;
    }
    
    return 0;
}

こんな感じです。POJ（北京大学オンラインジャッジ）に提出したコードなので、C++11が使えません。

POJへのリンクを貼っておきます。 Ants

どうやって強くなるか

オンラインジャッジについて

競プロはインターネット上のオンラインジャッジで練習をします。有名なサイトをいくつか参考までに載せておきます。

AOJ 会津大学オンラインジャッジ: 日本の会津大学が運営しているサイトです。言語もC++14やPython、Haskellまで対応しています。とても使いやすいサイトです。まずは、ここの初心者コースから始めるといいと思います。

POJ 北京大学オンランジャッジ: 少し、初心者向けではないかもしれませんが、問題の種類でいうならば非常に多いです。ただ、言語（話す言語）が中国語もしくは英語なのとプログラミング言語がC++11に対応していません。

AtCoder: これも日本で運営されているサイトです。上の二つのサイトとは違いコンテスト形式で通常は土曜日の午後9:00から始まります。（ただ、残念ながら僕は毎週その時間帯には予定が入ってる...）ランキングやレーティングなどがあり、自分がどのくらいできるのかがよくわかります。

TopCoder: これは世界でも最大級のサイトだと思います。しかし、言語（話す言語）が英語なので少しわからないと辛いかもしれません。このサイトは問題と定期的にコンテストが開かれます。ただし、海外の時間帯で日本では参加できるわけがない時間帯に設定されることがあります。

書籍について

普通は解けない問題があればインターネットで調べて解決するので十分ですが、体系的にアルゴリズムを学ぶのにとても役立ちます。

プログラミング コンテスト チャレンジブック 第二版: 競プロのバイブル的な本です。通称、蟻本と呼ばれます。表紙に書かれている先ほどのAntsをイメージした図と名前をかけています。一冊は買っといたほうがいいと思います。ちなみに僕の学校のパソコン部では持ってない人が取り合いになったりもします。

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造: 簡単な本で初心者にはとてもお勧めできます。上の本はある程度難しいのでこちらの本から初めてみるのがいいかもしれません。ちなみに、著者の会津大学の渡部さんはわたのべさんと読みます。

少し書き方について

書き方に関しては色々あるのでここから話すのは個人的なものです。

実はさっきのコードには改善点があります。

defineとconstexpr

先ほどは #define MAX 1000000 と書きました。
これは競プロにおいてはよくやることで、あらかじめ制約を上に書くことで配列などの範囲をわかりやすくします。

しかし、数年前まではこう書いていましたが今はあまりよろしくありません。というのも#defineで書くとエラーメッセージが気持ちが読みづらいことになってしまいます。実際にコンパイルする前にソースコードの"MAX"という部分を全て"1000000"に書き換えてから処理を始めるので、エラーメッセージが"〜MAX is〜"のような形ではなく、"〜1000000 is〜"のようにわかりづらい表示になります。この問題では考えなくても良い気がしますが、書き方としてはあまり使われません。（この話はEffective C++という本に書いてあったはず）

そこで代わりにC++11から追加されたconstexprを使います。コンパイル時定数として扱われるので、defineよりも優れています。
上のコードは本来であれば（POJがC++11に対応していれば）
constexpr int MAX 1000000;
と書いた方が良いです。
2016/12/11 追記 タイプミスをコメントで教えてもらいました。 constexor → constexpr

constexprとdefineの違いについては割愛します。（正直なところ自分でもよくわかってない。）

では、defineは使い道がないのかというと、全くそういうことでもありません。次のようなことをしている人もいます。
#define REP(i, a) for(int i = 0; i < (a); ++i)
これはfor文を書く時間が勿体無いのでマクロで簡略化する方法です。僕は慣れられずに使わないのですが中には使う人もいます。僕はなんとなく使いたくないんですけど。

他にもincludeをとりあえず何が必要かわからないから全部書いてしまうこともあります。そのらへんの話はこのページあたりがとても参考になります。

入出力について

実は、競プロで判定をする時には、とても多い量の入力にかけられています。なので、普段はそこまで気にする必要のない入出力にも気をつけたほうがいいです。

stdioを使う場合

時代はC言語まで退化しますが速度はおそらく一番早いです。ただし、書式設定には気をつけたください。特に入力でスペースなどがある場合はそれを考慮する必要があります。ちなみに僕はいつもこれを使っています。

iostreamを使う場合

先ほどは書きませんでしたが、
std::ios::sync_with_stdio(false);
というおまじないをmainの一番上の場所に書くと処理が早くなります。ただし、これを使うとcin, coutとscanf, printfを混在させることはできません。 あとは改行についてですが、
std::cout << std::endl;
よりも
std::cout << '\n';
の方が早いです。（普段は前者の方が安定した動作をします。 参考: http://www.bohyoh.com/CandCPP/FAQ/FAQ00009.html）)
2016/12/11 追記
コメントでご指摘をいただきましたが、そもそも、文字列などを出力する場合は'+'もしくは'+='の方が早いです。
Example:

	
		std::string S;
		std::cin >> S;
		std::cout << S + '\n';
	
	

その他

他にも入出力部分をmain、処理部分をsolveという関数で書いて分けたりもします。蟻本の書き方がこれなので他の人もこういう書き方をしていることはありますが、特に気にする必要はないです。

JOIについて

JOI、明後日です。
Antsの内容がわかれば、2問完全正解はいけると思います。
予選とのボーダーはDPができるかどうかだったのですが、去年からJOIの運営が4問目をDPでない問題にしたので予想はできないです。5問答えられれば予選は突破できそうです。

ただ、JOIの問題の提出がとても面倒くさくて、JOIやPOJのようにソースコードを提出するだけではなく、それらの入力データ（5個）が渡されて、それに対して出力データを用意して提出しなくてはいけません。（練習ページでやってみるといいかもしれません。）
そんな作業を手でやっていると間違いなく時間が足りなくなるので、普通はredirectというバッチファイルを作ってそれを使って自動化します。

参考までに（macOS向け）

#/bin/sh

clang++ $1 std=c++11 -o .execute.out

mkdir "out$2"

for var in {1..5}
	do
		input_file=`ls *in$2/*$var.txt`
		output_file="out$2/out$var.txt"
		./.execute.out < $input_file > $output_file
	done

使い方は
sh ./redirect.sh source_file problem_number
という風にして第一変数にコード、第二変数に何番目の問題かを指定します。入出力ファイルは同じ階層に1問目ならin1というフォルダを作ってその中に入力ファイルを入れます。

Windows向けは今、持っていないので知り合いにもらったら載せます。

Blog Test

はてぶろのテストです。

僕は技術系の（主にプログラミング）なんかに興味があったりします。まだまだ、未熟者ですが、よろしくお願いします。