部分和を列挙する

今日は、昨日練習したTopCoderの問題について書きます。

SRM 403 devision2 Hard:

http://www.topcoder.com/stat?c=problem_statement&pm=8571

簡単に要約すると、

4と7のみから構成される数字をlucky numberと呼ぶ。

整数nが与えられたときlucky numberのみを足し合わせてnをつくることができる場合は、そのlucky numberを列挙せよ。ただし、そのような組み合わせが複数個ある場合は、個数が最小のもの、さらにそれが複数個ある場合は、辞書順で最小になるものを求めよ。

詳しくは、上のTopCoderのサイトを参照ください。

ここでポイントは、

1. lucky numberを探索してキャッシュすること
2. nがlucky numberのみで構成できるかどうかDPを使って判定すること
3. 構成出来る場合は、その解を問題の定義どおりに列挙すること

2.までは、出来たんだけど・・・

赤い人のコードを参考に復習しました。

まず、1.ですが再帰で書くとかなりスマートに書けます。

2.は部分和問題と同等の方法で書けます。dp[i]には整数iを構成するのに必要なlucky numberの最小値をキャッシュします。（私はdp[i]にiを構成するために必要なluckyu numberをvectorにぶち込んでキャッシュしてました。これだと、メモリ制限や時間制限でoutになりました。。）

3.は2.で作った配列を元に経路復元みたいなことをやります。その際、なるべく小さい数をたくさん取るように（辞書順で小さくなるように）greedyで復元します。

以下、（赤い人を参考に）私が書いたコードを張っておきます。

int dp[1000001];

class TheSumOfLuckyNumbers {
public:
    void makeLucky(vector<int>&A, int x, int n) {
        if (x)
            A.PB(x);
        if (x * 10 + 4 <= n)
            makeLucky(A, x * 10 + 4, n);
        if (x * 10 + 7 <= n)
            makeLucky(A, x * 10 + 7, n);
    }

    vector<int> sum(int n) {
        VI A;
        makeLucky(A, 0, n);
        SORT(A);

        // DP
        EACH(itr, A) {
            dp[*itr] = 1;
            REP(i, n+1) {
                if (!dp[i])
                    continue;
                if (i + *itr > n)
                    continue;
                if (!dp[i + *itr] || dp[i + *itr] >= dp[i] + 1)
                    dp[i + *itr] = dp[i] + 1;
            }
        }

        VI ret;
        int pos = n;
        // Greedy
        EACH(itr, A) {
            while (dp[pos] - dp[pos - *itr] == 1 && pos) {
                if (!dp[pos - *itr] && pos - *itr)
                    break;
                ret.PB(*itr);
                pos -= *itr;
                if (pos - *itr < 0) break;
            }
            if (!pos)
                break;
        }

        return ret;
    }
};

あと、気付きですが、TopCoderの過去問を解くのはPOJを解くよりも良いかもしれません。

その理由は、

1. 問題のレベル分けがきちんとなされている
2. 赤い人のコードや解説(editorial)が読める
3. すべての問題が種類別にカテゴライズされている。

3.のカテゴライズは今日気付きました。

Problem Archiveのところにcategoryってのがあるので、そこで「DP」とか「String manipulation」とか「recursive」とか選択できるみたいです。

http://www.topcoder.com/tc?module=ProblemArchive