NSTomoS’s blog

NSTomoSの情報系の記録用ブログです.

c++で競プロ入門(2)

今回はABC040のC問題を解いていきます.

まず前回は投稿後に色々修正してすみませんでした…
今回以降はなるべく減らします…

そもそもC言語c++の関係は?

前回さらっとifforを使ったのですが,きちんと書くのを忘れていました.
c++C言語を機能拡張したものです.
なので,C言語の機能をほぼそのまま使用できます.
従って,今後C言語にある機能は解説なしで使っていきます.

C問題 柱柱柱柱柱

abc040.contest.atcoder.jp

この問題ではc++vector,そして頻出アルゴリズム動的計画法(DP)を扱っていきます.

STL

vectorの説明の前に,c++で重要な概念の一つであるSTLについて説明します.
STL(Standard Template Library)はc++の標準ライブラリの一つで,データ構造や,それらの操作,アルゴリズム等を型に依存しないで実装されているライブラリです.
競技プログラミングではこれらを用いる場合が非常に多いです.

動的配列vector

vectorSTLの動的配列のコンテナ(データ構造)です.
vectorをインクルードして使用してください.

STLではコンテナ名の後に<type>の形で使用する形を指定します.
今回はint型で用いるので以下のように宣言します.

vector<int> hoge;

配列の要素の参照は普通の配列と同様に[]で行います.

push_back関数で末尾に要素を追加できます.
が,今回は宣言時に使用する大きさが分かっているので,宣言時にの大きさ指定を行います.
名前の後に(size)のようにするとsizeの数の要素数を持ち,さらに(size,init)のようにするとinitで初期化されます.

従って,今回の1整数nとn個の整数の入力部は以下のようになります.

int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
    cin >> a[i];
}

この時,{a_1〜a_n}{a_0〜a_{n-1}}に変えています.
つまり1オリジンだったものを0オリジンにしています.
競技プログラミングでは入力は1オリジンでも配列等の関係で内部的に0オリジンに直した方が良い場合が多々あります.
ただ,出力する際には1オリジンに戻し忘れないようにしましょう.

動的計画法(DP)

今回の問題は動的計画法(DP)で解くことができます.
動的計画法

  • 分割統治法
  • メモ化

を用いたアルゴリズムの総称です.
それぞれC問題を例に解説していきます.

分割統治法

分割統治法は問題を細かく分けて小さな問題の解から大きな問題の解を求める方法です.
今回の問題の場合は,「{x-1}本目の柱と{x-2}本目の柱までの最小移動コストが分かっている時,{x}本目までの最小移動コスト(これを{f(x)}と定義する)を求める」という小さな問題を考えます.

次の3つの場合を考えます.
{x=0}の時,まだ移動していないので移動コストは{f(0)=0}です.
{x=1}の時,一回だけ{0}本目の柱から{1}本目の柱まで移動したので,移動コストは{f(1)=|a_1-a_0|}です.
そして {x\ge2}の時は,{|a_x-a_{x-1}|+f(x-1)}か,{|a_x-a_{x-2}|+f(x-2)}のどちらか小さい方が{f(x)}の答えになるはずです.

この漸化式を再帰関数に落とし込んで実装すると以下のようになります.

gista4681d44f494f96c95105000989598ef

再帰関数を使う関係でvector<int> aを大域変数にして,nの入力後に,resize()関数で要素数を指定しています.
(なお,このような使い方をするなら普通の配列を使った方が楽です.)

さて,このコードはサンプルケースでACします. しかしながらジャッジを通すとTLEします.

なぜでしょうか?
再帰関数は引数が01以外の場合,二つの再帰関数を呼び出します. 厳密な計算量は{O(N^2)}となります.
この計算量では,この問題の制約の最悪の場合({N=100,000})では,「時間制限 : 2sec」では終了しないのです.

メモ化

何度も呼び出される再帰関数ですが,実は引数が同じ値で何度も呼び出されています. 例えばf(5)f(4),f(3)を呼び出しますが,このf(4)f(3)を呼び出します.
これは非常に無駄です.

そこでメモ化です.
これは何度も同じ計算をする場合に最初の計算を記憶しておいて無駄な計算を減らす手法です.

まず思いつくのは再起関数f(x)の返り値を記憶する配列を別に用意し,もしその配列に値があればそれを返すようなf(x)に改良する方法です.
これはメモ化再帰と呼ばれるトップダウン動的計画法です.
しかし,これは実装が少々面倒です.

簡単に実装できてメモ化も実現できる方法があります.
それがボトムアップ動的計画法です.
どうせf(x)x0からn-1まで求めるのであれば,配列のまま,小さい数から計算をしていけば良いのです.

実装すると以下のようになります.

gist42b23dd72061eb22c3ca1b7feab484dd

これはちゃんと制限時間内に終了し,ACします.
ちなみに計算量は{O(N)}です.

この動的計画法が使えるようになると解ける問題の幅がだいぶ広がります.

次回予告(D問題)

このままD問題に突っ込むと長くなるのでC,Dで分けます…
次回もぜひ読んでください.