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

hamayanhamayan's blog

Palindromic Love Letter [東京工業大学プログラミングコンテスト2019 G]

https://atcoder.jp/contests/ttpc2019/tasks/ttpc2019_g

解説

https://atcoder.jp/contests/ttpc2019/submissions/7237908

操作は逆に行うこともできるので、問題の言い換えができる。
「操作をちょうどK回行うことで、文字列Tを何種類の回分にできるか」
という問題になる。
今回は操作の組み合わせではなく、結果の組み合わせだけを考えている。
そのため、ちょうどK回と指定があるが、K回以下の回数と考えても問題ない。
同じ所を編集すれば、回数を無駄に増やせるからである。
「操作をK回以下行うことで、文字列Tを何種類の回分にできるか」
これで何が良くなるかというと、あるゴールの回分を考えた時に、最短手順で構築して
手数がK回以下であるかを判定すればいいためである。

さて、まずはDPかなという感じもする。
回分を構築していくので、前半部分を構築すれば後半も構築できるので、N/2で考えていく。
奇数のときは、真ん中も考慮する必要がある。
dp[i][k] := i番目まで確定していてk回操作済みのときの組み合わせ
これはO(NK)でできる。
だが、Kが109なので、高速化は難しそう。
DPではないのか?
よくよく考えると、回分で対応している部分は他の部分とは独立している。
なので、DPで順番に決めていく必要はなさそうだ。

ここまでは経験から順当に行くかもしれないが、これ以降が難しい。
回分で対応するグループは3通りに分けられる。
same: s[i]=S[N-i]になってる
miss: s[i]!=S[N-1]になってる
center: Nが奇数の場合で中心になってる
sameをそのままの文字にするときは操作0回、違う文字にするなら操作2回必要。
missをそのままの文字にするときは操作1回、違う文字にするなら操作2回必要。
centerそのままの文字にするときは操作0回、違う文字にするなら操作1回必要。
これでだいぶ抽象化された。
sameとmissの文字を変える回数で全探索すれば、重複なく全通り数えられるのでは?
sameで違う文字にする組がcnt_same個、missで違う文字にする組がcnt_miss個とすると、
cnt_same2+cnt_miss2+(miss-cnt_miss)≦Kを満たせばいい。
この組み合わせ計算は、以下を事前計算しておく。
sameで違う文字にcnt_same組する場合の組み合わせ cmb_same(cnt_same) = C(same, cnt_same) * 25cnt_same
missで違う文字にcnt_miss組する場合の組み合わせ cmb_miss(cnt_miss) = C(miss, cnt_miss) * 24cnt_miss * 2miss-cnt_miss
すると、組み合わせはcmb_same(cnt_same)cmb_miss(cnt_miss)となる。
これで、O(N2)まで来た。
あとは、cnt_missで全探索する時に、使えるcnt_sameの範囲が[0,R]であるなら、
cmb_same(cnt_same)
cmb_miss(0) + cmb_same(cnt_same)cmb_miss(1) + ... + cmb_same(cnt_same)cmb_miss(R)
= cmb_same(cnt_same) * (cmb_miss(0) + cmb_miss(1) + ... + cmb_miss(R))
となるため、累積和で高速化可能。
これでO(N)で間に合う(自分は横着してO(NlogN))
centerは2通りしかないので、こちらも全探索すればいい。

K=1のときは元々回分なのに壊すしかないというパターンが考えられるので場合分けして答えよう。

int N, K;
string S;
Comb<mint, 201010> com;
mint cmb_miss[101010], cmb_same[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K >> S;

    int miss = 0, same = 0, center = N % 2;
    rep(i, 0, N / 2) {
        if(S[i] == S[N - 1 - i])
            same++;
        else
            miss++;
    }

    if(K == 1) {
        int ans = 0;
        if (0 < center and miss == 0)
            ans = 25;
        else if (miss == 1)
            ans = 2;
        cout << ans << endl;
        return;
    }

    rep(cnt_same, 0, same + 1) cmb_same[cnt_same] = com.aCb(same, cnt_same) * (mint(25) ^ cnt_same);
    rep(cnt_same, 1, same + 1) cmb_same[cnt_same] += cmb_same[cnt_same - 1];

    rep(cnt_miss, 0, miss + 1) cmb_miss[cnt_miss] = com.aCb(miss, cnt_miss) * (mint(24) ^ cnt_miss) * (mint(2) ^ (miss - cnt_miss));
    
    mint ans = 0;
    rep(cnt_miss, 0, miss + 1) rep(cnt_center, 0, center + 1)
    {
        int ok = -1, ng = same + 1;
        while(ok + 1 != ng) {
            int cnt_same = (ok + ng) / 2;
            if (cnt_same * 2 + cnt_miss * 2 + (miss - cnt_miss) + cnt_center <= K)
                ok = cnt_same;
            else
                ng = cnt_same;
        }

        if(0 <= ok) {
            mint co = cmb_same[ok] * cmb_miss[cnt_miss];
            if(0 < cnt_center)
                co *= 25;
            ans += co;
        }
    }
    cout << ans << endl;
}