部分和を列挙する

今日は、昨日練習した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で復元します。

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

view plainprint?

1. int dp[1000001];  
2.   
3. class TheSumOfLuckyNumbers {  
4. public:  
5.     void makeLucky(vector<int>&A, int x, int n) {  
6.         if (x)  
7.             A.PB(x);  
8.         if (x * 10 + 4 <= n)  
9.             makeLucky(A, x * 10 + 4, n);  
10.         if (x * 10 + 7 <= n)  
11.             makeLucky(A, x * 10 + 7, n);  
12.     }  
13.   
14.     vector<int> sum(int n) {  
15.         VI A;  
16.         makeLucky(A, 0, n);  
17.         SORT(A);  
18.   
19.         // DP  
20.         EACH(itr, A) {  
21.             dp[*itr] = 1;  
22.             REP(i, n+1) {  
23.                 if (!dp[i])  
24.                     continue;  
25.                 if (i + *itr > n)  
26.                     continue;  
27.                 if (!dp[i + *itr] || dp[i + *itr] >= dp[i] + 1)  
28.                     dp[i + *itr] = dp[i] + 1;  
29.             }  
30.         }  
31.   
32.         VI ret;  
33.         int pos = n;  
34.         // Greedy  
35.         EACH(itr, A) {  
36.             while (dp[pos] - dp[pos - *itr] == 1 && pos) {  
37.                 if (!dp[pos - *itr] && pos - *itr)  
38.                     break;  
39.                 ret.PB(*itr);  
40.                 pos -= *itr;  
41.                 if (pos - *itr < 0) break;  
42.             }  
43.             if (!pos)  
44.                 break;  
45.         }  
46.   
47.         return ret;  
48.     }  
49. };  

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