Codeforces 119 A Cut RibbonをDPで解く

簡単なDPの良問を見つけたので「DP分からんから競プロやめます」という人向けにメモ（僕もEditorialが理解できずに辞めかけました（8割嘘です））．

問題

長さが のリボンがある．これを長さ を単位としてカットしたい．カットされたリボンが最も多くなるようにカットした時のリボンはいくつになっている？

考え方

リボンをカットしていくことをシミュレーションしようとすると，リボンがどんどん短くなっていくので実装するときに配列の位置と残りのリボンの長さが逆になってややこしい．この問題を，「長さ のリボンのパーツがそれぞれ無限にある．これらをつなぎ合わせて長さ のリボンを作る．リボンのパーツが一番多くなるように作った時，使われたパーツの数はいくつ？」というふうに読み替えてみる．

入力例の1つ目 n, a, b, c = 5, 5, 3, 2 で考える．まず，リボンの配列 r を作り，r[a], r[b], r[c] をそれぞれ1で初期化する．この初期化は，はじめにリボンの位置0からそれぞれ長さa, b, cのリボンのパーツを置いたパターンを記録しておくことを意味する．r はこの事象が重ね合わせで記録されていることになる．

[0, 0, 0, 0, 1] ■■■■■
[0, 0, 1, 0, 0] ■■■□□
[0, 1, 0, 0, 0] ■■□□□
↓
[0, 1, 1, 0, 1]

次に，この配列 r を頭から走査していく．r[i] が1以上ということは，ここまで一番多くのリボンパーツを使って長さ までやって来たことを意味する．このとき，位置 i から新たに長さa, b, cのリボンパーツをつなげることを考える．位置 i に対して長さ のリボンパーツをつなげることを考えよう．このとき，長さ まで他の方法でより多くのパーツを使ってたどり着いているかもしれない．すなわち，今まで長さ のリボンを作ってきた方法にさらに長さ のリボンパーツをつなげる方法と，他のやり方で長さ のリボンを作る方法のうち，より多くのパーツを使っている方法を選ばなければならない．これは r[i + e] = max(r[i] + 1, r[i + e]) として表せる．maxの第1項が前者，第2項が後者に対応している．

上の例でシミュレーションしてみよう．インデックスはリボンの長さ，中の数はそこまで使った一番多くのパーツ数を意味している．

 1, 2, 3, 4, 5  ← i
[0, 1, 1, 0, 1]
    ↑ 最初は i = 2
[0, 1, 1, 2, 1]
    i     ↑ 長さは 2 + 2 = 4. パーツの個数は 1 + 1 = 2.
つまり，この時点では長さ4まで長さ2のリボン2つを使ったと言える
[0, 1, 1, 2, 2]
    i        ↑ 長さは 2 + 3 = 5. パーツの個数は 1 + 1 = 2.
長さ5のリボンを1つ使うより，長さ2と3のリボンを1つずつ使ったほうが
個数が多くなるので r[5] が更新された
長さ2に長さ5のリボンパーツをつなぐと必要な長さ5からはみ出るので省略

[0, 1, 1, 0, 1]
       ↑ 次は i = 3
[0, 1, 1, 2, 2]
             ↑ 長さ: 3 + 2 = 5, 個数: 1 + 1 = 2
r[5] は長さ2と3のリボンパーツをつなげた2個が最大だった
長さ3と2のリボンパーツを使っても個数は同じ
これよりあとのパターンは全て全体の長さ5をはみ出すので省略

この手続きを右端まで繰り返すと，r[5] は長さ5まで最も多くのパーツを使った時の個数が記録されていることになる．したがって，答えとしては r[5] をそのまま出力すればよい．

プログラム

import std.stdio, std.algorithm, std.string, std.conv, std.range;

void main() {
    int n, a, b, c;
    readf("%d %d %d %d\n", &n, &a, &b, &c);
    dp(n, a, b, c).writeln;
}

int dp(int n, int a, int b, int c) {
    int[] r = new int[n + 1];
    // 初期化の部分
    foreach (e; [ a, b, c ]) {
        // パーツがそもそも全体の長さを超えている時がある
        if (e <= n) {
            r[e] = 1;
        }
    }

    foreach (int i, ref e; r) {
        // 何らかの方法で i までたどり着いたなら……
        if (e > 0) {
            // 長さ a, b, c のそれぞれのパーツをつなげるやり方について
            // （長さを変数 cut で表す）
            foreach (cut; [ a, b, c ]) {
                // つなげても n からはみ出さなければ
                if (i + cut <= n) {
                    // r[i] に長さ cut のリボンをつなぐ時と
                    // 他の方法で r[i + cut] までたどり着く時のうち
                    // より個数の多い方を記録する
                    r[i + cut] = max(r[i] + 1, r[i + cut]);
                }
            }
        }
    }

    // 上の走査によって，r[n] には長さ n のリボンを作る時の最大のパーツ数が記録されている
    return r[n];
}