SRM 291 DIV1 Hard StickedWords

問題 Editorial

問題

辞書dictが与えられる。
この辞書dictに含まれる単語を使ってしりとりをする。
ただし、同じ単語を複数使っても良い。
しりとりをして文字列を作ることが出来る。例えば"abc"と"cd"と"efgh"でしりとりすると"abcdefgh"という文字列になる。
その文字列のうち、len文字以上であって辞書順最小のものを求めよ

• 1 <= |dict| <= 50
• 2 <= |dict[i]| <= 50
• dictは英小文字アルファベットからなる
• 1 <= len <= 2500

解答

辞書順greedyっぽくやる。
これからできるかの判定には、アルファベットからアルファベットへの文字数グラフを作って、(len <= 今の文字数 + Max (i='a'..'z') { -dist[最後の文字][i] })のようなことをすればいい。
しかしそれぞれの要素の文字数が違うので単純な辞書順greedyではできない。
ならば文字数ごとに考えればいい。dp[i]をi文字の辞書順最小の文字列とすれば、(dp[i] = Min (w in dict, last dp[i-(|w|-1)] = head w) { dp[i-(|w|-1)] ++ tail w} )というふうにできる。
これの計算量は微妙な気もするが、単純に実装しても最大550ms程度で通る。

dp[長さ][最後のアルファベット]というDPも考えられる(メモリ節約が必要)。最初これの計算量はかなり厳しいと思ったが、それぞれの単語で1つのアルファベットしか関与しないのだから、まったく問題ない

コメント

後者のdpの、一見次元が増えてその分かかってくるかなーって思えるけれど実際にはそんなことない、というのはまあ自明なんだけどなるほどと思えた。
前者はなんかdp[i]の大小を常に持って、appendと比較の部分をなんかうまくやれば各dp[i]がO(|dict| |単語| log (len+|単語|))くらいで出来る気がなんとなーくするけど本当かな？いつか考えてみたい

コード

#include <string>
#include <vector>
#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 mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
using namespace std;

struct StickedWords {
	string constructLine(vector <string> d, int len) {
		int n = d.size();
		static int wf[26][26], maxlength[26];
		mset(wf, INF);
		rep(i, 26) wf[i][i] = 0;
		rep(i, n) {
			int a = d[i][0] - 'a', b = d[i][d[i].size()-1] - 'a';
			wf[a][b] = min(wf[a][b], - ((int)d[i].size() - 1));
		}
		//負閉路うまくやるのってWFではどうやってやるのがうまいのかわからない
		rep(k, 26) rep(i, 26) rep(j, 26) if(wf[i][k] < INF && wf[k][j] < INF)
			wf[i][j] = min(wf[i][j], wf[i][k] + wf[k][j]);
		rep(k, 26) if(wf[k][k] < 0) {
			rep(i, 26) rep(j, 26) if(wf[i][k] < INF && wf[k][j] < INF)
				wf[i][j] = -INF;
		}
		rep(i, 26) {
			maxlength[i] = 0;
			rep(j, 26) maxlength[i] = max(maxlength[i], - wf[i][j]);
		}
		static string dp[2551];
		rer(i, 1, len+50) {
			dp[i] = "~";
			rep(j, n) {
				if(i + maxlength[d[j][d[j].size()-1]-'a'] < len) continue;
				int prevlen = i - ((int)d[j].size() - 1);
				if(prevlen <= 0) continue;
				if(prevlen != 1 && dp[prevlen][dp[prevlen].size()-1] != d[j][0]) continue;
				string t = prevlen == 1 ? d[j] : dp[prevlen] + d[j].substr(1);
				dp[i] = min(dp[i], t);
			}
		}
		string r = "~";
		rer(i, len, len+50) r = min(r, dp[i]);
		return r == "~" ? "" : r;
	}
};