Codeforces #423 Div1 A. String Reconstruction

こっちはまぁよかったんだけどね。
http://codeforces.com/contest/827/problem/A

問題

未知の文字列Sがある。
ここで、いくつかの文字列と、S中でそれらが部分文字列として登場する位置が与えられる。
これらの情報と合致するSのうち、辞書順最短のものを求めよ。
なお、そのようなSは必ず存在する。

解法

部分文字列に関する情報は必ず正しいので、「今から何文字の間は何番目の部分文字列と一致する」という情報をスライド最小値の要領で管理し、Sの先頭から文字列を埋めていこう。
どの部分文字列でもカバーされず不明な場所は'a'にしておけばよい。

int N;
string S[101010];
char buf[1010101];
int L;
string R;
vector<int> add[2010100];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d",&N);
	FOR(i,N) {
		scanf("%s%d",buf,&x);
		S[i]=buf;
		while(x--) {
			scanf("%d",&y);
			add[y-1].push_back(i);
			L=max(L,y+(int)S[i].size()-1);
		}
	}
	R.resize(L,'a');
	deque<pair<int,int>> Q;
	FOR(i,L) {
		while(Q.size() && Q.front().second<i) Q.pop_front();
		FORR(e,add[i]) {
			int x=i+S[e].size()-1;
			while(Q.size() && Q.back().second<=x) Q.pop_back();
			Q.push_back({e,x});
		}
		
		if(Q.size()) {
			x=Q.front().first;
			y=Q.front().second;
			R[i]=S[x][S[x].size()-1-(y-i)];
		}
		
	}
	cout<<R<<endl;
	
	
}

まとめ

若干面倒なので750ptでもよさそう。