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

hamayanhamayan's blog

ukuku 2 [yukicoder No.765]

https://yukicoder.me/problems/no/765

考察過程

1. どこから手を付けていいか分からないので、とりあえず全探索対象を探す
2. 削除文字を全探索すると、難しそうなので、だめそう
3. 回分なので、中心も全探索できそう
4. すると若干貪欲にやると、最大回文にしたときの端を削除することで回分を伸ばすことができる
5. 最大回分を求めるのも、回文を伸ばす最大もロリハでいける
6. これで解けそう

解説

https://yukicoder.me/submissions/307971

まずロリハを使って、左側の文字列と右側の文字列が同じ文字列となる最大文字数を求める関数を作っておく。
左側の文字列とは、右端をlとして伸ばしたときの文字列。
右側の文字列とは、左端をrとして伸ばしたときの文字列。

    int getMaxSame(int l, int r) {
        int lsz = l + 1;
        int rsz = N - r;

        int ok = 0, ng = min(lsz, rsz) + 1;
        while (ok + 1 != ng) {
            int md = (ok + ng) / 2;
            if (rs.hash(r, r + md - 1) == rsr.hash(N - 1 - l, N - 1 - l + md - 1)) ok = md;
            else ng = md;
        }
        return ok;
    }

rsは文字列Sでそのままロリハを作ったもの。rsrは文字列Sを反転させた文字列についてロリハを作ったものになる。
左側の文字列で伸ばせる最大数をlsz, 右側の文字列で伸ばせる最大数をrszとする。
すると、0~min(lsz, rsz)だけ文字列があるが、同じ文字列になるかは単調性を持つので、二分探索できる。
ロリハで同じ文字列か判定しながら、二分探索しよう。
 
この関数ができれば、あとは、全探索を進めるだけ。
回分として、偶数奇数を分けて最大を探す。
どちらも、処理はそんなに変わらないので、奇数回分のみ説明する。
中心をcとして、ma=getMaxSame(c,c)を計算する。
すると、maはcを中心とする最長の回分の半径になるので、ma*2-1の長さの回分があることが分かる。
もし、「c - ma < 0 and N <= c + ma」であれば、文全体がこの回文になっているので、端を1つ消すと、回文が両端1つ分減るので、N-2が答え。
もし、そうでなく、「c - ma < 0 or N <= c + ma」であれば、片方の端が文全体の端になっているので、端でない方を消すことでその回文を維持できるので、ma*2-1が答え。
もし、そのどちらでも無いなら、回文を伸ばす余地があるので、左側を消した場合、右側を消した場合で、回文を伸ばす。
どちらも、消した方を飛ばして、端の文字からgetMaxSameをする。
ここで得られた文字*2分の回分が伸びるので、ma*2-1+(ここで得られた文字)*2が答え。
 
注意点として、偶数長の回分を作るときに、中心を消すことで作る場合を別途処理する必要がある。(サンプル1)
ここまでの説明がわかっていれば、この場合を処理するのは難しくないだろう。

string S; int N;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S;
    N = S.length();

    StringMaster sm(S);
    int ans = 0;

    // 奇数回分
    rep(c, 0, N) {
        int ma = sm.getMaxSame(c, c);
        if (c - ma < 0 and N <= c + ma) chmax(ans, N - 2);
        else if (c - ma < 0 or N <= c + ma) chmax(ans, ma * 2 - 1);
        else {
            // 左を消す
            if(0 <= c - ma - 1) chmax(ans, ma * 2 - 1 + sm.getMaxSame(c - ma - 1, c + ma)*2);
            // 右を消す
            if (c + ma + 1 < N) chmax(ans, ma * 2 - 1 + sm.getMaxSame(c - ma, c + ma + 1) * 2);
        }
    }

    // 偶数回分
    rep(c, 0, N - 1) {
        int ma = sm.getMaxSame(c, c + 1);
        if (c - ma < 0 and N <= c + 1 + ma) chmax(ans, N - 2);
        else if (c - ma < 0 or N <= c + 1 + ma) chmax(ans, ma * 2);
        else {
            // 左を消す
            if (0 <= c - ma - 1) chmax(ans, ma * 2 + sm.getMaxSame(c - ma - 1, c + 1 + ma) * 2);
            // 右を消す
            if (c + 1 + ma + 1 < N) chmax(ans, ma * 2 + sm.getMaxSame(c - ma, c + 1 + ma + 1) * 2);
        }
    }

    // 真ん中を消すパターン
    rep(c, 0, N - 2) chmax(ans, sm.getMaxSame(c, c + 2) * 2);

    cout <