Matrix Palindromes [CSAcademy #55]

https://csacademy.com/contest/round-55/task/matrix-palindromes/

縦N,横Mのアルファベット小文字から成る行列がある。
最低何セル変更することで、以下の条件を満たすような行列が作れるか。

• 全ての行が回文
• 少なくともK個の列が回文

N,M≦10^5

解法

説明のため、N=H,M=W,行列B[y][x]として説明する。
あと、下のコードはかなり冗長そうなので余り参考にならないかもしれない。
　
「少なくともK個の列が回分になるようにする」 -> 「全ての行が回文になるようにする」という順で構築する。
　
x行目が回文となるためには、W-1-x行目も同様の回文になる必要がある。
よって、x行目を回文にするのに、y=[0,ceil(H/2)]について
「B[y][x], B[y][W - 1 - x], B[H - 1 - y][x], B[H - 1 - y][W - 1 - x]のうち、最も出現頻度が高い文字に合わせるためのコスト」を計算して総和をとると必要コストが得られる。
この時、その後に全ての行を回文にするコストを考えると、元々回文が含まれている行はあまりいじらない方が得策であると分かる。
そのため、もし、その行を変更することで、「全ての行が回文になるようにする」時のコストが減らせるなら、その分、コストを減らす。
よって、x行目を回文にするのに必要なコストは「出現頻度が高い文字に合わせる為のコスト - その列だけ全ての行を回文にする時に必要なコスト」となる。
コスト順に昇順ソートして、必要コストが最小となる列を選択して回分化する。
　
あとは、適当に全ての行が回文となるように変更してやるだけ。

typedef long long ll;
int H, W, K;
string B[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W >> K;
    rep(y, 0, H) cin >> B[y];

    vector<pair<pair<ll,ll>, int>> v;
    rep(x, 0, W / 2) {
        ll sm = 0, sm2 = 0;
        rep(y, 0, H / 2) {
            map<char, int> c;
            c[B[y][x]]++;
            c[B[H - 1 - y][x]]++;
            c[B[y][W - 1 - x]]++;
            c[B[H - 1 - y][W - 1 - x]]++;
            int ma = 0;
            fore(p, c) ma = max(ma, p.second);
            sm += 4 - ma;

            if (B[y][x] != B[y][W - 1 - x]) sm2++;
            if (B[H - 1 - y][x] != B[H - 1 - y][W - 1 - x]) sm2++;
        }

        if (H % 2) if (B[H / 2][x] != B[H / 2][W - 1 - x]) sm++;
        v.push_back({ {sm-sm2, sm}, x });
    }

    if (K % 2 and W % 2) {
        ll sm = 0;
        rep(y, 0, H / 2) {
            map<char, int> c;
            c[B[y][W / 2]]++;
            c[B[H - 1 - y][W / 2]]++;
            int ma = 0;
            fore(p, c) ma = max(ma, p.second);
            sm += 2 - ma;
        }
        v.push_back({ {sm, sm}, W / 2 });
    }

    sort(v.begin(), v.end());

    ll ans = 0;
    rep(i, 0, (K + 1) / 2) {
        auto p = v[i];

        ans += p.first.second;
        int x = p.second;

        rep(y, 0, H) B[y][x] = B[y][W - 1 - x] = '!';
    }

    rep(y, 0, H) {
        rep(x, 0, W / 2) if (B[y][x] != B[y][W - 1 - x]) ans++;
    }

    cout << ans << endl;
}