2019-08-11

TopCoder SRM 764: RectangleHunt

TopCoder 幾何

問題概要

原文 → TopCoder Statistics - Problem Statement

$N$ 個の点が与えられる。

与えられる点から 4 つ選んでできる長方形のうち、面積が最大のものを答えよ。ただし長方形を作ることができなければ -1 と答えよ。なお、長方形は軸に平行でなくてもよい。

解説

全探索が許される制約なので、4 重ループをしてそれぞれについて長方形になりうるかどうかを判定すればよい。

長方形を判定する前に、平行四辺形の場合にどのように判定するべきかを考える。以下、平行四辺形の頂点を反時計回りに $a, b, c, d$ とそれぞれおくことにする。おそらく最も簡単なのは以下の判定方法である。

辺 $ab$ と辺 $dc$ が平行
辺 $ad$ と辺 $bc$ が平行

しかし、これだけではまだ不十分な場合があって、たとえば一直線上に $a, c, b, d$ と並んでいるとき、上の条件をすべて満たしてしまう。なので、追加で以下の条件も見る必要がある。

辺 $ac$ と辺 $bd$ が平行でない

これらは全て外積の計算で判定できる。

では元の問題に立ち返り、長方形の場合にどうすべきか考える。長方形とは平行四辺形の特殊な例で、対角線の長さが等しくなる。つまり、下の条件も満たす必要がある。

辺 $ac$ と辺 $bd$ の長さが等しい

今回の問題とは関係ないが、正方形かどうかを判定するには 4 辺すべての辺の長さが等しい必要があるので追加で以下の条件も必要になるはず。(これが必要十分でなかったら教えてください)

辺 $ad$ と辺 $ab$ の長さが等しい

struct RectangleHunt {
    ll cross(pair<ll, ll> a1, pair<ll, ll> a2, pair<ll, ll> b1, pair<ll, ll> b2) {
        ll x1 = a1.first - a2.first;
        ll x2 = b1.first - b2.first;
        ll y1 = a1.second - a2.second;
        ll y2 = b1.second - b2.second;

        ll res = x1 * y2 - x2 * y1;
        return res;
    }

    ll area(pair<ll, ll> a1, pair<ll, ll> a2, pair<ll, ll> b1) {
        ll x1 = a1.first - b1.first;
        ll x2 = a2.first - b1.first;
        ll y1 = a1.second - b1.second;
        ll y2 = a2.second - b1.second;
        return llabs(x1 * y2 - y1 * x2);
    }

    ll len(pair<ll, ll> s1, pair<ll, ll> s2) {
        ll dfx = s1.first - s2.first;
        ll dfy = s1.second - s2.second;
        return dfx * dfx + dfy * dfy;
    }
    
    double get(const vector< pair<int, int> > &points, const vector<int> &ord) {
        vector< pair<int, int> > p;
        for(int i=0; i<4; i++) {
            p.emplace_back(points[ ord[i] ]);
        }

        if(cross(p[0], p[1], p[3], p[2]) != 0) return -1;
        if(cross(p[0], p[3], p[1], p[2]) != 0) return -1;
        if(cross(p[0], p[2], p[1], p[3]) == 0) return -1;
        if(len(p[0], p[2]) != len(p[1], p[3])) return -1;
        return area(p[0], p[1], p[3]);
    }
    
    double largest(vector <int> x, vector <int> y) {
        double ans = -1;
        int N = x.size();
        for(int i=0; i<N; i++) {
            for(int j=i+1; j<N; j++) {
                for(int k=j+1; k<N; k++) {
                    for(int l=k+1; l<N; l++) {
                        vector< pair<int, int> > points;
                        points.emplace_back(make_pair(x[i], y[i]));
                        points.emplace_back(make_pair(x[j], y[j]));
                        points.emplace_back(make_pair(x[k], y[k]));
                        points.emplace_back(make_pair(x[l], y[l]));

                        vector<int> ord(4);
                        iota(ord.begin(), ord.end(), 0);

                        do {
                            ans = max(ans, get(points, ord));
                        }while(next_permutation(ord.begin(), ord.end()));
                    }
                }
            }
        }
        return ans;
    }
};

幾何の条件いつもミスするけどそろそろどうにかしたいな。

2019-08-11

LeetCode Biweekly Contest 6: String Transforms Into Another String

LeetCode グラフ

問題概要

原文 → 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;
    }
};

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

2019-08-03

CodeChef July Challenge: Parity Again

CodeChef

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

問題概要

原文 → Contest Page | CodeChef

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

整数が与えられるので以下を処理
- $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());
        }
    }
}

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

hogecoder

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

TopCoder SRM 764: RectangleHunt

問題概要

解説

LeetCode Biweekly Contest 6: String Transforms Into Another String

問題概要

解説

CodeChef July Challenge: Parity Again

問題概要

解説

ソースコード