はまやんはまやんはまやん

hamayanhamayan's blog

Palindromic Friendship [CSAcademy #58 C]

https://csacademy.com/contest/round-58/task/palindromic-friendship/statement/

1からNまで順番になっている配列がある。
M組の友達関係があり、A[i]とB[i]が友達である。
配列の連続部分列の中で友達回文であるものの長さの最大値を答えよ。
友達回文とは、長さがKだとすると、1番目とK番目、2番目と(K-1)番目、…がそれぞれ友達関係にある列の事。

解法

回文判定のよくあるやり方として、区間DPがある。
DP[l][r] := 部分列[l,r]が回文かどうか
これを更新していく事を考えるとO(N^2)でダメ。
 
今回の友達回文ではDP[l][r]=trueとなる為には最小限配列のl番目とr番目が友達関係である必要がある。
その為、DP[l][r]を探索してくなかで、配列のl番目とr番目が友達関係であるものだけ探索すればよいということが分かる。
この気付きが今回は大切。

DP[l][r]がtrueかどうかを判定するにはDP[l+1][r-1]がtrueかどうかの判定が必要なので、DP[l][r]を探索するのだが、r-lが小さい順から探索していく必要がある。
その為、「v[len] := abs(B[i]-A[i])がlenである友達関係の添字の集合」を用意しておき、小さい方から探索する。
あとは、DP[l+1][r-1]を高速に取ってこれるようにl+1番目とr-1番目が友達関係である添字をmappingで管理しながら更新していけば答え。

int N, M, A[201010], B[201010];
map<pair<int, int>, int> mapping;
int dp[201010];
vector<int> v[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, M) {
        cin >> A[i] >> B[i];
        if (A[i] > B[i]) swap(A[i], B[i]);
        mapping[{A[i], B[i]}] = i + 1;
        v[B[i] - A[i]].push_back(i);
    }

    int ans = 0;
    rep(len, 0, N) fore(i, v[len]){
        if (len <= 2) dp[i] = 1, ans = max(ans, len);
        else {
            int a = A[i] + 1, b = B[i] - 1;
            int j = mapping[{a, b}];
            if (j and dp[j - 1]) {
                dp[i] = 1, ans = max(ans, len);
            }
        }
    }
    cout << ans + 1 << endl;
}