D - 語呂合わせ 〜ABC031〜

問題

D - 語呂合わせ

考え方

深さ優先探索でぐるぐる回す。n の数だけクエリがあるが，これを全部足し合わせて一つの文字列 sum_v, sum_w について深さ優先探索をすると楽に解ける。

計算量が気になったが，各語呂合わせの文字の制約で3文字以下に収まるということがあったので多分大丈夫であった。

Accepted Program

#include <iostream>
#include <string>
using namespace std;

int stamp[10] = {
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0  
};

string sum_v = "";
string sum_w = "";
int k, n;
string ans[9 + 1];
string v[51], w[51];

bool dfs (int s, int ss) {
  if (s >= sum_v.size() && ss < sum_w.size()) {
    return false;  
  }
  if (ss >= sum_w.size() && s < sum_v.size()) {
    return false;  
  }
  if (s == sum_v.size() && ss == sum_w.size()) {
    for (int i = 0; i < n; i++) {
      string sub = "";
      for (int j = 0; j < v[i].size(); j++) {
        int itr = v[i][j] - '0';
        sub = sub + ans[itr];   
      }   
      if (sub != w[i]) {
        return false;  
      }
    }      
    return true;
  }
  int now = sum_v[s] - '0';
  if (stamp[now] == 1) {
    for (int i = 0; i < ans[now].size(); i++) {
      if (ss + i >= sum_w.size()) {
        return false;  
      }
      if (ans[now][i] != sum_w[ss + i]) {
        return false;    
      }  
    }  
    return dfs(s + 1, ss + ans[now].size());
  }
  else {
    string sub = "";
    for (int i = 0; i < 3; i++) {
      stamp[now] = 1;
      if (ss + i >= sum_w.size()) {
        stamp[now] = 0;
        break;  
      }
      sub += sum_w[ss + i];
      ans[now] = sub;
      if (dfs(s + 1, ss + i + 1)) {
        return true;  
      } 
      stamp[now] = 0;
    }
    return false;
  }
}

int main () {
  cin >> k >> n;
  for (int i = 0; i < n; i++) {
    cin >> v[i] >> w[i];   
    sum_v += v[i];
    sum_w += w[i];
  }  
  for (int i = 0; i <= k; i++) {
    ans[i] = "";    
  }
  if (dfs(0, 0)) {
    for (int i = 1; i <= k; i++) {
      cout << ans[i] << endl;     
    }
  }
}