CodeChef July Challenge: Parity Again

個人的に面白かったので書きます。

問題概要

原文 → Contest Page | CodeChef

整数集合 (multiset ではない set) があり、はじめは空集合である。この集合に対して以下で示すクエリを 回処理する。

• 整数 が与えられるので以下を処理
  • に を insert する
  • の元 全てに対して、 を に insert する ( は xor)
• 上の処理を行った後に、整数を 2 進数として見たときの popcount が偶数である要素の個数と、奇数である要素の個数をそれぞれスペース区切りで出力

制約

• 

解説

一見愚直では間に合わなさそうに見えるが、「 に が含まれていた場合は何もせず、含まれていない場合のみ真面目に操作」するだけで間に合う。以下にその理由を示す。

まず、問題文中の操作より以下が成り立つ。

• ある整数 についてどちらも に含まれている場合、 も に含まれている

これを踏まえると、実は以下も成り立つ。

• ある整数 が に含まれておらず、 が に含まれている場合、 は に含まれていない

背理法でこれを示す。 が に含まれていたとしよう。 も も含まれていることと、上の条件より、 が に含まれる。しかし、これは仮定に矛盾するので、 かつ であるならば である。

これを踏まえると、 が に含まれていない場合は にすでに存在する要素と xor を取ることで常に新たな要素を作ることになるし、 が含まれている場合は にすでに存在する要素と xor を取っても新たな要素が何も生まれないということになる。つまり、冒頭で示したような工夫をすることで全ての要素について高々 1 回しか生成しないようにできるため、十分高速に動作する。

ソースコード

int main() {
    int T; scanf("%d", &T);
    while(T--) {
        set<int> even, odd;
        even.emplace(0);
        int Q; scanf("%d", &Q);
        while(Q--) {
            int X; scanf("%d", &X);
            set<int> &p = (__builtin_parity(X) ? odd : even);
            if(!p.count(X)) {
                vector<int> n_even, n_odd;
                for(auto e : even) {
                    int V = e ^ X;
                    if(__builtin_parity(V)) n_odd.emplace_back(V);
                    else n_even.emplace_back(V);
                }
                for(auto e : odd) {
                    int V = e ^ X;
                    if(__builtin_parity(V)) n_odd.emplace_back(V);
                    else n_even.emplace_back(V);
                }
                for(auto e : n_even) even.emplace(e);
                for(auto e : n_odd) odd.emplace(e);
            }
            printf("%zu %zu\n", even.size() - 1, odd.size());
        }
    }
}

これ頭で考えてて解けなかったんですが、解説みてなるほどなぁってなりました。

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;
}

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

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