パナソニックプログラミングコンテスト E - Three Substrings

問題: https://atcoder.jp/contests/abc156/tasks/abc158_f

問題概要

次の同じ方法で得られた長さ $2000$ 文字以内の文字列 $ a, b, c$ が与えられる。元の文字列 $s$ の長さとしてありえる最小値を求めよ。

文字列 $s$ の空でない部分文字列を選ぶ。そのうちいくつかの文字を '?' に置き換える (0個，全部も可) 。

解法概要

与えられる文字列の長さは高々 2000 (これを $n_\mathit{max}$ とおく) 文字なので，1つの文字列 (たとえば $a$) の長さを固定してしまい，残りの2つについては固定した文字列から見た相対位置を $[-4000, 4000]$ の範囲で試すことができる ($[-2000, 2000]$ では足りていないことに注意)。

ただし，ある文字列 $a_1$ を他の文字列 $a_0$ に対して相対位置 $i$ で配置できるか？の判定は時間計算量 $\mathcal{O}(min(|a_0|, |a_1|))$ なので，何にも考えずに実装しようとすると $\mathcal{O}(n_\mathit{max}^3)$ とかになってしまう。しかしこれは「ある文字列 $a_1$ を他の文字列 $a_0$ に対して相対位置 $i$ で配置できるか？の判定」の結果を前計算しておくことで回避できる。

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

constexpr int INF = 1 << 30;
constexpr int BASE = 4000;

inline bool match(char c1, char c2) {
    return (c1 == c2 || c1 == '?' || c2 == '?');
}

// t を s から見て相対位置 i-BASE に置くことができるか
inline bool can_place(string &s, string &t, int ns, int nt, int i) {
    for(int j=0;j<nt;++j) {
        if(i+j-BASE < 0 || ns <= i+j-BASE) continue;
        if(!match(s[i+j-BASE], t[j])) return false;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    string a[3];
    cin >> a[0] >> a[1] >> a[2];
    int n[3] = {int(a[0].length()), int(a[1].length()), int(a[2].length())};

    // a (位置: BASE) に対する c の位置を i にしてよいか
    vector<bool> ac(2*BASE+1, true);
    for(int i=0;i<=2*BASE;++i) {
        ac[i] = can_place(a[0], a[2], n[0], n[2], i);
    }

    // b (位置: BASE) に対する c の位置を i にしてよいか
    vector<bool> bc(2*BASE+1, true);
    for(int i=0;i<=2*BASE;++i) {
        bc[i] = can_place(a[1], a[2], n[1], n[2], i);
    }

    int ans = INF;
    // a の位置は BASE に固定
    for(int bi=0;bi<=2*BASE;++bi) { // b の位置
        if(!can_place(a[0], a[1], n[0], n[1], bi)) continue;
        for(int ci=0;ci<=2*BASE;++ci) { // c の位置
            if(0 <= BASE+(ci-bi) && BASE+(ci-bi) <= 2*BASE && !bc[BASE+(ci-bi)]) continue;
            if(!ac[ci]) continue;
            ans = min(ans, max({BASE+n[0], bi+n[1], ci+n[2]}) - min({BASE, bi, ci}));
        }
    }

    cout << ans << endl;
}

所感

3つの要素があるときはそのうち1つの位置なり値なりを固定してしまうとうまくいくパターンが多い気がする。

それから，今回はwriter さんの思想がバチバチに表れたコンテストだったと思います (最近界隈に影響されて「バチバチに」という副詞をつい使ってしまいます) 。