今日の精進-DFS(AtCoder ABC268-D)
今日、解き直した問題は AtCoder ABC268-D「Unique Username」です。DFSも苦手です。
問題
ポイント
$${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;
}
公式解説では、文字列に1つ目の「 _ 」を加える操作をDFSの中で行っていましたが、次回この問題に挑戦するときがあったら、きっと自分だったらあらかじめ「 _ 」を付けたものを用意しそうだなぁと思ったので、それでACできるようにしました。DFSも少しシンプルになったので、DFSが苦手な自分にはよかったなと。
次回もがんばります。
この記事が気に入ったらサポートをしてみませんか?