Search on the blog

2010年11月7日日曜日

部分和を列挙する

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

SRM 403 devision2 Hard:

簡単に要約すると、
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」とか選択できるみたいです。

0 件のコメント:

コメントを投稿