SRM524 Div2 Hard

1000
少し前に解いた問題と似た雰囲気があるからどうにかなった。
[最後に使った数字][これまでの余り]を状態にしたBFSで計算できる。筆算を思い浮かべる。
こういう問題は面白いと感じる。

view plainprint?

1. class MultiplesWithLimit {  
2. public:  
3.   string minMultiples(int N, vector <int> D)   
4.   {  
5.     sort(D.begin(), D.end());  
6.       
7.     const int MOD = 10000;  
8.     const int LAST = 10;  
9.   
10.     bool vis[LAST][MOD];  
11.     fill(&vis[0][0], &vis[LAST - 1][MOD], false);  
12.   
13.     int len[LAST][MOD];  
14.     fill(&len[0][0], &len[LAST - 1][MOD], 0);  
15.   
16.     pair<int, int> path[LAST][MOD];      
17.   
18.     queue< pair<int, int> > q;  
19.     for (int n = 1; n < 10; ++n) {  
20.       if (binary_search(D.begin(), D.end(), n)) continue;  
21.       q.push(make_pair(n, n % N));  
22.       vis[n][n % N] = true;  
23.     }  
24.   
25.     pair<int, int> p = make_pair(-1, -1);  
26.     for (; q.size(); q.pop()) {  
27.       p = q.front();  
28.       if (vis[p.first][p.second] && p.second == 0) break;  
29.       for (int n = 0; n < 10; ++n) {  
30.         if (binary_search(D.begin(), D.end(), n)) continue;  
31.         int m = (p.second * 10 + n) % N;  
32.         if (vis[n][m]) continue;  
33.         vis[n][m] = true;  
34.         path[n][m] = p;  
35.         q.push(make_pair(n, m));  
36.       }  
37.     }          
38.   
39.     if (p.second) return "IMPOSSIBLE";  
40.   
41.     string s;  
42.     while (true) {  
43.       if (s.size() && p.second == 0) break;  
44.       s += '0' + p.first;  
45.       p = path[p.first][p.second];  
46.     }  
47.     reverse(s.begin(), s.end());  
48.       
49.     if (9 <= s.size()) {  
50.       char buff[100];  
51.       int size = s.size();  
52.       sprintf(buff, "%c%c%c...%c%c%c(%d digits)",   
53.               s[0], s[1], s[2], s[size-3], s[size-2], s[size-1], size);  
54.       s = string(buff);  
55.     }  
56.   
57.     return s;  
58.   }  
59.   
60. };  

class MultiplesWithLimit {
public:
  string minMultiples(int N, vector <int> D) 
  {
    sort(D.begin(), D.end());
    
    const int MOD = 10000;
    const int LAST = 10;

    bool vis[LAST][MOD];
    fill(&vis[0][0], &vis[LAST - 1][MOD], false);

    int len[LAST][MOD];
    fill(&len[0][0], &len[LAST - 1][MOD], 0);

    pair<int, int> path[LAST][MOD];    

    queue< pair<int, int> > q;
    for (int n = 1; n < 10; ++n) {
      if (binary_search(D.begin(), D.end(), n)) continue;
      q.push(make_pair(n, n % N));
      vis[n][n % N] = true;
    }

    pair<int, int> p = make_pair(-1, -1);
    for (; q.size(); q.pop()) {
      p = q.front();
      if (vis[p.first][p.second] && p.second == 0) break;
      for (int n = 0; n < 10; ++n) {
        if (binary_search(D.begin(), D.end(), n)) continue;
        int m = (p.second * 10 + n) % N;
        if (vis[n][m]) continue;
        vis[n][m] = true;
        path[n][m] = p;
        q.push(make_pair(n, m));
      }
    }        

    if (p.second) return "IMPOSSIBLE";

    string s;
    while (true) {
      if (s.size() && p.second == 0) break;
      s += '0' + p.first;
      p = path[p.first][p.second];
    }
    reverse(s.begin(), s.end());
    
    if (9 <= s.size()) {
      char buff[100];
      int size = s.size();
      sprintf(buff, "%c%c%c...%c%c%c(%d digits)", 
              s[0], s[1], s[2], s[size-3], s[size-2], s[size-1], size);
      s = string(buff);
    }

    return s;
  }

};