2019-08-11

LeetCode Weekly Contest 149: Online Majority Element In Subarray

LeetCode

問題概要

はじめに、長さ $N$ の数列 $A$ が与えられるので、以下のクエリにオンラインで答えよ。

$A$ の $l$ 番目から $r$ 番目の間に $x$ 回以上出現するものを答えよ。なお $x$ は区間の長さの半分を真に超えるため該当する場合は 1 つしか該当しない。そのような要素がなければ -1 と答えよ。

解説

クエリの長さで平方分割を行う。ある $s$ があって、クエリで与えられる区間の長さが $s$ 以下であるかどうかで場合分けを行う。

長さが以下である場合
- この場合は $l$ から $r$ までを愚直に調べて、最も多いものが条件を満たすかどうかを見ればよい。
長さが以上である場合
- クエリで与えられる区間の長さを $L$ とする。クエリの条件より、答えが存在するならばその数は区間内に $\frac{L}{2}$ 回を超えて出現するはずであるため、そもそも数列内に $\frac{L}{2}$ 回以下しか登場しない要素について調べる必要がない。そして、 $L \geq s$ であることから、調べるべき要素の種類数は高々 $\frac{2N}{s}$ 個である。よって、各要素についてインデックス列を持ち二分探索を行うことで処理できる。

$s = \sqrt{N}$ と置くと、前者の処理で $O(\sqrt{N})$ に、後者の処理で $O(\sqrt{N} \log(N))$ となるので、高速に処理可能である。

別解

知りたいのは区間内の majority なので、区間内にある値を乱択し、それが majority であるかどうかをチェックするだけでも高い確率で通る。majority ならば選ばれる確率はだいたい 2 分の 1 で、20 回試行したときにそれを全部外すのは $\frac{1}{2^{20}}$ なので、確率としてはとても低い。

ソースコード

愚直に調べるパートには Boyer-Moore majority vote algorithm を使用している。線形だけど定数倍が軽そう。

class MajorityChecker {
public:
    vector<int> vec;
    unordered_map< int, vector<int> > rec;
    vector< pair<int, int> > occur;
    int s;
    MajorityChecker(vector<int>& arr) {
        this->vec = arr;
        int N = vec.size(); s = sqrt(N);
        for(int i=0; i<N; i++) {
            rec[ vec[i] ].emplace_back(i);
        }
        for(auto e : rec) {
            occur.emplace_back(e.second.size(), e.first);
        }
        sort(occur.rbegin(), occur.rend());
    }
    
    int query(int left, int right, int threshold) {
        right++;
        if(right - left <= s) {
            int cand = 0, cnt = 0;
            for(int i=left; i<right; i++) {
                if(cnt == 0) cand = vec[i], cnt = 1;
                else if(cand == vec[i]) cnt++;
                else cnt--;
            }
            for(int i=left; i<right; i++) {
                if(vec[i] == cand) threshold--;
            }
            return (threshold <= 0 ? cand : -1);
        }
        else {
            for(size_t k=0; k<occur.size(); k++) {
                int cand = occur[k].second, cnt = occur[k].first;
                if(cnt < threshold) break;
                auto u = lower_bound(rec[cand].begin(), rec[cand].end(), right);
                auto d = lower_bound(rec[cand].begin(), rec[cand].end(), left );
                if(u - d >= threshold) return cand;
            }
            return -1;
        }
    }
};

これは勉強になりました。

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

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

hogecoder

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

LeetCode Weekly Contest 149: Online Majority Element In Subarray

問題概要

解説

別解

ソースコード

TopCoder SRM 764: RectangleHunt

問題概要

解説

LeetCode Biweekly Contest 6: String Transforms Into Another String

問題概要

解説