SRM 524 DIV2 1000 multipleswithlimit

modular arithmeticの絡んだ数論チックな問題（好きなタイプの問題）。余り毎にメモ化しておけばいいのはすぐ気付いたけど、最初のsubmissionでは、dp[2][10000]みたいにして、rolling table/flying tableを使って解いて、TLE。前回新しく更新されたところだけをpick upすればいいので、priority_queueを利用したダイクストラ法のようなやり方をすればいいのに気付く。これでAC。

（追記）editorial読んだら、queueでいいっぽい。最初に埋まったやつがbestになるから、確かにqueueでOK。

view plainprint?

1. typedef pair<int, pair<string, int> >  ISI;  
2. string dp[10000];  
3.   
4. class MultiplesWithLimit {  
5.     string format(string x) {  
6.         if (x.length() < 9)  
7.             return x;  
8.   
9.         char ret[512];  
10.         sprintf(ret, "%s...%s(%d digits)", x.substr(0, 3).c_str(), x.substr(x.length()-3).c_str(), x.length());  
11.   
12.         return ret;  
13.     }  
14.   
15.     bool contain(vector<int> vec, int n) {  
16.         REP(i, vec.size())  
17.             if (vec[i] == n)  
18.                 return true;  
19.   
20.         return false;  
21.     }  
22.   
23. public:  
24.     string minMultiples(int N, vector<int> forbiddenDigits) {  
25.         vector<int> nums;  
26.   
27.         REP(i, 10) {  
28.             if (!contain(forbiddenDigits, i))  
29.                 nums.push_back(i);  
30.         }  
31.   
32.         priority_queue<ISI, vector<ISI>, greater<ISI> > Q;  
33.         Q.push(MP(0, MP("", 0)));  
34.         string ret = "";  
35.   
36.         REP(i, 10000) dp[i] = "";  
37.         while (!Q.empty()) {  
38.             string str = Q.top().second.first;  
39.             int rm = Q.top().second.second;  
40.   
41.             Q.pop();  
42.             if (rm == 0 && str != "") {  
43.                 ret = str;  
44.                 break;  
45.             }  
46.             if (dp[rm].length() < str.length() ||  
47.                 (dp[rm].length() == str.length() && dp[rm] < str))  
48.                 continue;  
49.   
50.             REP(i, nums.size()) {  
51.                 int rm_t = (10 * rm + nums[i]) % N;  
52.                 string str_t = str + (char)(nums[i] + '0');  
53.   
54.                 if (str_t == "0") continue;  
55.                 if (dp[rm_t] == "" ||  
56.                     str_t.length() < dp[rm_t].length() ||  
57.                     (str_t.length() == dp[rm_t].length() && str_t < dp[rm_t])  
58.                 ) {  
59.                     dp[rm_t] = str_t;  
60.                     Q.push(MP(str_t.length(), MP(str_t, rm_t)));  
61.                 }  
62.             }  
63.         }  
64.   
65.         if (ret == "")  
66.             return "IMPOSSIBLE";  
67.   
68.         return format(ret);  
69.     }  
70. };  

typedef pair<int, pair<string, int> >  ISI;
string dp[10000];

class MultiplesWithLimit {
    string format(string x) {
        if (x.length() < 9)
            return x;

        char ret[512];
        sprintf(ret, "%s...%s(%d digits)", x.substr(0, 3).c_str(), x.substr(x.length()-3).c_str(), x.length());

        return ret;
    }

    bool contain(vector<int> vec, int n) {
        REP(i, vec.size())
            if (vec[i] == n)
                return true;

        return false;
    }

public:
    string minMultiples(int N, vector<int> forbiddenDigits) {
        vector<int> nums;

        REP(i, 10) {
            if (!contain(forbiddenDigits, i))
                nums.push_back(i);
        }

        priority_queue<ISI, vector<ISI>, greater<ISI> > Q;
        Q.push(MP(0, MP("", 0)));
        string ret = "";

        REP(i, 10000) dp[i] = "";
        while (!Q.empty()) {
            string str = Q.top().second.first;
            int rm = Q.top().second.second;

            Q.pop();
            if (rm == 0 && str != "") {
                ret = str;
                break;
            }
            if (dp[rm].length() < str.length() ||
                (dp[rm].length() == str.length() && dp[rm] < str))
                continue;

            REP(i, nums.size()) {
                int rm_t = (10 * rm + nums[i]) % N;
                string str_t = str + (char)(nums[i] + '0');

                if (str_t == "0") continue;
                if (dp[rm_t] == "" ||
                    str_t.length() < dp[rm_t].length() ||
                    (str_t.length() == dp[rm_t].length() && str_t < dp[rm_t])
                ) {
                    dp[rm_t] = str_t;
                    Q.push(MP(str_t.length(), MP(str_t, rm_t)));
                }
            }
        }

        if (ret == "")
            return "IMPOSSIBLE";

        return format(ret);
    }
};