Codeforces Round #527 Div.3 C: Prefixes and Suffixes

問題概要

原文 → Problem - C - Codeforces

文字の文字列 があり、あなたは が全体としてどのような文字列であるかは知らない。しかし、長さが から までの全ての prefix と suffix についての情報は持っている (ただし、どれが prefix でどれが suffix かはわからない)

与えられるそれぞれの文字列について、その文字列が prefix であるか suffix であるかに分類せよ。そのような割当が複数あるならばどれか 1 つを答えればよい。

解説

長さ の文字列の情報がふたつあり、これを とします。これらの情報から 全体が何であるかはある程度推測できます。具体的には、 (prefix, suffix) の場合と、 (prefix, suffix) の 2 パターンです。

全体の文字列が推測できたので、あとは条件に合うような割当ができれば良いです。これは check(s, k, assim) のようなメソッドを作ることで実現できます。文字列全体が と推測されているときに、次に処理すべきものが長さ の prefix 及び suffix であり、その時の割当が assim である、という意味です。 一見 TLE しそうなのですが、条件を満たさないときに探索をしないなど枝刈りをすると高速に動くようです。落ちるケースあったら教えてください。

また、multiset などでどの文字列がいくつあるかを数えながら割当を行う方法もあるようです。Writer による解説はその方針でやっています。

ソースコード

int N;
string par[210], NIL = "Z";

string check(string s, int k, string assim) {
    if(k == 0) return assim;
    
    int idxX = -1, idxY = -1;
    for(int i=0; i<2*N-2; i++) {
        if(par[i].length() != k) continue;
        if(idxX < 0) idxX = i;
        else         idxY = i;
    }

    if(s.substr(0, k) == par[idxX] and s.substr(N-k) == par[idxY]) {
        assim[idxX] = 'P'; assim[idxY] = 'S';
        string res = check(s, k-1, assim);
        if(res != NIL) return res;
        assim[idxX] = assim[idxY] = 'X';
    }
    if(s.substr(0, k) == par[idxY] and s.substr(N-k) == par[idxX]) {
        assim[idxY] = 'P'; assim[idxX] = 'S';
        string res = check(s, k-1, assim);
        if(res != NIL) return res;
        assim[idxX] = assim[idxY] = 'X';
    }
    return NIL;
}

signed main() {
    cin >> N;

    string X = "", Y = "";
    int idxX = -1, idxY = -1;
    for(int i=0; i<2*N-2; i++) {
        cin >> par[i];
        if(par[i].length() == N-1) {
            if(X == "") X = par[i], idxX = i;
            else        Y = par[i], idxY = i;
        }
    }
    
    if(Y.substr(1, N-2) == X.substr(0, N-2)) {
        string cand = Y[0] + X;
        string assim(2*N-2, 'X');
        assim[idxY] = 'P', assim[idxX] = 'S';

        string res = check(cand, N-2, assim);
        if(res != NIL) {
            cout << res << endl;
            return 0;
        }
    }
    if(X.substr(1, N-2) == Y.substr(0, N-2)) {
        string cand = X[0] + Y;
        string assim(2*N-2, 'X');
        assim[idxX] = 'P', assim[idxY] = 'S';

        string res = check(cand, N-2, assim);
        if(res != NIL) {
            cout << res << endl;
            return 0;
        }
    }
    return 0;
}