Tamflexの貯蔵庫

やる気のない備忘録

abc 031

D問題

abc031.contest.atcoder.jp

数字iがa[i-1]の長さの文字列に対応しているとして、深さ優先探索で解く。最大9種類のパターンに対しそれぞれ最大3文字なので3^9 = 19683通りしかないので時間内に解けそう。判定はそれぞれのデータセット(v,w)に対して

  1. Σ{i = 0 .. v.length() }a[v(i)] == w.length ?
  2. 切り分けたパターンを保存し不一致が存在しないか?

を判定すればOK?

int k, n;
int a[9];           // length of i
vector<int> d[55];  // v
string s[55];       // w
string t[9];        // answer

bool dfs(int dep)
{
  if (dep == k)
  {
    REP(i,k) t[i] = "";
    REP(i,n) // check match for each v w
    {
      int p = 0;
      for (int x : d[i])
      {
        string y = "";
        REP(j,a[x])
        {
          if (p < s[i].size())
          {
            y += s[i][p];
            p++;
          }
        }
        if (y.size() != a[x]) return false;
        // don't match length
        if (t[x] == "") t[x] = y;
        else if (t[x] != y) return false;
        // don't match contents
      }
      if (p != s[i].size()) return false;
      // don't reach the end
    }
    REP(i,k)
    {
      cout << t[i] << endl;
    }
    return true;
  }
  FOR(l,1,3)
  {
    a[dep] = l;
    if (dfs(dep+1)) return true;
  }
  return false;
}

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  // FROM HERE
  cin >> k >> n;
  REP(i,n)
  {
    int x; cin >> x;
    cin >> s[i];
    while (x)
    {
      d[i].push_back(x%10-1);
      x /= 10;
    }
    reverse(ALL(d[i]));
  }
  dfs(0);
  return 0;
}