ICPC2017 Asia Regional Tsukuba J String Puzzle

問題

長さnの文字列がありその一部の情報が以下のどれかの形式で与えられる。

• x文字目がcである
• l文字目からr文字目がh文字目からと等しい

このときq個のクエリ、x文字目が何の文字であるか、あるいは与えられた情報からではわからないかを答えよ。

制約条件

n≦10^9
アルファベットは英小文字
情報とクエリは1000以下ずつ
それぞれの文字iについて、i文字目とj文字目が等しい（j < j）であるような関係は高々一つしか与えられない。

解法

最後の制約が超強烈でこれを見落としていたので解けなかった。これがあると簡単。
ある位置と等しいような位置のうち最も左にあるものを求めることを考える。

制約から、左に動くような動き方は高々一通りだけ。
移動後同じ情報でまた左に動ける場合がある。たとえば[0, 100]と[3, 103]が等しいといった情報が与えられたとき。
このときは同じ幅ずつ左に動けるだけ動く感じになるので、位置を動かせるだけ一度に動かす。すると情報の数の移動回数で一番左に来られる。

一番左の位置がわかるなら、文字の情報とクエリを全部左に持ってくれば答えはすぐに求まる。

ソースコード

int n, a, b, q;

int main(){
	cin >> n >> a >> b >> q;
	vector<pair<int, char>> xs;
	rep(i, a){ int x; char c; cin >> x >> c; xs.emplace_back(--x, c); }
	
	vector<pi> ys;
	rep(i, b){ int y, h; cin >> y >> h; ys.emplace_back(--y, --h); }
	if(ys.size() && ys.back().second >= 0) ys.emplace_back(n, -1);
	
	map<pi, int> left; //区間とそこに含まれるときの左への移動距離
	rep(i, ys.size()){
		if(ys[i].second < 0) continue;
		int L = ys[i].first, R = ys[i + 1].first;
		int l = ys[i].second, r = l + R - L, d = L - l;
		left[pi(L, R)] = d;
	}
	
	auto move = [&](int p){ //一つの情報を使って左に動かす
		map<pi,int>::iterator it = left.lower_bound(pi(p + 1, 0));
		if(it == left.begin()) return p;
		--it;
		
		if(!(it->first.first <= p && p < it->first.second)) return p;
		int l = it->first.first - it->second, t = (p - l) / it->second;
		return p - t * it->second;
	};
	
	unordered_map<int, char> cs;
	for(auto i : xs){
		int p = i.first;
		for(int nxt = p; p != (nxt = move(p)); p = nxt);
		cs[p] = i.second;
	}
	string ans;
	while(q--){
		int p; cin >> p;
		for(int nxt = --p; p != (nxt = move(p)); p = nxt);
		ans += cs.count(p) ? cs[p] : '?';
	}
	cout << ans << endl;
	return 0;
}