SRM524 Div2 Hard

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

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;
  }

};