はじめに

競技プログラミングで DP (動的計画法) を使うことがよくあります。

私の場合、よく初期化忘れと範囲外アクセスでハマって時間を使ってしまいます。そこで記事にしようと思いました。

本記事のコード例は C++17, Rust + proconio で書いています。¹

TL;DR

DP の考え方はシンプル。よく使うテクニックのために、難しそうに見えることもあるかも。
初期化忘れに注意。とくに到達不能な場所があるときにはそう分かるように、適切な値を入れておきたい。 (*1)
範囲外アクセスに注意。大きな領域を確保する、外側をスキップするように条件分岐、同じ領域を使いまわすなど、いろいろ対策あり。 (*2)
配る DP で、 *1, *2 についてそれぞれ複数の実装を紹介します。

今回扱う問題

問題

Kyo 君は 1回の操作で 3個または 5個のボールを取ることができます。

$N$ 個のボールがあるとき、Kyo 君は最小で何回の操作を行うとボールをすべて取ることができるかを答えてください。どの順でもすべて取ることができないときは $-1$ と答えてください。

制約

$1 \le N \le 10000$

入力

$N$

入力例 1

出力例 1

18個のボールを取る操作は次の2通りあります。

3個を取る操作を 6回行う (3 * 6 = 18)
3個を取る操作を 1回、5個を取る操作を 3回行う (3 * 1 + 5 * 3 = 18)

後者の方が、少ない回数で行えます。

入力例 2

出力例 2

-1

7個のボールを、3個と 5個の組み合わせでちょうど取り除く方法はありません。

配る DP で解くイメージ

「配る DP」で書くとこんな感じです。 dp という配列に「ボールを取った合計個数に対応した最短手数」を入れています。3個ボールが多いところへは 1手増やして到達可能、5個ボールが多いところへも 1手増やして到達可能です。

先頭はボール 0個を 0手で到達可能、その他は - 無効としておきます。

カーソルを 1つずつ右に動かして、3個先と 5個先のを更新していきます。

i	_0	_1	_2	_3	_4	_5	_6	_7	_8	_9	10	11	12	13	14	15	16	17	18
初期	0	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-
	0	-	-	1	-	1	-	-	-	-	-	-	-	-	-	-	-	-	-
	0	-	-	1	-	1	-	-	-	-	-	-	-	-	-	-	-	-	-
	0	-	-	1	-	1	-	-	-	-	-	-	-	-	-	-	-	-	-
	0	-	-	1	-	1	2	-	2	-	-	-	-	-	-	-	-	-	-
	0	-	-	1	-	1	2	-	2	-	-	-	-	-	-	-	-	-	-
	0	-	-	1	-	1	2	-	2	-	2	-	-	-	-	-	-	-	-
	:	:	:	:	:	:	:	:	:	:	:	:	:	:	:	:	:	:	:
	0	-	-	1	-	1	2	-	2	3	2	3	4	3	4	3	4	5	4

カーソルが 5個目のとき、8個目にはすでに値が入っています。この問題は少ない手順を求めるものですので、小さな方を採用します。3 + 5 も 5 + 3 もどちらも 2手です。

プログラミングに落とし込みやすいように場合分けすると、dp[i+3], dp[i+5] の次の値は次のようになります。 - は到達不能。a, b は 0 以上の整数が入り、その手数で到達可能ということを示します。

	`dp[i+3] = -` の場合	`dp[i+3] = b` の場合
`dp[i] = -`	`dp[i+3] = -`	`dp[i+3] = b`
`dp[i] = a`	`dp[i+3] = a + 1`	`dp[i+3] = min(a + 1, b)`

	`dp[i+5] = -` の場合	`dp[i+5] = b` の場合
`dp[i] = -`	`dp[i+5] = -`	`dp[i+5] = b`
`dp[i] = a`	`dp[i+5] = a + 1`	`dp[i+5] = min(a + 1, b)`

このようにしてカーソルを 18個目まで動かすと、ボール 18個までの移動手数をすべて確認済みとなります。 4手で可能です。お疲れさまでした。

制約条件のボール 10000個程度なら一瞬で解けます。

よくある解答

上の流れのとおり実装します。

さて、競技プログラミングでは次のようなコードを良く見ます。

1a.cpp

#include <iostream>
#include <array>

using namespace std;

int main()
{
    long long n;
    cin >> n;

    const long long MAX = 100'000'000;
    array<long long, 10005> dp; // *2
    dp.fill(MAX); // *1
    dp[0] = 0;
    for (auto i = 0ll; i < n; ++i) {
        dp[i + 3] = min(dp[i + 3], dp[i] + 1);
        dp[i + 5] = min(dp[i + 5], dp[i] + 1);
    }

    auto result = dp[n] == MAX ? -1 : dp[n];
    cout << result << endl;
}

1a.rs

use proconio::input;

fn main() {
    input! {
        n: usize,
    }
    const MAX: i64 = 100_000_000; // *1
    let mut dp = [MAX; 10005]; // *2
    dp[0] = 0;
    for i in 0..n {
        dp[i + 3] = dp[i + 3].min(dp[i] + 1);
        dp[i + 5] = dp[i + 5].min(dp[i] + 1);
    }
    let result = if dp[n] == MAX { -1 } else { dp[n] };
    println!("{}", result);
}

*1, *2 って？答えになり得ない大きな値を、問題設定より大きめの配列を用意して埋めておくということ？どれくらい大きな値にすれば大丈夫？

このあたりが DP の最初の壁だと思っています。

ところで std:array

本記事内では C の配列ではなく、C++11 のstd::array を使っています。この 2つは同じ動作になります。 std::array は fill() などのメソッドが使えて、すこし便利です。

    array<long long, 10005> dp; // *2
    dp.fill(MAX); // *1

    const long long M = 10005;
    long long dp[M];
    for (long long i = 0; i < M; ++i) {
        dp[i] = MAX;
    }

検討 1. 初期化について

配列の初期値として、答えになり得ない大きな値で埋めている、という話です。

    const long long MAX = 100'000'000;
    dp.fill(MAX); // *1

初期化を忘れると

i	1	2	3	4	5	6
初期	-	-	-	-	-	-
	-	-	1	-	1	-
	-	-	1	-	1	-

うっかり初期化を忘れて 0 で埋めてしまったとすると、

i	3	4	5	6
初期	0	0	0	0
	1	0	1	0
	1	1	1	1

になります。違う答えになってしまいです。

0 と - は似ています。でも「到達可能」「到達不能」という大きな違いがあります。

C++ や Rust で dp を整数の配列とする場合、「手数」と「到達可能」「到達不能」の 2つの情報をまとめて扱うことが必要です。そして、1番目以外はまず「到達不能」を示す値で埋めておきたいです。

方法 1a. 到達不能を極端に大きな値で示す

i	1	2	3	4	5	6
初期	-	-	-	-	-	-
	-	-	1	-	1	-
	-	-	1	-	1	-

i	1	2	3	4	5	6
初期	Max	Max	Max	Max	Max	Max
	Max	Max	1	Max	1	Max
	Max	Max	1	Max	1	Max

- の代わりに、Max や Inf といった名前で、大きな値を入れておきます。この大きな値は - と同じようにふるまいます。

	`dp[i+3] = Max` の場合	`dp[i+3] = b` の場合
`dp[i] = Max`	`dp[i+3] = Max`	`dp[i+3] = b`
`dp[i] = a`	`dp[i+3] = a + 1`	`dp[i+3] = min(a + 1, b)`

先の表の - を大きな数字 Max に置き換えた場合です。この変更の値を示す 4つの式は、すべて dp[i+3] = min(dp[i]+1, dp[i+3]) とまとめられます。プログラミングで条件分岐を書くことなく、到達不能を示す Max を表すことができます。実装量が減れば実装時間も不具合も減ります。だから、競技プログラミングでよく使われます。

Max は、ボールの最大数 10000 より大きければなんでも良いです。有効な手数が 10000 / 3 を超えることはありません。問題文によって最大数を考えるのも面倒ですから、足し算してもオーバーフローしない const long long MAX = 1ll << 62; などをいつも使う、というのも良いかもです。 ²

1a.cpp

#include <iostream>
#include <array>

using namespace std;

int main()
{
    long long n;
    cin >> n;

    const long long MAX = 100'000'000;
    array<long long, 10005> dp; // *2
    dp.fill(MAX); // *1
    dp[0] = 0;
    for (auto i = 0ll; i < n; ++i) {
        dp[i + 3] = min(dp[i + 3], dp[i] + 1);
        dp[i + 5] = min(dp[i + 5], dp[i] + 1);
    }

    auto result = dp[n] == MAX ? -1 : dp[n];
    cout << result << endl;
}

1a.rs

use proconio::input;

fn main() {
    input! {
        n: usize,
    }
    const MAX: i64 = 100_000_000; // *1
    let mut dp = [MAX; 10005]; // *2
    dp[0] = 0;
    for i in 0..n {
        dp[i + 3] = dp[i + 3].min(dp[i] + 1);
        dp[i + 5] = dp[i + 5].min(dp[i] + 1);
    }
    let result = if dp[n] == MAX { -1 } else { dp[n] };
    println!("{}", result);
}

問題設定によって初期値を調整する

この方針は、問題設定によって初期値が変わります。今回の問題も「最小」を「最大」に変えると、初期値変更が必要になります。

問題'

Kyo 君は 1回の操作で 3個または 5個のボールを取ることができます。

$N$ 個のボールがあるとき、Kyo 君は最大で何回の操作を行うとボールをすべて取ることができるかを答えてください。どの順でもすべて取ることができないときは $-1$ と答えてください。

	`dp[i+3] = -` の場合	`dp[i+3] = b` の場合
`dp[i] = -`	`dp[i+3] = -`	`dp[i+3] = b`
`dp[i] = a`	`dp[i+3] = a + 1`	`dp[i+3] = max(a + 1, b)`

先ほどと同じように初期値として大きな値を入れてしまうと、テーブルが全然更新されません。

i	1	2	3	4	5	6
初期	Max	Max	Max	Max	Max	Max
	Max	Max	Max	Max	Max	Max
	Max	Max	Max	Max	Max	Max

この場合は、負の十分小さな値 Min を入れておく、でしょうか。テーブル更新後に負の値なら到達不能でます。

i	1	2	3	4	5	6
初期	Min	Min	Min	Min	Min	Min
	Min	Min	1	Min	1	Min
	Min	Min	1	Min+1	1	Min+1

最後に値を出力するときに、負の値なら到達不能を示す -1、0 以上ならそのままを答えるように、 dp[n] >= 0 ? dp[n] : -1 や max(dp[n], -1ll) のように書けば良いです。こちらもお疲れさまでした。

1_min.cpp

1a-1.cpp

#include <iostream>
#include <array>

using namespace std;

int main()
{
    long long n;
    cin >> n;

    const long long MIN = -100'000'000;
    array<long long, 10005> dp;
    dp.fill(MIN);
    dp[0] = 0;
    for (auto i = 0ll; i < n; ++i) {
        dp[i + 3] = max(dp[i + 3], dp[i] + 1);
        dp[i + 5] = max(dp[i + 5], dp[i] + 1);
    }

    long long result = max(dp[n], -1ll);
    cout << result << endl;
}

1a-1.rs

use proconio::input;

fn main() {
    input! {
        n: usize,
    }
    const MIN: i64 = -100_000_000;
    let mut dp = [MIN; 10005];
    dp[0] = 0;
    for i in 0..n {
        dp[i + 3] = dp[i + 3].max(dp[i] + 1);
        dp[i + 5] = dp[i + 5].max(dp[i] + 1);
    }
    let result = dp[n].max(-1);
    println!("{}", result);
}

方法 1b. 到達不能を -1 で示す

解答方法が「どの順でもすべて取ることができないときは $-1$ と答えてください」ですので、dp の初期値を -1 にしておくのも良ささそうです。

	`dp[i+3] = -1` の場合	`dp[i+3] = b` の場合
`dp[i] = -1`	`dp[i+3] = -1`	`dp[i+3] = b`
`dp[i] = a`	`dp[i+3] = a + 1`	`dp[i+3] = min(a + 1, b)`

Max や Min を使う場合は 1 つの数式で表現することができました。残念ながら -1 を特別な値とすると、この時のようにはうまくまとめられません。「dp[i] >= 0 && (dp[i+3] == -1 || dp[i+3] > dp[i] + 1) の場合に、dp[i+3] = dp[i] + 1 と更新する」とベタっと書くことになるでしょう。

1b.cpp

#include <iostream>
#include <array>

using namespace std;

int main()
{
    long long n;
    cin >> n;

    array<long long, 10005> dp;
    dp.fill(-1);
    dp[0] = 0;

    auto f = [&dp](auto i, auto j) {
        auto x = dp[i] + 1;
        if (dp[j] < 0 || dp[j] > x) {
            dp[j] = x;
        }
    };

    for (auto i = 0ll; i < n; ++i) {
        if (dp[i] >= 0) {
            f(i, i + 3);
            f(i, i + 5);
        }
    }

    cout << dp[n] << endl;
}

1b.rs

use proconio::input;

fn f(dp: &mut [i64], i: usize, j: usize) {
    let x = dp[i] + 1;
    if dp[j] < 0 || dp[j] > x {
        dp[j] = x;
    }
}

fn main() {
    input! {
        n: usize,
    }
    let mut dp = [-1; 10005];
    dp[0] = 0;
    for i in 0..n {
        if dp[i] >= 0 {
            f(&mut dp, i, i + 3);
            f(&mut dp, i, i + 5);
        }
    }
    let result = dp[n];
    println!("{}", result);
}

実装がけっこう長くなります。マジックナンバー -1 で dp を初期化するというのも嫌な感じです。

方法 1c. 到達不能を値を持たない Optional 型で示す

C++17 の std::optional を使うと、マジックナンバー -1 を取り除けます。空の値 nullopt は手数とは違う特別な意味を持っていそうに見えます。他の言語で null や None や nil を 0 と使い分けるのと同じ感じです。

optional - cpprefjp C++日本語リファレンス

	`dp[i+3] = nullopt` の場合	`dp[i+3] = b` の場合
`dp[i] = nullopt`	`dp[i+3] = nullopt`	`dp[i+3] = b`
`dp[i] = a`	`dp[i+3] = a + 1`	`dp[i+3] = min(a + 1, b)`

こうすると、表の下側が「a + 1 と (b が有効なら b, 無効なら a + 1) の小さいほう」と 1つの式でまとめられます。 -1 で初期化するよりも短く書くことができます。³

1c.cpp

#include <iostream>
#include <optional>
#include <array>

using namespace std;

int main()
{
    long long n;
    cin >> n;

    array<optional<long long>, 10005> dp;
    dp[0] = 0;
    for (auto i = 0ll; i < n; ++i) {
        if (dp[i].has_value()) {
            auto x = dp[i].value() + 1;
            dp[i + 3] = min(dp[i + 3].value_or(x), x);
            dp[i + 5] = min(dp[i + 5].value_or(x), x);
        }
    }

    long long result = dp[n].value_or(-1);
    cout << result << endl;
}

1c-cpp23.cpp

#include <iostream>
#include <optional>
#include <array>

using namespace std;

int main()
{
    long long n;
    cin >> n;

    array<optional<long long>, 10005> dp;
    dp[0] = 0;
    for (auto i = 0ll; i < n; ++i) {
        if (dp[i].has_value()) {
            auto x = dp[i].value() + 1;
            auto f = [x](auto y) { return optional(min(x, y)); };
            auto g = [x]() { return optional(x); };
            dp[i + 3] = dp[i + 3].and_then(f).or_else(g);
            dp[i + 5] = dp[i + 5].and_then(f).or_else(g);
        }
    }

    long long result = dp[n].value_or(-1);
    cout << result << endl;
}

1c.rs

use proconio::input;

fn main() {
    input! {
        n: usize,
    }
    let mut dp = vec![None; n + 5];
    dp[0] = Some(0);
    for i in 0..n {
        if let Some(x) = dp[i] {
            let x = x + 1;
            dp[i + 3] = Some(dp[i + 3].unwrap_or(x).min(x));
            dp[i + 5] = Some(dp[i + 5].unwrap_or(x).min(x));
        }
    }
    let result = dp[n].unwrap_or(-1);
    println!("{}", result);
}

それでも Max を使う最初の実装の方がより短いです。実装ミスを防ぐという意味では、 std::optional に慣れているなら optional を使う方が安全そうです。好みの問題だと思います。

検討 1. のまとめ

方法	評価
1a. 到達不能を極端に大きな値で示す	◎
1b. 到達不能を -1 で示す	△
1c. 到達不能を値を持たない Optional 型で示す	○

評価は、実装速度を優先したい、綺麗に書きたい、などコーディングスタイルによって変わります。

検討 2. 範囲外アクセスについて

大きな固定サイズの配列を作っていることについてです。

    array<long long, 10005> dp; // *2

検討 1. の初期化方法は「方法 1a. 到達不能を極端に大きな値で示す」とします。ほかと組み合わせることもできます。

方針 2a. 大きめの静的な配列を用意する

問題の条件では $1 \le N \le 10000$ でした。それなら最大値の $N = 10000$ でもあふれない量の配列を用意すれば、どんな $N$ がやってきても安心です。

i	0	...	9999	10000	10001	10002	10003	10004
	0	...	2001	2000	2001	2002	2001	2002

dp[10000] の値が正しくなるためには、その 1つ前までカーソルを動かせば確実です。そうすると dp[10004] までアクセスできると安心です。そのため、サイズ 10005 にしています。

うっかり配列のサイズが足りないと、配列の範囲外にアクセスしようとしてプログラムが落ちます。危険です。

いくつ増やしていいか考えるのが面倒な時は、えいやっと大きくても大丈夫です。 2倍して 20000 など。

1a.cpp

#include <iostream>
#include <array>

using namespace std;

int main()
{
    long long n;
    cin >> n;

    const long long MAX = 100'000'000;
    array<long long, 10005> dp; // *2
    dp.fill(MAX); // *1
    dp[0] = 0;
    for (auto i = 0ll; i < n; ++i) {
        dp[i + 3] = min(dp[i + 3], dp[i] + 1);
        dp[i + 5] = min(dp[i + 5], dp[i] + 1);
    }

    auto result = dp[n] == MAX ? -1 : dp[n];
    cout << result << endl;
}

1a.rs

use proconio::input;

fn main() {
    input! {
        n: usize,
    }
    const MAX: i64 = 100_000_000; // *1
    let mut dp = [MAX; 10005]; // *2
    dp[0] = 0;
    for i in 0..n {
        dp[i + 3] = dp[i + 3].min(dp[i] + 1);
        dp[i + 5] = dp[i + 5].min(dp[i] + 1);
    }
    let result = if dp[n] == MAX { -1 } else { dp[n] };
    println!("{}", result);
}

いつも大きな領域を確保すると無駄そうにも思います。でもどうせ制約条件内の一番厳しい条件までは動かないといけませんから、これにより解ける問題数が変わることはありません。

大きな N でも動くことを早めに確認できるというメリットもあります。小さな N では動くけれど大きな数でランタイムエラーになる、というのは競技プログラミングあるあるです。たぶん。

方針 2b. 少し大きめの動的な配列にする

静的 = コンパイル時に配列のサイズが決まる std::array の代わりに、動的 = 実行時に配列のサイズを指定する std::vector にします。それ以外は変わりません。

i	0	1	2	3	4	5	6
初期	0	Max	Max	Max	Max	Max	Max
	0	Max	Max	1	Max	1	Max
	0	Max	Max	1	Max	1	Max
解答			Max

2b.cpp

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    long long n;
    cin >> n;

    const long long MAX = 100'000'000;
    vector<long long> dp(n + 5, MAX); // ★
    dp[0] = 0;
    for (auto i = 0ll; i < n; ++i) {
        dp[i + 3] = min(dp[i + 3], dp[i] + 1);
        dp[i + 5] = min(dp[i + 5], dp[i] + 1);
    }

    auto result = dp[n] == MAX ? -1 : dp[n];
    cout << result << endl;
}

2b.rs

use proconio::input;

fn main() {
    input! {
        n: usize,
    }
    const MAX: i64 = 100_000_000;
    let mut dp = vec![MAX; n + 5]; // ★
    dp[0] = 0;
    for i in 0..n {
        dp[i + 3] = dp[i + 3].min(dp[i] + 1);
        dp[i + 5] = dp[i + 5].min(dp[i] + 1);
    }
    let result = if dp[n] == MAX { -1 } else { dp[n] };
    println!("{}", result);
}

方針 2c. 同じ大きさの動的な配列にして、ループ内で条件分岐

はみ出しても良いように大きめの配列を用意する、というのはいかにも競技プログラミング用テクニックな感じです。

ふつうに実装すると、配列の外側にはアクセスしないように条件分岐となると思います。 2個のボールについて調べるときに、3個以上のボールまで調べても答えには影響しません。

たとえば 6個めのボールまで調べるときに、配列の 7番目以降は更新しないようにします。毎回アクセス可能かを if (j < dp.size()) のように確認します。

i	0	1	2	3	4	5	6
初期	0	Max	Max	Max	Max	Max	Max
	0	Max	Max	1	Max	1	Max
	0	Max	Max	1	Max	1	Max
	0	Max	Max	1	Max	1	Max
	0	Max	Max	1	Max	1	2
	0	Max	Max	1	Max	1	2
	0	Max	Max	1	Max	1	2
解答							2

2c.cpp

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    long long n;
    cin >> n;

    const long long MAX = 100'000'000;
    vector<long long> dp(n + 1, MAX);
    dp[0] = 0;

    auto f = [&dp](auto i, auto j) {
        if (j < dp.size()) {
            dp[j] = min(dp[j], dp[i] + 1);
        }
    };

    for (auto i = 0ll; i < n; ++i) {
        f(i, i + 3);
        f(i, i + 5);
    }

    auto result = dp[n] == MAX ? -1 : dp[n];
    cout << result << endl;
}

2c.rs

use proconio::input;

fn f(dp: &mut [i64], i: usize, j: usize) {
    if j < dp.len() {
        dp[j] = dp[j].min(dp[i] + 1);
    }
}

fn main() {
    input! {
        n: usize,
    }
    const MAX: i64 = 100_000_000;
    let mut dp = vec![MAX; n + 1];
    dp[0] = 0;
    for i in 0..n {
        f(&mut dp, i, i + 3);
        f(&mut dp, i, i + 5);
    }
    let result = if dp[n] == MAX { -1 } else { dp[n] };
    println!("{}", result);
}

方針 2d. 同じ大きさの動的な配列にして、最後を特殊処理

方針 2c で 3つ先と 5つ先の 2つの値を更新「できない」のは、最後の 5つだけでした。だとすると、途中で配列の範囲内かを調べるのはあまり意味がありません。この最後だけを特殊処理すれば良いです。

6 個めのボールを調べる場合は、2つの値を更新できるところまでループを回し、最後だけ「6-3 番目のボールの手数」を調べれば十分です。次の表のように求まります。

i	0	1	2	3	4	5	6
初期	0	Max	Max	Max	Max	Max	Max
	0	Max	Max	1	Max	1	Max
	0	Max	Max	1	Max	1	Max
	0	Max	Max	1	Max	1	2
解答							2

2d.cpp

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    long long n;
    cin >> n;

    const long long MAX = 100'000'000;
    vector<long long> dp(n + 1, MAX);
    dp[0] = 0;

    for (auto i = 0ll; i <= n - 5; ++i) {
        dp[i + 3] = min(dp[i + 3], dp[i] + 1);
        dp[i + 5] = min(dp[i + 5], dp[i] + 1);
    }
    if (n >= 3) {
        dp[n] = min(dp[n], dp[n - 3] + 1);
    }

    auto result = dp[n] == MAX ? -1 : dp[n];
    cout << result << endl;
}

2d.rs

use proconio::input;

fn main() {
    input! {
        n: usize,
    }
    const MAX: i64 = 100_000_000;
    let mut dp = vec![MAX; n + 5];
    dp[0] = 0;
    for i in 0..=(n as i64 - 5) {
        let i = i as usize;
        dp[i + 3] = dp[i + 3].min(dp[i] + 1);
        dp[i + 5] = dp[i + 5].min(dp[i] + 1);
    }
    if n >= 3 {
        dp[n] = dp[n].min(dp[n - 3] + 1);
    }
    let result = if dp[n] == MAX { -1 } else { dp[n] };
    println!("{}", result);
}

今回の解答例はすべて「配る DP」としました。「貰う DP」だとより自然に書けます。

この、末尾の 3個手前を見る実装の場合、N < 3 のときにうっかり負のインデックスを使って配列にアクセスしないよう注意です。プログラムが落ちます。 N = 10000 が解ける実装でも、 N = 2 で足元をすくわれかねません。

方針 2e. 小さな配列を使いまわす

DP の更新対象は 3個先と 5個先だけです。5個分の履歴を残しておけば、どこまででも値が求まるはずです。

たとえば N = 8 の解答を、7要素の配列を使って求めるイメージです。右端にたどり着くと左に戻ります。 7で割った余りをインデックスとして使用します。

i	0	1	2	3	4	5	6
初期	0	Max	Max	Max	Max	Max	Max
cur=0	0	Max	Max	1	Max	1	Max
cur=1	Max	Max	Max	1	Max	1	Max
cur=2	Max	Max	Max	1	Max	1	Max
cur=3	Max	2	Max	1	Max	1	2
cur=4	Max	2	Max	Max	Max	1	2
cur=5	Max	2	Max	2	Max	1	2
cur=6	Max	2	3	2	3	Max	2
cur=7	Max	2	3	2	3	Max	Max
解答		2

でを更新した後は、もうその値を使いません。直後にで空を示す Max を入れ、次の利用に備えます。

2e.cpp

#include <iostream>
#include <array>

using namespace std;

int main()
{
    long long n;
    cin >> n;

    const long long MAX = 100'000'000;
    const long long M = 7;
    array<long long, M> dp;
    dp.fill(MAX);
    dp[0] = 0;
    for (auto i = 0ll; i < n; ++i) {
        dp[(i + 3) % M] = min(dp[(i + 3) % M], dp[i % M] + 1);
        dp[(i + 5) % M] = min(dp[(i + 5) % M], dp[i % M] + 1);
        dp[i % M] = MAX;
    }

    auto result = dp[n % M] == MAX ? -1 : dp[n % M];
    cout << result << endl;
}

2e.rs

use proconio::input;

fn main() {
    input! {
        n: usize,
    }
    const MAX: i64 = 100_000_000;
    const M: usize = 7;
    let mut dp = [MAX; M];
    dp[0] = 0;
    for i in 0..n {
        let (i, i3, i5) = (i % M, (i + 3) % M, (i + 5) % M);
        dp[i3] = dp[i3].min(dp[i] + 1);
        dp[i5] = dp[i5].min(dp[i] + 1);
        dp[i] = MAX;
    }
    let result = if dp[n % M] == MAX { -1 } else { dp[n % M] };
    println!("{}", result);
}

これで範囲外アクセスの心配はなくなります。配列のサイズがとても小さく済むことも嬉しいです。

しかしとてもコードの読み書きが大変になります。問題が解けるかどうかという点で見るとあまり変わりません。

もともと解けていた場合: より省メモリーで解けるけれど、解けることに変わりはない
もともとメモリー不足で解けなかった場合: おそらくメモリーだけ解消しても、繰り返し回数が多いままだとタイムアウトして、結局解けないはず

一応 std::deque を使う、または modint と組み合わせると狭い配列でももう少しスッキリ書けそうです。でも競技プログラミングとしては、このように複雑な書き方をしてまで省メモリーにしても仕方ないと思います。

検討 2. のまとめ

方法	評価
2a. 大きめの静的な配列を用意する	◎
2b. 少し大きめの動的な配列にする	◎
2c. 同じ大きさの動的な配列にして、ループ内で条件分岐	○
2d. 同じ大きさの動的な配列にして、最後を特殊処理	○
2e. 小さな配列を使いまわす	△

評価は、実装速度を優先したい、綺麗に書きたい、などコーディングスタイルによって変わります。

最後に

いろいろ並べました。結局は「よく見るコードには理由がある」ということでした。

どの方法でも「(*1) 初期化忘れ」「(*2) 範囲外アクセス」を防げます。これらの中で、好みの DP の書き方が見つかりましたら幸いです。

おまけ: DP を使わない場合

ところでこの問題は DP 無しでも解けます。できるだけ 5個のボールを取る回数を多くするためには、5で割りきれるまでの最小限の回数だけ 3個のボールを取る、とすれば良いのでした。

次のコードで、制約条件を超える N=10,000,000,000 などが与えられたとしても、一瞬で解けます。

3.cpp

#include <iostream>

using namespace std;

int main()
{
    long long n;
    cin >> n;

    long long m = 0;
    while (m % 5 != n % 5) { 
        m += 3;
    }
    long long result = -1;
    if (m <= n) {
        result = m / 3 + (n - m) / 5;
    }
    cout << result << endl;
}

3.rs

use proconio::input;

fn main() {
    input! {
        n: i64,
    }
    let mut m = 0;
    while m % 5 != n % 5 {
        m += 3;
    }
    let result = if m <= n { m / 3 + (n - m) / 5 } else { -1 };
    println!("{}", result);
}

AtCoder ABC に Rust で参加しています。C++ のコード例も書くと、もしかすると記事を読む人が増えるかも、くらいの感じです。 ↩
AtCoder 2023 年言語アップデートで Rust 1.43 の usize::MAX などが使えるようになるのを楽しみにしています。しかし DP 初期化としてはオーバーフローしやすく、使い勝手が良くないかもしれません。 ↩
std::optional を使って可読性の方向に振ることもできます。 1c-cpp23.cpp では C++23 に追加予定のモナド風操作を行っています。dp[i + 3] = dp[i + 3].and_then(f).or_else(g); のように「dp[i + 3] が有効なら min() を適用する」「dp[i + 3] が無効なら optional(x) を入れる」と書けます。流れが分かりやすいです。こちらも AtCoder 2023 年言語アップデートで使えるようになるかもしれません。 ↩

競プロの DP 実装時の初期化忘れと範囲外アクセスを防ごうとする話

はじめに

TL;DR

今回扱う問題

配る DP で解くイメージ

よくある解答

ところで std:array

検討 1. 初期化について

初期化を忘れると

方法 1a. 到達不能を極端に大きな値で示す

問題設定によって初期値を調整する

方法 1b. 到達不能を -1 で示す

方法 1c. 到達不能を値を持たない Optional 型で示す

検討 1. のまとめ

検討 2. 範囲外アクセスについて

方針 2a. 大きめの静的な配列を用意する

方針 2b. 少し大きめの動的な配列にする

方針 2c. 同じ大きさの動的な配列にして、ループ内で条件分岐

方針 2d. 同じ大きさの動的な配列にして、最後を特殊処理

方針 2e. 小さな配列を使いまわす

検討 2. のまとめ

最後に

おまけ: DP を使わない場合