Codeforces Round #576 Div.1 D: Rectangle Painting 1

本番は嘘解法で通してしまったのでちゃんと書きます。

問題概要

原文 → Problem - D - Codeforces

のグリッド状のマスが与えられ、それぞれは白または黒に塗られている。

このマスの任意の 長方形領域に対して、その領域内にあるマスを全て白にするという操作を何度でもすることができる。この操作のコストは である。

全てのマスを白くするために必要なコストの合計の最小値を求めよ。

解説

まず、操作を行う長方形領域が重ならないし、接しもしないことが重要である。そうなることを簡単に証明する。

ふたつの長方形領域があって、その大きさがそれぞれ であり、これらが重なっているまたは接しているものとする。この長方形領域をどちらも含むような長方形領域であって幅と高さそれぞれ最小のものをとり、そのサイズを とおくと、重なっているまたは接しているという仮定から および が成り立つ。

の長方形を取ることで損をしないことを示す (これが示せれば重なるケースや接するケースを考慮しなくて良い)。 について をどこでとるかで場合分けして考える。

• のとき
  • 上の不等式から明らかに成立
• のとき
  • 上の不等式から明らかに成立
• のとき
  • 別々に取ると だけコストがかかるが、 より であることがわかり、 より であることもわかるので、 の長方形を取って損しないことが分かる
• のとき
  • 上と同様の理由で成立

よって長方形領域が重なる・接することはない。

あとはどのようにして解くかだが、ある長方形領域に着目したときの最適な値をメモ化再帰で求めればよい。ある行または列に対して、はじめから全て白であればそこで長方形領域が分かれるとみなしてよく、より小さい問題にして解くことができる。

ソースコード

int dp[51][51][51][51];
int sum[51][51];

int get_sum(int lx, int ly, int rx, int ry) {
    return sum[rx][ry] + sum[lx][ly] - sum[lx][ry] - sum[rx][ly];
}

int solve(int lx, int ly, int rx, int ry) {
    if(dp[lx][ly][rx][ry] >= 0) return dp[lx][ly][rx][ry];
    int bx = (rx - lx), by = (ry - ly);
    if(bx == 0 or by == 0) return 0;
    
    int res = max(bx, by);
    for(int i=lx; i<rx; i++) {
        if(get_sum(i, ly, i+1, ry) == 0) {
            res = min(res, solve(lx, ly, i, ry) + solve(i+1, ly, rx, ry));
        }
    }
    for(int i=ly; i<ry; i++) {
        if(get_sum(lx, i, rx, i+1) == 0) {
            res = min(res, solve(lx, ly, rx, i) + solve(lx, i+1, rx, ry));
        }
    }
    return dp[lx][ly][rx][ry] = res;
}

int main() {
    int N; scanf("%d", &N);
    for(int i=1; i<=N; i++) {
        for(int j=1; j<=N; j++) {
            char c; scanf(" %c", &c);
            if(c == '#') sum[i][j]++;
        }
    }

    for(int i=0; i<=N; i++) {
        for(int j=1; j<=N; j++) {
            sum[i][j] += sum[i][j-1];
        }
    }
    for(int j=0; j<=N; j++) {
        for(int i=1; i<=N; i++) {
            sum[i][j] += sum[i-1][j];
        }
    }

    fill(dp[0][0][0], dp[N+1][0][0], -1);
    cout << solve(0, 0, N, N) << endl;
    return 0;
}

Educational Codeforces Round 69 D: Yet Another Subarray Problem

問題概要

原文 → Problem - D - Codeforces

長さ の整数列 と、パラメータ が与えられる。

数列内の連続する閉区間 について、そのコストは で表される。なお、空の区間に対するコストは である。

あり得る全ての区間を考慮した時のコストの最大値を求めよ。

解法

で割った切り上げ、というパートが存在しなければよくある問題で、最適な左端のみを覚えながら右端を ずつ伸ばしていけば良い (累積和を取って変形すると、左端に関しては累積和の が必要になる)。

しかし今回は切り上げがあるので少し工夫が必要。

インデックスを で考え、合同となるインデックスはまとめて管理しよう。 番目までインデックスを伸ばすときは における最適値が変わる可能性があり、直前の値を持ってくるか、それまで最適だったものをそのまま使うかの 通りを考慮する必要がある。

ソースコード

int main() {
    ll N, M, K; scanf("%lld%lld%lld", &N, &M, &K);
    vector<ll> A(N);
    for(int i=0; i<N; i++) scanf("%lld", &A[i]);
    vector<ll> S(N+1);
    for(int i=0; i<N; i++) S[i+1] = S[i] + A[i];

    ll ans = 0;
    vector<ll> opt(M, INF);
    for(int i=1; i<=N; i++) {
        opt[(i-1)%M] = min(opt[(i-1)%M] + K, S[i-1] + K);
        for(int k=0; k<M; k++) chmax(ans, S[i] - opt[k]);
    }
    printf("%lld\n", ans);
    return 0;
}

本番では が大きい場合しか解けなかった (右端を まで伸ばしたときに について何倍するか変化するのは高々 個なので、変化するところだけ愚直に更新していっても が 以上だと全体でも なので使えるはず)

小さいときにどうするかは全く思い浮かばなかったのでかなしい

Educational Codeforces Round 18 E: Colored Balls

問題概要

原文 → Problem - E - Codeforces

色のボールがあり、 番目の色で塗られたボールは 個ある。

これらのボールを以下の条件を全て満たすように箱に入れる。

• それぞれの箱について、箱の中にあるボールの色は 種類のみ
• 空箱が存在しない
• 箱に入っているボールの個数の最大値と最小値の差は高々

必要な箱の個数の最小値を求めよ。

解説

色目のボールを箱に入れることを考える。積を考えると、「箱の個数」または「箱に入れるボールの個数」のいずれかは 以下であることが分かる。なのでそれぞれについて問題を解けばよい。

箱の個数が定まっているときに、それぞれの箱に入れるボールの個数がどうなるべきかは割り算をするとわかる。(剰余が のときに注意)

あとは「箱に入れるボールの個数が 個または であるときに、条件を満たす入れ方が可能か？また可能な時の箱の数の最小値がいくらか？」を解ければ良いことになる。

実は、各 について最適な箱の数は であり、入れ方が可能かどうかの判定は を満たすかどうかで可能である。

上の条件を満たすと仮定すると が成立するが、これは「全ての箱に 個入れたと仮定した時の個数」と「全ての箱に 個入れたと仮定した時の個数」で を挟んでいることに相当している。

ソースコード

int main() {
    int N; scanf("%d", &N);
    vector<int> A(N);
    for(int i=0; i<N; i++) scanf("%d", &A[i]);

    ll ans = INF;
    {
        // 箱の個数について
        for(int x=1; x*x<=A[0]; x++) {
            int d = A[0] / x, m = A[0] % x;
            for(int k=d; k>=d-(m==0); k--) {
                int mi = k, ma = k+1;
                ll sum = 0;
                for(int i=0; i<N; i++) {
                    ll b = (A[i] + ma - 1) / ma;
                    if(mi * b <= A[i]) sum += b;
                    else sum = INF;
                }
                ans = min(ans, sum);
            }
        }
    }

    {
        // 箱に入れるボールの個数について (x か x+1)
        for(int x=1; x*x<=A[0]; x++) {
            int mi = x, ma = x+1;
            ll sum = 0;
            for(int i=0; i<N; i++) {
                ll b = (A[i] + ma - 1) / ma;
                if(mi * b <= A[i]) sum += b;
                else sum = INF;
            }
            ans = min(ans, sum);
        }
    }
    cout << ans << endl;
    return 0;
}

で分けて何かするのは思い浮かんでいたけど、判定の式がわからなかった。