今日の精進-DFS（AtCoder ABC268-D）

今日、解き直した問題は AtCoder ABC268-D「Unique Username」です。DFSも苦手です。

問題

D - Unique Username

ポイント

• $${1 \leq N \leq 8}$$ なので、 文字列 $${S}$$ の並び順のパターンは順列全探索で作れる。

• 文字列と文字列の間には「 _ 」が必ず1つは入るから順列全探索で作った $${S}$$ に「 _ 」を加えておく（最後の文字列は除く）。

• 追加することができる「 _ 」の数はあらかじめ数えておく。

• あとは $${3 \leq X \leq 16}$$ を満たす範囲で、
  ・文字列と文字列をつなぐのか
  ・文字列に「 _ 」を加えるのか
  をDFSで試して、$${T}$$ になければ出力すればいい。

ACしたコード

ACしたコードは下記の通りです。

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
// using mint = modint998244353;
// using mint = modint1000000007;
// const int mod = 1000000007;
// const ll INF = 1LL << 62;
// const int INF = 1001001001;

void dfs(vector<string> &v, int limit, string res, map<string,int> &mp, int now) {
  if (limit < 0) {
    return;
  }
  if (now == (int) v.size()) {
    if (3 <= (int) res.size() && mp[res] != 1) {
      cout << res << endl;
      exit(0);
    } else {
      return;
    }
  }

  // 次の文字列を加える場合
  dfs(v, limit, res + v[now], mp, now + 1);
  if (res != "") {
    // 文字列に「 _ 」を加える場合
    dfs(v, limit - 1, res + "_", mp, now);
  }
}

int main() {
  int N, M;
  cin >> N >> M;
  vector<string> S(N);
  rep(i, N) {
    cin >> S[i];
  }
  map<string, int> mp;
  rep(i, M) {
    string T;
    cin >> T;
    mp[T] = 1;
  }

  sort(S.begin(), S.end());

  int limit = 16;
  rep(i, N) {
    limit -= (int) S[i].size();
  }
  limit -= N - 1;

  do {
    // 文字列に _ を加えておく（最後の文字列は除く）
    vector<string> S2;
    rep(i, (int) S.size()){
      if (i != (int) S.size() - 1) {
        S2.push_back(S[i] + "_");
      } else {
        S2.push_back(S[i]);
      }
    }
    
    dfs(S2, limit, "", mp, 0);

  } while(next_permutation(S.begin(), S.end()));

  cout << "-1" << endl;
  return 0;
}

提出 #49576179 - ユニークビジョンプログラミングコンテスト2022 夏(AtCoder Beginner Contest 268)

公式解説では、文字列に1つ目の「 _ 」を加える操作をDFSの中で行っていましたが、次回この問題に挑戦するときがあったら、きっと自分だったらあらかじめ「 _ 」を付けたものを用意しそうだなぁと思ったので、それでACできるようにしました。DFSも少しシンプルになったので、DFSが苦手な自分にはよかったなと。
次回もがんばります。