AtCoder Beginner Contest過去問003

AtCoder Beginner Contest 003を解きました。 atcoder.jp

f:id:NM_MN:20190220153308p:plain D問題は難易度が高く101点満点中、100点がもらえるところまでやりました。そのうちまた挑戦して101点の回答を作りたいです。 さて前回記事(ブログ移転しました)でも記した通り、ABC113の問題を解くために動的計画法について学びました。今回のD問題で早速それを使えるタイミングがありました。

1.組み合わせ _ nC _ k を出力するプログラムは面倒くさい

D問題を解くためにcombinationを利用する必要がありました。よく使いそうなのにC++にはcombinationを扱う関数が無いようなのです(もしあったら教えて下さい)。 そこでcombinationの数を出力する関数を自分で作る必要がありました。

まず思いつくのが定義式を用いる方法。combinationは次の式で求めることが出来ます。

_ nC _ k = \frac{n!}{k!(n-k)!}

が！！！この定義式を用いると階乗の計算をしなければいけません。問題の条件を見ると900の階乗まで扱う可能性があります。こんなのオーバーフローするに決まっています。 定義式を使う方法はダメなので違う方法を考える必要がありました。

2. 漸化式を用いる

combination、もとい二項係数の求め方として次の漸化式を用いる方法があります。

_ nC _ k = _ {n-1}C _ {k-1} + _ {n-1}C _ {k}

_ nC _ 0 = _ nC _ k = 1

この漸化式を用いてcombinationを求める関数がこうです。

int comb(int n, int k) {
    if (k == 0 || n == k)return 1;
    else return comb(n - 1, k - 1) + comb(n - 1, k);
}

実に簡単な実装ですがこれでは上手くいかないことを僕は前回の過去問で学んでいます。再帰的な処理を行うといちいち初項付近まで浮き上がるハメになり、一度得た計算結果を再利用することが出来ません。ここで扱うのが動的計画法のメモ化です。 階層の深いところから再帰的に処理するのではなく、浅い階層からメモしながら深い階層へと潜っていきます(パスカルの三角形を上から書いていくのに等しいです)。

    vector<vector<long long>>comb(n + 1, vector<long long>(n + 1, 0));
    for (int i = 0; i < n + 1; i++) {
        comb[i][0] = 1;
        comb[i][i] = 1;
    }
    for (int i = 1; i < n + 1; i++) {
        for (int j = 1; j < k + 1; j++) {
            comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j];
        }
    }

こうすれば再帰的な処理を含まないので高速に計算することが出来ます。しかも計算結果は保管されているので _ nC _ k はcomb[n][k]として簡単に取り出せます。

3.まとめ

今回はアルゴリズムで新しい学びがあったと言うよりは、前回学んだ内容がそのまま活かせたのがとても満足でした(細かい話をするとmodあたりで学びはあったのだが)。 それと401点中400点まではスムーズに書くことが出来たので手ごたえを感じています。また過去問を解きつつ、リアルタイムでコンテストに参加するのを次の目標としたいです。

4.参考文献

Wikipedia 「組み合わせ(数学)」

Wikipedia 「二項係数」

「組み合わせ(nCr)をC++で実装して時間計測」