SRM 302 DIV1 Hard JoinedString
問題
単語列wordsが与えられる。それらを全て含む、長さ最小の文字列の辞書順最小を求めよ
- 1 <= |words| <= 12
- 1 <= |words[i]| <= 50
解答
まず、他の文字列に含まれている関係にある文字列たちを除去する。
この除去された文字列は他の文字列に含まれるので、考えなくても問題の制約は満たすことに注意。
こうすると、最後に使った単語と次に使う単語だけから、その連結の最小の長さが求められる。
前の前の単語の前まで「めり込む」ことは無いことに注意すると(それがもしあれば、次の単語は前の単語を含んでいることになってしまう)、
前の単語への「めり込み」ができるだけ大きい位置でやればいいことがわかる。これは純粋に全探索すればいい。
考えればわかるが、既に使った他の単語を経由することで短くなるということは無いので、答えは単語の順列になる。
これで(使った単語のbitmask * 最後に使った単語 -> 最小長さ) のDPができる。
辞書順最小は、追加される単語片を考えて、それで辞書順最小greedyを普通にやればいい。
コメント
自分は最初1文字ごとの状態を持つ奴+状態が増加するDPも気づかずに後ろからBFSをやって遅く、しかもTLEした。
それはBFSを高速化したらギリギリ(1.9s+)通ったが、複雑だしこの問題には意味ないと思う。
とりあえず、極大な単語のみを考える、というのは文字列とかでは考えよう。
しかし答えが順列になるというのも気づかないというのは…うーん…
コード
冷静に考えれば自明であるDP(+経路復元風辞書順greedy)バージョン
#include <string> #include <vector> #include <algorithm> #include <cstring> #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i)) #define all(o) (o).begin(), (o).end() #define pb(x) push_back(x) #define mp(x,y) make_pair((x),(y)) #define mset(m,v) memset(m,v,sizeof(m)) #define INF 0x3f3f3f3f using namespace std; typedef vector<int> vi; typedef vector<string> vs; int edge[51][51]; int dp[51][1<<12]; struct JoinedString { int n; vs w; //一番最後にw[i]を使って、mask状態であるやつ int rec(int i, int mask) { if(dp[i][mask] != -1) return dp[i][mask]; int r = INF; if(mask == (1 << n) - 1) r = 0; else rep(j, n) if((~mask >> j & 1) && edge[i][j] != INF) { //他のやつを経由してやる方法の方が短くなるということはないので、maskが増加するもののみを試せる。だからDPできる r = min(r, edge[i][j] + rec(j, mask | (1 << j))); } return dp[i][mask] = r; } string joinWords(vector <string> words) { //同じものはそれで閉路を作り、バグとしては、両方が削除されてしまったり残ってしまったりする。 //閉路が作られるのは包含関係(など(preでない)順序関係)において同じ(同値の)ときのみ。場合によるが、たいてい初めにunique(ここの同値判定に注意)してしまうのがよい sort(all(words)); words.erase(unique(all(words)), words.end()); n = words.size(); //極大のもののみを抽出するというのは列検索系などの問題において典型だろう。考えるべき vi indeg(n); rep(i, n) rep(j, n) if(i != j) { int m = words[i].size(), p = words[j].size(); if(m > p) continue; rer(k, 0, p - m) if(words[i] == words[j].substr(k, m)) indeg[i] ++; } rep(i, n) if(indeg[i] == 0) w.pb(words[i]); n = w.size(); w.pb("?"); //初期状態 mset(edge, INF); rep(i, n+1) rep(j, n+1) { int m = w[i].size(); //前の単語にどの程度'めり込める'か。極大であるので、完全にめり込み過ぎることはないことに注意 //minを取っていることにも注意。はみ出ている部分の長さを求めている。 rer(k, 1, m) if(w[i].substr(k, m - k) == w[j].substr(0, m - k)) edge[i][j] = min(edge[i][j], (int)w[j].size() - (m - k)); } mset(dp, -1); string r = ""; int ci = n, mask = 0; while(mask != (1 << n) - 1) { pair<string,int> p = mp("~", -INF); rep(j, n) if(rec(ci, mask) == edge[ci][j] + rec(j, mask | (1 << j))) p = min(p, mp(w[j].substr((int)w[j].size() - edge[ci][j]), j)); r += p.first; ci = p.second, mask |= 1 << p.second; } return r; } };
1文字ずつのパターンマッチング状態を圧縮せずに持ってBFSしてギリギリ(1.9s+)バージョン
パターンマッチング状態とaccept状態の生成の例としてはいいと思う。
このパターンマッチング状態を持つやつは、1文字ずつ処理することが求められるような問題に真価を発揮するっぽいかな。行列累乗がその典型と。
#include <string> #include <vector> #include <queue> #include <cstring> #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i)) #define each(it,o) for(__typeof((o).begin()) it = (o).begin(); it != (o).end(); ++ it) #define pb(x) push_back(x) #define mset(m,v) memset(m,v,sizeof(m)) #define INF 0x3f3f3f3f using namespace std; typedef vector<int> vi; int next[12*51][26]; int accept[12*51]; vi invgraph[12*51]; int memo[12 * 51][1<<12]; struct State { int s, mask, len; State(int s_, int mask_, int len_): s(s_), mask(mask_), len(len_) {} }; struct JoinedString { string joinWords(vector <string> words) { int n = words.size(); mset(next, -1); mset(accept, 0); rep(i, n) { int m = words[i].size(); rer(j, 0, m) { string prefix = words[i].substr(0, j); for(int l = j; l >= 0; l --) rep(k, n) if(prefix.substr(l, j - l) == words[k].substr(0, j - l)) { if(words[k].size() == j - l) { accept[i * 51 + j] |= 1 << k; continue; } char c = words[k][j - l]; next[i * 51 + j][c - 'A'] = k * 51 + (j - l + 1); } } } rep(i, n) rer(j, 0, words[i].size()) invgraph[i * 51 + j].clear(); rep(i, n) rer(j, 0, words[i].size()) rep(c, 26) if(next[i * 51 + j][c] != -1) invgraph[next[i * 51 + j][c]].pb(i * 51 + j); { mset(memo, INF); deque<State> q; rep(i, n) rer(j, 0, words[i].size()) q.push_back(State(i * 51 + j, ((1 << n) - 1) & ~accept[i * 51 + j], 0)); while(!q.empty()) { State t = q.front(); q.pop_front(); if(memo[t.s][t.mask] != INF) continue; memo[t.s][t.mask] = t.len; //BFSの(定数倍)高速化をしないとTLE rep(i, n) if(~t.mask >> i) if(memo[t.s][t.mask | (1 << i)] > t.len) q.push_front(State(t.s, t.mask | (1 << i), t.len)); each(i, invgraph[t.s]) if(memo[*i][t.mask & ~accept[*i]] > t.len + 1) q.push_back(State(*i, t.mask & ~accept[*i], t.len + 1)); } } string res = ""; int anslen = memo[0][0]; int currentst = 0, currentmask = accept[0]; rep(pos, anslen) { rep(c, 26) { int nextst = next[currentst][c]; if(nextst == -1) continue; int nextmask = currentmask | accept[nextst]; if(pos + 1 + memo[nextst][nextmask] == anslen) { res += char('A' + c); currentst = next[currentst][c]; currentmask = nextmask; break; } } } return res; } };
