hogecoder

tsutaj 競技プログラミングの記録

LeetCode Biweekly Contest 6: String Transforms Into Another String

問題概要

原文 → Loading...

文字列  s1 s2 が与えられる。

以下の操作を 0 回以上行うことによって、 s1 s2 と一致させることができるか判定せよ。

  • アルファベットをふたつ選び、それを  x, y とする。 s1 に含まれる全ての  x を同時に  y へ変更する。

解説

操作をグラフとしてみることを考える。より具体的には、「 x y に変更する」という操作を、 x から  y への有向辺としてとらえる。

まず、それぞれの頂点に対して、出る辺が 2 つ以上存在するときは不可能である。同じアルファベットを異なる複数のアルファベットに変更することができないからである。

不可能なパターンはもう 1 つあり、それは「すべての頂点がなんらかの閉路に含まれている」ときである。

そもそもこの有向グラフは操作すべき順番を与えてくれるものであって (x → y → z というグラフがあるなら、y を z に変えた後に x を y に変えなければならない)、閉路に含まれる頂点でないならこのルールに従えば条件通りに操作可能であるが、閉路に含まれる場合は依存関係が循環しているのでもう少し工夫がいる。どの閉路にも含まれない頂点が存在するとき、そのいずれかは入次数が 0 (つまり操作後に空き状態になる) であるから、それをうまく使えば閉路を壊すことができる。ただしそのような頂点がない場合は閉路が壊せないので、条件を満たすことができなくなる。

実装によっては  s1 s2 がはじめから一致している場合がコーナーになりうるので注意。

class Solution {
public:
    bool canConvert(string str1, string str2) {
        const int N = 26;
        int L = str1.size();
        if(str1 == str2) return true;
        
        vector<int> indeg(N), outdeg(N);
        int edge[N][N] = {};
        vector< vector<int> > G(N);
        for(int i=0; i<L; i++) {
            int u = str1[i] - 'a';
            int v = str2[i] - 'a';
            if(edge[u][v]) continue;
            edge[u][v] = true;
            G[u].emplace_back(v);
            indeg[v]++;
            outdeg[u]++;
        }
        
        // outdeg
        for(int i=0; i<N; i++) if(outdeg[i] >= 2) return false;
        
        // exist non-loop vertex
        queue<int> que;
        
        bool non_loop = false;
        for(int i=0; i<N; i++) {
            if(indeg[i] == 0) {
                non_loop = true;
                que.emplace(i);
            }
        }
        while(que.size()) {
            int cur = que.front(); que.pop();
            for(auto to : G[cur]) {
                if(--indeg[to] == 0) {
                    non_loop = true;
                    que.emplace(to);
                }
            }
        }
        
        if(!non_loop) return false;
        return true;
    }
};

こういうの一発で通せるようになりたいですね。

CodeChef July Challenge: Parity Again

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

問題概要

原文 → Contest Page | CodeChef

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

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

制約

  •  1 \leq Q, X \leq 10^{5}

解説

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

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

  • ある整数  x, y についてどちらも  S に含まれている場合、 x \oplus y S に含まれている

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

  • ある整数  x S に含まれておらず、 y S に含まれている場合、 x \oplus y S に含まれていない

背理法でこれを示す。 x \oplus y S に含まれていたとしよう。 y x \oplus y も含まれていることと、上の条件より、 y \oplus (x \oplus y) = x S に含まれる。しかし、これは仮定に矛盾するので、 x \notin S かつ  y \in S であるならば  x \oplus y \notin S である。

これを踏まえると、 X S に含まれていない場合は  S にすでに存在する要素と xor を取ることで常に新たな要素を作ることになるし、 X が含まれている場合は  S にすでに存在する要素と 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

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

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

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

解説

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

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

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

  •  \max(h_1, w_1) = h_1, \max(h_2, w_2) = h_2 のとき
    • 上の不等式から明らかに成立
  •  \max(h_1, w_1) = w_1, \max(h_2, w_2) = w_2 のとき
    • 上の不等式から明らかに成立
  •  \max(h_1, w_1) = h_1, \max(h_2, w_2) = w_2 のとき
    • 別々に取ると  h_1 + w_2 だけコストがかかるが、 w_1 \leq h_1 より  W \leq w_1 + w_2 \leq h_1 + w_2 であることがわかり、 h_2 \leq w_2 より  H \leq h_1 + h_2 \leq h_1 + w_2 であることもわかるので、  (H, W) の長方形を取って損しないことが分かる
  •  \max(h_1, w_1) = w_1, \max(h_2, w_2) = h_2 のとき
    • 上と同様の理由で成立

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

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

ソースコード

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