AOJ 1387 - String Puzzle

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1387

解法

各分割区間と一致する場所が、「より左にある」という制約が重要で、これにちゃんと気がつけば解ける。
これによって

　文字列のある位置の文字と別の位置の文字が、与えられた条件によって等しい
　⇔ それぞれの位置について、条件をたどって等しいことが言える位置集合のなかで、最も左の位置が等しい

が成り立つ。
したがって、最初に与えられた文字を最も左端に寄せた時にどこに対応するかを計算すれば、各クエリに対して答えるのは簡単（そのクエリの位置を左端に寄せていって、対応する位置の文字を読むだけ）。

左端への寄せ方だが、雑にやると TLE する。
ある区間に一致する区間が、その区間とかなり overlap していると、対応する位置に細かく移していくと O(n) になるからである。
これの解決は簡単で、overlap の場合は一気に飛ばすようにすれば良いだけである。
愚直に一回のステップで左に動く大きさが \(y[i] - h[i]\) なので、これが今見ている区間を追い越すギリギリを求めれば良い。
すなわち、今の位置を \(p\) として、\(p\) が乗っている区間を \(i\) とすれば $$p = p - \left(\left\lfloor\frac{p - y[i]}{y[i] - h[i]}\right\rfloor + 1\right) \times (y[i] - h[i])$$ と更新すると良い。

これで O((a + q)b) で解ける。

ソースコード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, a, b, q; cin >> n >> a >> b >> q;
    vector<int> x(a);
    vector<char> c(a);
    for(int i = 0; i < a; ++i) {
        cin >> x[i] >> c[i];
    }
    vector<int> y(b), h(b);
    for(int i = 0; i < b; ++i) {
        cin >> y[i] >> h[i];
    }

    auto find_left_most_pos = [&] (int p) {
        while(true) {
            const int i = upper_bound(begin(y), end(y), p) - begin(y) - 1;
            if(i < 0 || h[i] == 0) break;
            p -= ((p - y[i]) / (y[i] - h[i]) + 1) * (y[i] - h[i]);
        }
        return p;
    };
    map<int, char> ans;
    for(int i = 0; i < a; ++i) {
        ans[find_left_most_pos(x[i])] = c[i];
    }

    while(q--) {
        int z; cin >> z;
        z = find_left_most_pos(z);
        cout << (ans.count(z) ? ans[z] : '?');
    }
    cout << endl;
}

感想

こんなに簡単なのに本番だと解かれないんだから本当に怖い。
参加してたときも Standings みてかなりビビって手を付けなかった気がする。