Colorful Cookie

2 secs 1024 MB

east1016

Problem

Submissions

Test cases

Editorial

基本方針

$W$ の制約が小さいので、長方形領域の横の長さを $1$ から $W$ まで全探索することを考えます。

長方形領域の横の長さを $w$ で固定した場合、長方形領域の縦の長さは $\left\lfloor \frac{H}{w} \right\rfloor$ とするのが最適となります。

縦方向の探索には、要素を $1$ 個ずつ伸ばしていく方法や、累積和を使うなどして高速化すれば AC することができます。

実装例(C++)

xxxxxxxxxx
 
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
using namespace std;
​
int main() {
    int h, w, k;
    cin >> h >> w >> k;
    vector<string> s(h);
    rep(i, 0, h) cin >> s[i];
​
    // 長方形領域の横の長さが [wl, wr) の場合の嬉しさの最大値を求める関数f
    auto f = [&](int wl, int wr) {
        int hlen = min(k / (wr - wl), h);
        if (hlen == 0) return 0;
​
        // 各アルファベットについての累積和を求める
        vector<vector<int>> prefix_sum(26, vector<int>(h + 1));
        rep(i, 0, h) {
            rep(j, wl, wr) {
                if (s[i][j] != '.') prefix_sum[s[i][j] - 'a'][i + 1]++;
            }
            rep(j, 0, 26) prefix_sum[j][i + 1] += prefix_sum[j][i];
        }
​
        int ret = 0;
        rep(i, 0, h - hlen + 1) {
            int sum = 0, kind = 0;
            rep(j, 0, 26) {
                if (prefix_sum[j][i + hlen] - prefix_sum[j][i] > 0) {
                    sum += prefix_sum[j][i + hlen] - prefix_sum[j][i];
                    kind++;
                }
            }
            ret = max(ret, sum * kind);
        }
        return ret;
    };
​
    int ans = 0;
    rep(i, 0, w) rep(j, i + 1, w + 1) ans = max(ans, f(i, j));
    cout << ans << endl;
}
​

余談

初期の案では制約が $1 \leq H,W \leq 2000$ でしたが、自分の力では解けませんでした。