アルゴリズム活用力は, 主にコーディングの試験の際に見られるところであり, webアプリやモバイルアプリを作るのにはあまり必要ないかもしれない. しかし, 将来転職する際にAtcoderである程度の成績を納めていたら強いのではという理由と, 単に楽しいからという理由で蟻本の中級くらいやりたいなと思っている. ってか, 今日のAtcoder全然解けへんくて萎えた…

今回は, 2_3 値を覚えて再利用"動的計画法"を勉強した.

01ナップサック問題

dpを使った動的計画法の初歩が書かれていた. 全探索を行うとO(2^n)かかってしまうところが, メモ化によりO(nW)の計算量で済む. この問題のコツは, 品物と重さを引数として価値の総和を出した時に計算結果を残しておくという発想から.


const int MAX_N = 100;
int n, W;
int w[MAX_N], v[MAX_N];
// dp[i+1][j]: i番目までの品物から重さの総和がj以下となるように選んだ時の,
// 価値の総和の最大値
int dp[MAX_N + 1][MAX_N + 1];
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> w[i] >> v[i];
    }
    cin >> W;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= W; j++) {
            if (j < w[i]) {
                dp[i + 1][j] = dp[i][j];
            } else {
                dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]);
            }
        }
    }
    printf("max sum value is %d\n", dp[n][W]);
    return 0;
}

参考: メモ化テーブルを初期化する方法

memset(dp, -1, sizeof(dp));

ってな感じで, 0と-1ならば初期化できる. 1はできない.

最長共通部分列問題

この問題のコツは, 2つも文字列を引数とした計算結果をメモ化するところである. 最初のうちはDPテーブルをかくと漸化式が浮かびやすいかなと思う.


const int MAX_N = 1000;
int n, m;
char s[MAX_N], t[MAX_N];
int dp[MAX_N][MAX_N];
int main() {
    cin >> n >> m >> s >> t;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (s[i] == t[j]) {
                dp[i + 1][j + 1] = dp[i][j] + 1;
            } else {
                dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);
            }
        }
    }
    cout << "max value is " << dp[n][m] << endl;
    return 0;
}

個数制限なしのナップサック問題

個数制限がなくなったことで, 愚直に計算するとforループがもう一つ増えてしまう. そこで無駄に計算を行なっている箇所を探して, 漸化式を簡単にする. コツとしては, DPテーブルをみて漸化式の動きをみて, 簡単になる箇所がないかを探すのみだと思う.

参考: 偶奇を考えた配列の再利用

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

(i + 1) & 1の使い方がめちゃうまい気がする… こうして, 2行分のデータを確保できる.

01ナップサック問題その2

重さの制約条件が緩くなって, Wが10^9まで飛んでしまった時は, Wでforループを回したくなくなる. そんなときは, メモ化けする対象を入れ替えることでうまくいく. メモ化の値に大きくなるものを入れるのがコツな気がする.


const int MAX_N = 100;
const int MAX_V = 100;
const int INF = 99999999;
int n, W;
int w[MAX_N], v[MAX_N];
// dp[i+1][j]: i番目までの品物から価値の総和がjとなるよう選んだときの,
// 重さの総和の最小値 そのような解が存在しない場合は十分大きな値INF
int dp[MAX_N + 1][MAX_N * MAX_V + 1];
int main() {
    // 入力値の読み込み
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> w[i] >> v[i];
    }
    cin >> W;
    // 解く
    fill(dp[0], dp[0] + MAX_N * MAX_V + 1, INF);
    dp[0][0] = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= MAX_N * MAX_V; j++) {
            if (j < v[i]) {
                dp[i + 1][j] = dp[i][j];
            } else {
                dp[i + 1][j] = min(dp[i][j], dp[i][j - v[i]] + w[i]);
            }
        }
    }
    int res = 0;
    for (int i = 0; i <= MAX_N * MAX_V; i++) {
        if (dp[n][i] <= W) {
            res = i;
        }
    }
    printf("max sum value is %d\n", res);
    return 0;
}

個数制限付き部分和

bool値をメモ化けするのは無駄がある. そこで大きな値である残りのa_iを入れることで漸化式が改善されて計算量を落とすことができる.


const int MAX_N = 100;
const int MAX_K = 100000;
int n;
int K;
int a[MAX_N];
int m[MAX_N];
// dp[i+1][j]: i番目まででjを作る際に余る最大のi番目の個数(作れない場合は-1)
int dp[MAX_K];
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> m[i];
    }
    cin >> K;
    memset(dp, -1, sizeof(dp));
    dp[0] = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= K; j++) {
            if (dp[j] >= 0) {
                dp[j] = m[i];
            } else if (j < a[i] || dp[j - a[i]] < 0) {
                dp[j] = -1;
            } else {
                dp[j] = dp[j - a[i]] - 1;
            }
        }
    }
    if (dp[K] > 0) {
        printf("answer is YES\n");
    } else {
        printf("answer is NO\n");
    }
    return 0;
}

最長増加部分列問題

案外奥が深い問題. 部分文字列の候補があがってくるのでそれをメモ化するとO(n^2)で解くことができるが, 候補よりも, 最終要素がなにであるかに着目するとO(n \log n)で解くことができる. ここらへんは地頭の良さ.

参考: lower_bound

fill(dp, dp + n, INF);
for (int i = 0; i < n; i++) {
    * lower_bound(dp, dp + n, a[i]) = a[i];
}
printf("%ld\n", lower_bound(dp, dp + n, INF) - dp);

ってな感じで, ソートされた列aから二分探索でa_i <= kとなりような最小のa_iのポインタを求めることができる.

分割数

最適化だけでなく場合の数にも応用.


const int MAX_N = 1000;
const int MAX_M = 1000;
int n, m;
int M;
int dp[MAX_M + 1][MAX_N + 1];
int main(int argc, char const *argv[]) {
    cin >> n >> m;
    cin >> M;
    dp[0][0] = 1;
    for (int i = 1; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (j >= i) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - i];
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    printf("%d\n", dp[m][n] % M);
    return 0;
}

重複組み合わせ

これはめちゃめちゃ難しかった. これも,

  • 何をメモ化するか
    • 漸化式が作れるように
    • 計算量が多くならないように
  • 1つ前の値を意識する
    • DPテーブルから漸化式を導き出す

みたいなところが大事である.


const int MAX_N = 1000;
int n, m;
int a[MAX_N + 1];
int M;
int dp[MAX_N + 1][MAX_N + 1];
int main(int argc, char const *argv[]) {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    cin >> M;
    // 1つも選ばない方法は常に1通り
    for (int i = 0; i <= n; i++) {
        dp[i][0] = 1;
    }
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            if (j - 1 - a[i] >= 0) {
                dp[i + 1][j] =
                    (dp[i + 1][j - 1] + dp[i][j] - dp[i][j - 1 - a[i]] + M) % M;
            } else {
                dp[i + 1][j] = (dp[i + 1][j - 1] + dp[i][j]) % M;
            }
        }
    }
    printf("%d\n", dp[n][m]);
    return 0;
}

感想

蟻本なかなか重たい. 結構な練習を積まないと身につかない. やっぱり初級編だけ終わらせようかなと思ってきた…